Small-world network

Small-world network example
Hubs are bigger than other nodes Average vertex degree = 1.917
Average shortest path length = 1.803.
Clusterization coefficient = 0.522
Random graph
Average vertex degree = 1.417
Average shortest path length = 2.109.
Clusterization coefficient = 0.167

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. Specifically, a small-world network is defined to be a network where the typical distance L between two randomly chosen nodes (the number of steps required) grows proportionally to the logarithm of the number of nodes N in the network, that is:[1]

L \propto \log N

In the context of a social network, this results in 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, wikis such as Wikipedia, 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.[2] They noted that graphs could be classified according to two independent structural features, namely the clustering coefficient, and average node-to-node distance (also known as average shortest path length). Purely random graphs, built according to the Erdős–Rényi (ER) 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, currently named the Watts and Strogatz model, with (i) a small average shortest path length, and (ii) a large clustering coefficient. The crossover in the Watts-Strogatz model between a "large world" (such as a lattice) and a small world was first described by Barthelemy and Amaral in 1999.[3] This work was followed by a large number of studies, including exact results (Barrat and Weigt, 1999; Dorogovtsev and Mendes; Barmpoutis and Murray, 2010).

Properties of small-world networks

Small-world networks tend to contain cliques, and near-cliques, meaning sub-networks which have connections between almost any two nodes within them. This follows from the defining property of a high clustering coefficient. Secondly, most pairs of nodes will be connected by at least one short path. This follows from the defining property that the mean-shortest path length be small. Several other properties are often associated with small-world networks. Typically there is an over-abundance of hubs - nodes in the network with a high number of connections (known as high degree nodes). 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. Graphs of very different topology qualify as small-world networks as long as they satisfy the two definitional requirements above.

Network small-worldness has been quantified by comparing clustering and path length of a given to network to an equivalent random network with same degree distribution.[4] Another method for quantifying network small-worldness utilizes the original definition of the small-world network comparing the clustering of a given network to an equivalent lattice network and its path length to an equivalent random network.[5] The small-world measure (\omega) is defined as

\omega = \tfrac{L_r}{L} - \tfrac{C}{C_l}

R. Cohen and Havlin[6][7] showed analytically that scale-free networks are ultra-small worlds. In this case, due to hubs, the shortest paths become significantly smaller and scale as

L \propto \log \log N

Examples of small-world networks

Small-world properties are found in many real-world phenomena, including websites with navigation menus, food chains, electric power grids, metabolite processing networks, networks of brain neurons, voter networks, telephone call graphs, and social influence networks.

Networks of connected proteins have small world properties such as power-law obeying degree distributions.[8] Similarly transcriptional networks, in which the nodes are genes, and they are linked if one gene has an up or down-regulatory genetic influence on the other, have small world network properties.[9]

Examples of non-small-world networks

Networks are less likely to have the small-world properties if links between nodes arise mainly from spatial or temporal proximity, because there may be no short path between two "distant" nodes. Being constrained to physical space or time, as in a subway system or road network, tends to impede the formation of particularly long links that are conducive to hub formation.

In another example, the famous theory of "six degrees of separation" between people tacitly presumes that the domain of discourse is the set of people alive at any one time. The number of degrees of separation between Albert Einstein and Alexander the Great is almost certainly greater than 30 and this network does not have small-world properties. 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.

Tacit assumptions, if not examined, can cause a bias in the literature on graphs in favor of finding small-world networks (an example of the file drawer effect resulting from the publication bias).

Network robustness

It is hypothesized by some researchers such as Barabási 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. As the fraction of peripheral nodes in a small world network is much higher than the fraction of hubs, the probability of deleting an important node is very low. For example, if the small airport in Sun Valley, Idaho was 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. However, 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, such as Chicago's O'Hare airport, are shut down because of snow; many people 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

The main mechanism to construct small-world networks is the Watts-Strogatz mechanism.

Small-world networks can also be introduced with time-delay,[10] which will not only produces fractals but also chaos[11] under the right conditions, or transition to chaos in dynamics networks.[12]

