From disease to data, it’s a small, networked world

Networks are everywhere. They may be physical constructs, like the transport system or power grid, or more abstract entities, such as family trees or the worldwide web. A network is a collection of nodes linked together, like cities connected by roads or people genetically related to each other. Such a system of nodes and links is what mathematicians call a graph.

Graph theory underlies the analysis of networks. A graph can be depicted by drawing dots for the nodes and lines for links between nodes. The map of the London Underground is a good example of a graph. Mathematically, a graph can be represented by a large array of numbers called an adjacency matrix, with ones for links between nodes and zeros elsewhere. In a computer, the graph is stored as a list or a matrix. A list is smaller, saving memory, but a matrix allows faster access.

Many physical systems can be modelled by graphs. For example, the internet is a graph whose nodes are computers and whose links are communication channels between them. Graph theory has widespread applications in chemistry, electronics, computer science, economics, biology and sociology and many other disciplines in addition to mathematics itself. It is valuable in understanding the behaviour of complex systems and can be used to predict the effects of changes in their structure.

Cluster coefficients

We can define the distance between nodes as the smallest number of links needed to connect them. The maximum distance is called the diameter of the graph. The graph density is the ratio of the number of links to the maximum possible number. If it is low, the graph is called sparse, and efficient algorithms are available for its analysis. Sub-graphs can be identified using measures called cluster coefficients. In a social network, people with common interests may form a cluster or clique.

A small graph diameter means that any node is reachable from another in few links. Social networks, with many cliques, are small-world networks like this. The “six degrees of separation” concept is that any two people are connected by acquaintance through a chain of six or fewer links.

Network analysis helps us to design more effective traffic systems, but careful analysis is vital: the German mathematician Dietrich Braess observed adding a road to a network can increase congestion. Braess’s paradox is an example of an emergent phenomenon: system behaviour cannot always be predicted from the properties of the individual components.

The structural analysis of a power grid gives vital information about its robustness against cascading failures. A higher level of connectivity means greater resilience, reducing the risk of blackouts, but is more expensive to install. Network analysis can provide an optimal design, given practical constraints.

Networks can be strongly interdependent. For example, the spread of disease depends on an infected person’s social network. But it can leap from one continent to another along the airline network. In 2003, Sars spread from Hong Kong to 37 countries in three weeks. Knowledge of the pattern can help health authorities to devise effective vaccination strategies.

The digital revolution has brought access to vast amounts of information on economic trading, biological reactions and human behaviour, and data volumes are growing exponentially. Many networks have millions or even billions of nodes, and network analysis is a rapidly changing field with intensive ongoing research.

• The Hamilton Day Lecture, sponsored by The Irish Times, takes place tomorrow at 7pm in the Edmund Burke Theatre, TCD. Prof Daniel Spielman will talk about understanding networks. Book on ria.ie
• Peter Lynch is emeritus professor at the school of mathematics and statistics at UCD. He blogs at thatsmaths.com