Graph Theory & Small Networks

Introduction

Networks are everywhere. The brain is a sophisticated neural network connected by axons. Society, too, are networks connected by family, friends and professional ties. On a larger scale food webs can be represented as a network of species. Networks have even diffused through our technology such as the World Wide Web where routers and web pages are all interconnected. Even the language we speak today is a network of words connected by syntactic associations. Networks are everywhere.

Yet despite the importance and frequency of such complex networks, little is understood of their properties and structure. How do viruses diffuse so rapidly in communication systems? How do some networks continue to function even after a vast majority of their nodes have failed? Is it possible that everyone is connected by six handshakes?

For much of the last century, scientists treated all complex networks as being completely random. This theory had its roots in the work of two mathematicians, Paul Erdos and Alfred Renyi. Their work suggested that systems such as communications could be effectively modelled by connecting nodes with randomly placed links. Their simple approach revitalised graph theory and led to the emergence of the field of random networks.

An important prediction of random network theory is regardless of the random placement of links most nodes will still have approximately the same number of links. In fact, in a random network the nodes follow a Poisson distribution with a bell shape (see Fig.1). Random networks are also called exponential, because the probability that a node is connected to k other sites decreases exponentially for large k. This is better described by the famous small world networks. It was Watts and Strogatz in 1998 that recognised that a class of random graphs could be categorised as small world networks. They noted that graphs could be classified according to their clustering coefficient and their diameter. Many random graphs show a small diameter and also have a small clustering coefficient. What Strogatz and Watts found was that in real world networks the diameter is still small but has a clustering coefficient significantly higher than expected by random chance. Watts and Strogatz thus proposed a simple model of random graphs with (a) a small diameter and (b) a large clustering coefficient.

I wasn't until 1998 when Albert-Lбszlǒ Barabбsi and fellow workers from the University of Notre Dame, embarked on a project to map the World Wide Web, expecting to find a random network. Instead their measurements defied that expectation. Even though their research only covered a minute portion of the entire Web, the map it uncovered revealed some surprising results. A few highly connected pages were essentially holding the World Wide Web together. It was found that more than 80% of the web pages had fewer than four links, but a small minority, less than 0.01% of all web pages had 1,000 links. One node was found to have more than two million links!

Whilst analysing how many web pages had exactly k of links they showed that the distribution follow a so called power law rather than a bell shaped distributions that define random networks. The power law states that the probability that any node was connected to k other nodes was proportional to . In the case of the web n was found to be 2, meaning any node was approximately four times more likely to have half the number of incoming links as another node.

Whilst Poisson distributions have a peak, power laws do not follow and instead illustrate a decreasing function (see Fig. 2). When plotted on a double logarithmic scale the power is a straight line (see Fig. 3). Unlike the seemingly even distribution of links in random networks, the power law describes a system where a few nodes/hubs dominate. Hubs are ,to put it simply, forbidden in random networks and thus a new type of network was discovered, scale-free networks.

Example of Random and Scale Free Networks

This simplified map of the US highway system, consists of nodes with randomly placed connections. In such random networks, the distribution curve of node linkages follows a bell shaped curves (Fig.1). This tells us that a majority of the nodes have the same number of links

This simplified map of the US airline system shows a scale free network. The hubs (red) are the nodes with a very high number of links. In this type of network the linkages between nodes follow a power law where most nodes have just a few links but a certain few nodes have a substantial number of linkages (Fig.2). The defining characteristic of a scale free network is that the distribution of the links when plotted on a Log-Log graph results in a straight line (Fig.3).

How common are Scale-Free Networks?

Researchers have uncovered scale fee structures in a stunning range of systems. Whilst the virtual side of the internet was the fist scale free network discovered it was also found that the physical, router structure of the internet was also scale free. Scientists in Sweden discovered that some social networks were scale free, for instance the network of sexual relationships followed a power law. Scale free networks also cropped up in business where a study into the US biotechnology industry showed companies such as Genzyme and Chiron having a extremely large number of partnerships as thus acting as hubs. Scale free has also been discovered in the protein interaction network. Even the network of actors in Hollywood in which the links between actors are the movies in which they have appeared in are scale free. So to answer the question simply, scale-free networks are stunningly common in most networks. The big question is can systems so different have the same structure and obey the same laws?

Random