Degree-Diameter graphs are constructed such that the number of neighbors 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 minimized. Constructing such small-world networks is done as part of the effort to find graphs of order close to the Moore bound.

Another way to construct a small world network from scratch is given in Barmpoutis et al.,[13] where a network with very small average distance and very large average clustering is constructed. A fast algorithm of constant complexity is given, along with measurements of the robustness of the resulting graphs. Depending on the application of each network, one can start with one such "ultra small-world" network, and then rewire some edges, or use several small such networks as subgraphs to a larger graph.

See also: Diffusion-limited aggregation, pattern formation

Applications

Applications to sociology

The advantages to small world networking for social movement groups are their resistance to change due to the filtering apparatus of using highly connected nodes, and its better effectiveness in relaying information while keeping the number of links required to connect a network to a minimum.[14]

The small world network model is directly applicable to affinity group theory represented in sociological arguments by William Finnegan. Affinity groups are social movement groups that are small and semi-independent pledged to a larger goal or function. Though largely unaffiliated at the node level, a few members of high connectivity function as connectivity nodes, linking the different groups through networking. This small world model has proven an extremely effective protest organization tactic against police action.[15] Clay Shirky argues that the larger the social network created through small world networking, the more valuable the nodes of high connectivity within the network.[14] The same can be said for the affinity group model, where the few people within each group connected to outside groups allowed for a large amount of mobilization and adaptation. A practical example of this is small world networking through affinity groups that William Finnegan outlines in reference to the 1999 Seattle WTO protests.

Applications to earth sciences

Many networks studied in geology and geophysics have been shown to have characteristics of small-world networks. Networks defined in fracture systems and porous substances have demonstrated these characteristics.[16] The seismic network in the Southern California region may be a small-world network.[17] The examples above occur on very different spatial scales, demonstrating the scale invariance of the phenomenon in the earth sciences.

Applications to computing

Small-world networks have been used to estimate the usability of information stored in large databases. The measure is termed the Small World Data Transformation Measure.[18][19] The greater the database links align to a small-world network the more likely a user is going to be able to extract information in the future. This usability typically comes at the cost of the amount of information that can be stored in the same repository.

The Freenet peer-to-peer network has been shown to form a small-world network in simulation,[20] allowing information to be stored and retrieved in a manner that scales efficiency as the network grows.

Small-world neural networks in the brain

Both anatomical connections in the brain[21] and the synchronization networks of cortical neurons[22] exhibit small-world topology.

A small-world network of neurons can exhibit short-term memory. A computer model developed by Solla et al.[23][24] had two stable states, a property (called bistability) thought to be important in memory storage. An activating pulse generated self-sustaining loops of communication activity among the neurons. A second pulse ended this activity. The pulses switched the system between stable states: flow (recording a "memory"), and stasis (holding it).

On a more general level, many large-scale neural networks in the brain, such as the visual system and brain stem, exhibit small-world properties.[4]

Small world with a distribution of link length

The WS model includes a uniform distribution of long-range links. When the distribution of link lengths follows a power law distribution, the mean distance between two sites changes depending on the power of the distribution.[25]

See also

