Small-world network

In mathematics and physics, a small-world network is a type of mathematical graph in which most nodes are not neighbors of one another, but most nodes can be reached from every other by a small number of hops or steps. A small world network, where nodes represent people and edges connect people that know each other, captures the small world phenomenon of strangers being linked by a mutual acquaintance.

Many empirical graphs are well modeled by small-world networks. Social networks, the connectivity of the Internet, and gene networks all exhibit small-world network characteristics.

A certain category of small-world networks were identified as a class of random graphs by Duncan Watts and Steven Strogatz in 1998. They noted that graphs could be classified according to two independent structural features, namely the clustering coefficient and average node-to-node distance, the latter also known as average shortest path length. Purely random graphs, built according to the Erdős–Rényi model, exhibit a small average shortest path length (varying typically as the logarithm of the number of nodes) along with a small clustering coefficient. Watts and Strogatz measured that in fact many real-world networks have a small average shortest path length, but also a clustering coefficient significantly higher than expected by random chance. Watts and Strogatz then proposed a novel graph model, now currently named the Watts and Strogatz model, with (i) a small average shortest path length, and (ii) a large clustering coefficient. The first description of the crossover in the Watts-Strogatz model between a "large world" (such as a lattice) and a small-world was described by Barthelemy and Amaral in 1999. This work was followed by a large number of studies including exact results (Barrat and Weigt, 1999; Dorogovtsev and Mendes)

Properties of small-world networks

By virtue of the above definition, small-world networks will inevitably have high representation of cliques, and subgraphs that are a few edges shy of being cliques, i.e. small-world networks will have sub-networks that are characterized by the presence of connections between almost any two nodes within them. This follows from the requirement of a high cluster coefficient. Secondly, most pairs of nodes will be connected by at least one short path. This follows from the requirement that the mean-shortest path length be small. Additionally, there are several properties that are commonly associated with small-world networks even though they are not required for that classification. Typically there is an over-abundance of "hubs" - nodes in the network with a high number of connections (known as high degree). These hubs serve as the common connections mediating the short path lengths between other edges. By analogy, the small-world network of airline flights has a small mean-path length (i.e. between any two cities you are likely to have to take three or fewer flights) because many flights are routed through hub cities.

This property is often analyzed by considering the fraction of nodes in the network that have a particular number of connections going into them (the degree distribution of the network). Networks with a greater than expected number of hubs will have a greater fraction of nodes with high degree, and consequently the degree distribution will be enriched at high degree values. This is known colloquially as a fat-tailed distribution. Specifically, if a network has a degree-distribution which can be fit with a power law distribution, it is taken as a sign that the network is small-world. Power law distributions have fat tails when compared to exponential distributions characteristic of random networks. These networks are known as scale-free networks.

This type of network is by no means the only kind of small-world network. Graphs of very different topology can still qualify as small-world networks as long as they satisfy the two definitional requirements above.

Examples of small-world networks

