Networks are everywhere in the modern world. They may be physical constructs, like the transport system or power grid, or more abstract entities like family trees or the World Wide 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 [TM078; or search for “thatsmaths” at irishtimes.com ].
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 London Underground Map 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.
Distance, Density, Diameter
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.
A Traffic-Flow Paradox
Network analysis helps us to design more effective traffic systems, but careful analysis is vital: the German mathematician Dietrich Braess observed that adding an extra road to a network can actually increase congestion. Braess’ 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.
A Virus Flies Around the Globe
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 within three weeks. Knowledge of the spread pattern can enable 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 next Hamilton Day Lecture, sponsored by The Irish Times, is on understanding networks. It will be given tomorrow night (16 October) by Prof Daniel Spielman and tickets may be booked at http://www.ria.ie.
* * * * * *
Peter Lynch’s book about walking around the coastal counties of Ireland is now available as an ebook (at a very low price!). For more information and photographs go to RRI.