References

  1. ↑ http://www.nature.com/nature/journal/v393/n6684/full/393440a0.html
  2. ↑ Watts, Duncan J.; Strogatz, Steven H. (June 1998). "Collective dynamics of 'small-world' networks". Nature 393 (6684): 440–442. Bibcode:1998Natur.393..440W. doi:10.1038/30918. PMID 9623998. Papercore Summary http://www.papercore.org/Watts1998
  3. ↑ Barthelemy, M.; Amaral, LAN (1999). "Small-world networks: Evidence for a crossover picture". Phys. Rev. Lett. 82 (15): 3180. arXiv:cond-mat/9903108. Bibcode:1999PhRvL..82.3180B. doi:10.1103/PhysRevLett.82.3180.
  4. ↑ 4.0 4.1 Is there a brainstem substrate for action selection? M. D. Humphries, K. Gurney and T. J. Prescott, Phil. Trans. R. Soc. B 2007 362, 1627-1639, doi:10.1098/rstb.2007.2057
  5. ↑ The ubiquity of small-world networks Q.K. Telesford, K.E. Joyce, S. Hayasaka, J.H. Burdette, P.J. Laurienti, Brain Connect. 2011;1(5):367-75, doi:10.1089/brain.2011.0038
  6. ↑ R. Cohen, S. Havlin, and D. ben-Avraham (2002). "Structural properties of scale free networks". Handbook of graphs and networks (Wiley-VCH, 2002) (Chap. 4).
  7. ↑ R. Cohen, S. Havlin (2003). "Scale-free networks are ultrasmall". Phys. Rev. Lett. 90 (5): 058701. arXiv:cond-mat/0205476. Bibcode:2003PhRvL..90e8701C. doi:10.1103/PhysRevLett.90.058701. PMID 12633404.
  8. ↑ Bork, P.; Jensen, LJ; von Mering, C.; Ramani, A.; Lee, I.; Marcotte, EM. (2004). "Protein interaction networks from yeast to human" (PDF). Current Opinion in Structural Biology 14 (3): 292–299. doi:10.1016/j.sbi.2004.05.003. PMID 15193308.
  9. ↑ Van Noort, V; Snel, B; Huynen, MA. (Mar 2004). "The yeast coexpression network has a small-world, scale-free architecture and can be explained by a simple model". EMBO Rep. 5 (3): 280–4. doi:10.1038/sj.embor.7400090. PMC 1299002. PMID 14968131.
  10. ↑ X. S. Yang, Fractals in small-world networks with time-delay, Chaos, Solitons & Fractals, vol. 13, 215-219 (2002)
  11. ↑ X. S. Yang, Chaos in small-world networks, Phys. Rev. E 63, 046206 (2001)
  12. ↑ W. Yuan, X. S. Luo, P. Jiang, B. Wang, J. Fang, Transition to chaos in small-world dynamical network
  13. ↑ D.Barmpoutis and R.M. Murray (2010). "Networks with the Smallest Average Distance and the Largest Average Clustering". arXiv:1007.4031 [q-bio.MN].
  14. ↑ 14.0 14.1 Shirky, Clay. 2008. Here Comes Everybody
  15. ↑ Finnegan, William "Affinity Groups and the Movement Against Corporate Globalization"
  16. ↑ X. S. Yang, Small-world networks in geophysics, Geophys. Res. Lett., 28(13), 2549–2552 (2001)
  17. ↑ A. Jimenez, K. F. Tiampo, and A. M. Posadas, Small-world in a seismic network: the California case, Nonlin. Processes Geophys., 15, 389-395 (2008)
  18. ↑ http://mike2.openmethodology.org/wiki/Small_Worlds_Data_Transformation_Measure
  19. ↑ Hillard, Robert (2010). Information-Driven Business. Wiley. ISBN 978-0-470-62577-4.
  20. ↑ Sandberg, Oskar. "Searching in a Small World" (PDF).
  21. ↑ Sporns, Olaf; Chialvo DR; Kaiser M; Hilgetag CC (2004). "Organization, development and function of complex brain networks". Trends Cogn Sci. 8 (9): 418–425. doi:10.1016/j.tics.2004.07.008. PMID 15350243.
  22. ↑ Yu, Shan; D. Huang, W. Singer and D. Nikolić (2008). "A Small World of Neuronal Synchrony". Cerebral Cortex 18 (12): 2891–2901. doi:10.1093/cercor/bhn047. PMC 2583154. PMID 18400792.
  23. ↑ Cohen, Philip. Small world networks key to memory. New Scientist. 26 May 2004.
  24. ↑ Sara Solla's Lecture & Slides: Self-Sustained Activity in a Small-World Network of Excitable Neurons
  25. ↑ D. Li, K. Kosmidis, A. Bunde, S. Havlin (2011). "Dimension of spatially embedded networks". Nature Physics. Bibcode:2011NatPh...7..481D. doi:10.1038/nphys1932.

Books

Journal articles

External links