Small-world networks have been discovered in a surprising number of natural phenomena. For example, networks [http://polaris.icmb.utexas.edu/paper-pdfs/cosb-review.pdf] composed of proteins with connections indicating that the proteins physically interact have power-law obeying degree distributions and are small-world. Similarly transcriptional networks in which genes correspond to nodes, and up or down-regulatory genetic influence correspond to connections are small world networks obeying power-laws [http://www.jsbi.org/journal/GIW05/GIW05F030.html] .

There are also many other graphs which have been found to exhibit small-world properties. Examples include road maps, food chains, electric power grids, metabolite processing networks, neural networks, voter networks, telephone call graphs, and social influence networks.

In 2004, Sara Solla et al. developed a computer model of short-term memory constructed around a small-world network [http://www.newscientist.com/article.ns?id=dn5012] . This model successfully demonstrated bistability, a property thought to be important in memory storage. The bistability appears to be the result of recurrent self-sustaining loops of activity after an activating pulse is given. A second pulse would turn off the system. Hence, the pulses switch the system between its bistable states.

A functioning large small-world network that can be viewed and analysed by anyone is XING. It shows that of the more than 1,000,000 members worldwide hardly anyone is more than five or six nodes away from any random other person.

Non-examples of small-world networks

There are also several examples of naturally occurring graphs that are not small networks. These are especially likely to occur where the links in the graph arise from some form of physical proximity, e.g., spatial or temporal proximity.

For example, the famous "six degrees of separation" between people tacitly presumes that the domain of discourse is people alive at any one time. If persons A and B are linked if A and B knew each other, then the number of degrees of separation between Albert Einstein and Alexander the Great is almost certainly greater than 30. A similarly constrained network would be the "went to school with" network: if two people went to the same college ten years apart from one another, it is unlikely that they have acquaintances in common amongst the student body.

Similarly, the number of relay stations through which a message must pass was not always small. In the days when the post was carried by hand or on horseback, the number of times a letter changed hands between its source and destination would have been much greater than it is today. The number of times a message changed hands in the days of the visual telegraph (circa 1800-1850) was determined by the requirement that two stations be connected by line-of-sight.

These considerations are sometimes important, especially since the literature on graphs is sometimes biased in favour of finding small-world networks. There are certainly naturally occurring examples of small-world networks, but it is also possible to introduce tacit assumptions so that models that exhibit small-world properties are preferred.

Network robustness

It is hypothesized by some researchers such as Barabasi that the prevalence of small world networks in biological systems may reflect an evolutionary advantage of such an architecture. One possibility is that small-world networks are more robust to perturbations than other network architectures. If this were the case, it would provide an advantage to biological systems that are subject to damage by mutation or viral infection.

In a power law distributed small world network, deletion of a random node rarely causes a dramatic increase in mean-shortest path length (or a dramatic decrease in the clustering coefficient). This follows from the fact that most shortest paths between nodes flow through hubs, and if a peripheral node is deleted it is unlikely to interfere with passage between other peripheral nodes. For example, if the small airport in Sun Valley, Idaho were shut down, it would not increase the average number of flights that other passengers traveling in the United states would have to take to arrive at their respective destinations. That said, if random deletion of a node hits a hub by chance, the average path length can increase dramatically. This can be observed annually when northern hub airports are shut down because of snow. If Chicago's O'Hare airport shut down, many people would have to take additional flights.

By contrast, in a random network, in which all nodes have roughly the same number of connections, deleting a random node is likely to increase the mean-shortest path length slightly but significantly for almost any node deleted. In this sense, random networks are vulnerable to random perturbations, whereas small-world networks are robust. However, small-world networks are vulnerable to targeted attack of hubs, whereas random networks cannot be targeted for catastrophic failure.

Appropriately, viruses have evolved to interfere with the activity of hub proteins such as p53, thereby bringing about the massive changes in cellular behavior which are conducive to viral replication.

Construction of small-world networks

Several procedures are known to generate small-world networks from scratch. One of these methods is known as "preferential attachment" [http://arxiv.org/abs/cond-mat/9910332] . In this model, new nodes are added to a pre-existing network, and connected to each of the original nodes with a probability proportional to the number of connections each of the original nodes already had. I.e., new nodes are more likely to attach to hubs than peripheral nodes. Statistically, this method will generate a power-law distributed small-world network (that is, a scale-free network).

Elements of this mechanism can be seen to contribute to the small-worldness of the World Wide Web. A new site is more likely to have links to major pre-existing sites, such as Google or Wikipedia than arbitrary small obscure sites. This observation is known colloquially as a "rich get richer" model.

Degree-Diameter graphs are constructed such that the number of neighbours each vertex in the network has is bounded, while the distance from any given vertex in the network to any other vertex (the diameter of the network) is minimised. Constructing such small-world networks is done as part of the effort to find graphs of order close to the Moore bound.

"See also:" Diffusion-limited aggregation, pattern formation

Footnotes

# [http://polaris.icmb.utexas.edu/paper-pdfs/cosb-review.pdf Review article on protein interaction networks ]
# [http://www.jsbi.org/journal/GIW05/GIW05F030.html Article on topology of mammalian transcription networks]
# [http://arxiv.org/abs/cond-mat/9910332 Barabasi preferential attachment article]

ee also

* Erdős number
* Scale-free network
* Six degrees of Kevin Bacon
* Small world experiment
* Social network

References

Books

*cite book | author=Buchanan, Mark | title=Nexus: Small Worlds and the Groundbreaking Theory of Networks | publisher=Norton, W. W. & Company, Inc | year=2003 | id=ISBN 0-393-32442-7
*cite book | author=Dorogovtsev, S.N. and Mendes, J.F.F. | title=Evolution of Networks: from biological networks to the Internet and WWW | publisher=Oxford University Press | year=2003 | id=ISBN 0-19-851590-1
*cite book | author=Watts, D. J. | year=1999 | title=Small Worlds: The Dynamics of Networks Between Order and Randomness | publisher=Princeton University Press | id=ISBN 0-691-00541-9
* Fowler, JH. (2005) "Turnout in a Small World," in Alan Zuckerman, ed., "Social Logic of Politics", Temple University Press, 269-287

Journal articles

*cite journal | author=Albert, R.; Barabási A.L. | title= Statistical mechanics of complex networks | journal=Rev. Mod. Phys. | year=2002 | volume=74 | pages=47–97 | doi= 10.1103/RevModPhys.74.47
*cite journal | author=Barthelemy, M.; Amaral, LAN. | title= Small-world networks: Evidence for a crossover picture| journal=Phys. Rev. Lett. | year=1999 | volume=82 | pages=3180 | doi= 10.1103/PhysRevLett.82.3180
*cite journal | author=Dorogovtsev, S.N.; Mendes, J.F.F. | title= Exactly solvable analogy of small-world networks| journal=Europhys. Lett. | year=2000 | volume=50 | pages=1–7 | doi= 10.1209/epl/i2000-00227-1
*cite journal | author=Milgram, Stanley | title=The Small World Problem | journal=Psychology Today | year=1967 | volume=1 | issue=1 |pages=60–67
*cite journal | author=Newman, Mark | title=The Structure and Function of Complex Networks | journal=SIAM Review | year=2003 | volume=45 | pages=167–256 | doi=10.1137/S003614450342480 [http://www.santafe.edu/files/gems/paleofoodwebs/Newman2003SIAM.pdf pdf]
*cite journal | author=Ravid, D.; Rafaeli, S. | title=Asynchronous discussion groups as Small World and Scale Free Networks | journal=First Monday | year=2004 | volume=9 | issue=9 [http://firstmonday.org/issues/issue9_9/ravid/index.html]
*cite journal | author=Watts, Duncan J.; Strogatz, Steven H. | title=Collective dynamics of 'small-world' networks | journal=Nature | month=June | year=1998 | volume=393 | pages=440–442 | doi=10.1038/30918 [http://web.archive.org/web/20070418032327/http://www.tam.cornell.edu/SS_nature_smallworld.pdf]

External links

* [http://video.google.com/videoplay?docid=6310063982690417420 MIT Linear Algebra Lecture on Small-World Graphs] at Google Video, from MIT OpenCourseWare
* [http://online.itp.ucsb.edu/online/brain04/solla/ Dr. Sara Solla] - Lecture & Slides: Self-Sustained Activity in a Small-World Network of Excitable Neurons
* [http://www.math.chalmers.se/~ossa/lic.pdf Oskar Sandberg] - Paper(PDF file): Searching in a Small World.
* [http://demonstrations.wolfram.com/DynamicProximityNetworks/ Dynamic Proximity Networks] by Seth J. Chandler, The Wolfram Demonstrations Project.