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

That’s Maths: Graph theory interprets the world as a series of nodes and their links, which aids greater understanding of networks

In 2003, Sars spread from Hong Kong to 37 countries within three weeks. Photograph: Christian Keenan/Getty Images

In 2003, Sars spread from Hong Kong to 37 countries within three weeks. Photograph: Christian Keenan/Getty Images

 

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
The Irish Times Logo
Commenting on The Irish Times has changed. To comment you must now be an Irish Times subscriber.
SUBSCRIBE
GO BACK
Error Image
The account details entered are not currently associated with an Irish Times subscription. Please subscribe to sign in to comment.
Comment Sign In

Forgot password?
The Irish Times Logo
Thank you
You should receive instructions for resetting your password. When you have reset your password, you can Sign In.
The Irish Times Logo
Please choose a screen name. This name will appear beside any comments you post. Your screen name should follow the standards set out in our community standards.
Screen Name Selection

Hello

Please choose a screen name. This name will appear beside any comments you post. Your screen name should follow the standards set out in our community standards.

The Irish Times Logo
Commenting on The Irish Times has changed. To comment you must now be an Irish Times subscriber.
SUBSCRIBE
Forgot Password
Please enter your email address so we can send you a link to reset your password.

Sign In

Your Comments
We reserve the right to remove any content at any time from this Community, including without limitation if it violates the Community Standards. We ask that you report content that you in good faith believe violates the above rules by clicking the Flag link next to the offending comment or by filling out this form. New comments are only accepted for 3 days from the date of publication.