Small-world network
Part of a series on | ||||
Network science | ||||
---|---|---|---|---|
Network types | ||||
|
||||
Graphs | ||||
|
||||
Models | ||||
|
||||
| ||||
A small-world network is a graph characterized by a high clustering coefficient and low distances. On an example of social network, high clustering implies the high probability that two friends of one person are friends themselves. The low distances, on the other hand, mean that there is a short chain of social connections between any two people (this effect is known as six degrees of separation).[1] 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:[2]
while the global clustering coefficient is not small.
In the context of a social network, this results in the
A certain category of small-world networks were identified as a class of
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 a small-coefficient, , calculated by comparing clustering and path length of a given network to an equivalent random network with same degree on average.[6][7]
- if ( and ), network is small-world. However, this metric is known to perform poorly because it is heavily influenced by the network's size.[8][9]
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. The small-world measure () is defined as[8]
Where the characteristic path length L and clustering coefficient C are calculated from the network you are testing, Cℓ is the clustering coefficient for an equivalent lattice network and Lr is the characteristic path length for an equivalent random network.
Still another method for quantifying small-worldness normalizes both the network's clustering and path length relative to these characteristics in equivalent lattice and random networks. The Small World Index (SWI) is defined as[9]
Both ω′ and SWI range between 0 and 1, and have been shown to capture aspects of small-worldness. However, they adopt slightly different conceptions of ideal small-worldness. For a given set of constraints (e.g. size, density, degree distribution), there exists a network for which ω′ = 1, and thus ω aims to capture the extent to which a network with given constraints as small worldly as possible. In contrast, there may not exist a network for which SWI = 1, the thus SWI aims to capture the extent to which a network with given constraints approaches the theoretical small world ideal of a network where C ≈ Cℓ and L ≈ Lr.[9]
Examples of small-world networks
Small-world properties are found in many real-world phenomena, including websites with navigation menus, food webs, electric power grids, metabolite processing networks,
Networks of connected proteins have small world properties such as power-law obeying degree distributions.[13] 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.[14]
Examples of non-small-world networks
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[15] 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
Network robustness
It is hypothesized by some researchers, such as Albert-László 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 small world network with a degree distribution following a
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.
Construction of small-world networks
The main mechanism to construct small-world networks is the
Small-world networks can also be introduced with time-delay,[16] which will not only produce fractals but also chaos[17] under the right conditions, or transition to chaos in dynamics networks.[18]
Soon after the publication of
Another way to construct a small world network from scratch is given in Barmpoutis et al.,[20] 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.
Small-world properties can arise naturally in social networks and other real-world systems via the process of dual-phase evolution. This is particularly common where time or spatial constraints limit the addition of connections between vertices The mechanism generally involves periodic shifts between phases, with connections being added during a "global" phase and being reinforced or removed during a "local" phase.
Small-world networks can change from scale-free class to broad-scale class whose connectivity distribution has a sharp cutoff following a power law regime due to constraints limiting the addition of new links.[21] For strong enough constraints, scale-free networks can even become single-scale networks whose connectivity distribution is characterized as fast decaying.[21] It was also shown analytically that scale-free networks are ultra-small, meaning that the distance scales according to .[22]
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.[23]
The small world network model is directly applicable to
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.[25] The seismic network in the Southern California region may be a small-world network.[26] 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.[27][28] 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
Nearest Neighbor Search solutions like HNSW use small-world networks to efficiently find the information in large item corpuses.[30][31]
Small-world neural networks in the brain
Both anatomical connections in the brain[32] and the synchronization networks of cortical neurons[33] exhibit small-world topology.
Structural and functional connectivity in the brain has also been found to reflect the small-world topology of short path length and high clustering.[34] The network structure has been found in the mammalian cortex across species as well as in large scale imaging studies in humans.[35] Advances in connectomics and network neuroscience, have found the small-worldness of neural networks to be associated with efficient communication.[36]
In neural networks, short pathlength between nodes and high clustering at network hubs supports efficient communication between brain regions at the lowest energetic cost.[36] The brain is constantly processing and adapting to new information and small-world network model supports the intense communication demands of neural networks.[37] High clustering of nodes forms local networks which are often functionally related. Short path length between these hubs supports efficient global communication.[38] This balance enables the efficiency of the global network while simultaneously equipping the brain to handle disruptions and maintain homeostasis, due to local subsystems being isolated from the global network.[39] Loss of small-world network structure has been found to indicate changes in cognition and increased risk of psychological disorders.[9]
In addition to characterizing whole-brain functional and structural connectivity, specific neural systems, such as the visual system, exhibit small-world network properties.[6]
A small-world network of neurons can exhibit
See also
- Barabási–Albert model – Scale-free network generation algorithm
- Climate as complex networks – Conceptual model to generate insight into climate science
- Dual-phase evolution – Process that drives self-organization within complex adaptive systems
- Dunbar's number – Suggested cognitive limit important in sociology and anthropology
- Erdős number – Closeness of someone's association with mathematician Paul Erdős
- Erdős–Rényi (ER) model – Two closely related models for generating random graphs
- Local World Evolving Network Models
- Percolation theory – Mathematical theory on behavior of connected clusters in a random graph
- Network science – Academic field - mathematical theory of networks
- Scale-free network – Network whose degree distribution follows a power law
- Six degrees of Kevin Bacon – Parlor game on degrees of separation
- Small-world experiment – Experiments examining the average path length for social networks
- Social network – Social structure made up of a set of social actors
- Watts–Strogatz model – Method of generating random small-world graphs
- Network on a chip – Electronic communication subsystem on an integrated circuit – systems on chip modeled on small-world networks
- Zachary's karate club
References
- ^ Downey, Allen B. (2016). "3". Think Complexity (PDF). Needham, Massachusetts: Green Tea Press. p. 27.
- S2CID 4429113.
- OCLC 895661009.
- S2CID 4429113.
- S2CID 119398712.
- ^ PMID 16615219.
- PMID 18446219.
- ^ PMID 22432451.
- ^ S2CID 3844585.
- doi:10.14359/7189.
- ^ Senekal BA (December 2015). "'n Kwantifisering van kleinwêreldsheid in Afrikaanse kultuurnetwerke in vergelyking met ander komplekse netwerke: natuurwetenskappe" [A quantification of small worlds in African cultural networks compared to other complex networks: natural sciences.]. 'n Joernaal vir die Geesteswetenskappe, Natuurwetenskappe, Regte en Godsdienswetenskappe (in Afrikaans). 12 (3). Litnet Akademies: 665–88.
- ^ Senekal B, Kotzé E (2017). "Die statistiese eienskappe van geskrewe Afrikaans as'n komplekse netwerk" [The statistical properties of written Afrikaans as a complex network]. 'n Joernaal vir die Geesteswetenskappe, Natuurwetenskappe, Regte en Godsdienswetenskappe (in Afrikaans). 14 (1). Litnet Akademies: 27–59.
- PMID 15193308.
- PMID 14968131.
- ^ Einstein and Alexander the Great lived 2202 years apart. Assuming an age difference of 70 years between any two connected people in the chain that connects the two, this would necessitate at least 32 connections between Einstein and Alexander the Great.
- S2CID 119109068.
- S2CID 38158445.
- .
- ^ A Ramezanpour, V Karimipour, A Mashaghi, Generating correlated networks from uncorrelated ones. Physical Review E 67(4 Pt 2):046107 (2003) doi: 10.1103/PhysRevE.67.046107
- ].
- ^ PMID 11005838.
- S2CID 10508339.
- ^ OCLC 168716646.
- ^ Finnegan, William "Affinity Groups and the Movement Against Corporate Globalization"
- S2CID 118655139.(2001)
- .
- ^ Hillard R, McClowry S, Somich B. "Small Worlds Data Transformation Measure". MIKE2.0, the open source methodology for Information Development. Archived from the original on 2015-09-12. Retrieved 2012-01-05.
- ISBN 978-0-470-62577-4.
- ^ Sandberg O (2005). Searching in a Small World (PDF) (Ph.D. thesis). Göteborg, Sweden: Chalmers University of Technology and Göteborg University. Archived (PDF) from the original on 2012-03-16. Retrieved 2013-12-12.
- ^ "Hierarchical Navigable Small Worlds (HNSW) | Pinecone". www.pinecone.io. Retrieved 2024-03-05.
- ^ "Understanding Hierarchical Navigable Small Worlds (HNSW)". DataStax. Retrieved 2024-03-05.
- S2CID 2855338.
- PMID 18400792.
- PMID 27655008.
- S2CID 14757568.
- ^ S2CID 16174225.
- PMID 18784304.
- PMID 24223147.
- PMID 24063566.
- ^ Cohen P (26 May 2004). "Small world networks key to memory". New Scientist.
- from the original on 2016-09-14. Retrieved 2006-03-06.
- S2CID 35927833.
Further reading
Books
- Buchanan M (2003). Nexus: Small Worlds and the Groundbreaking Theory of Networks. Norton, W. W. & Company, Inc. ISBN 978-0-393-32442-6.
- Dorogovtsev SN, Mendes JF (2003). Evolution of Networks: from biological networks to the Internet and WWW. Oxford University Press. ISBN 978-0-19-851590-6.
- Watts DJ (1999). Small Worlds: The Dynamics of Networks Between Order and Randomness. Princeton University Press. ISBN 978-0-691-00541-6.
- Fowler JH (2005). "Turnout in a Small World". In Zuckerman A (ed.). Social Logic of Politics. Temple University Press. pp. 269–287.
Journal articles
- Albert R, Barabási AL (2002). "Statistical mechanics of complex networks". Rev. Mod. Phys. 74 (1): 47–97. S2CID 60545.
- Barabasi AL, Albert R (October 1999). "Emergence of scaling in random networks". Science. 286 (5439): 509–12. S2CID 524106.
- Barthelemy M, Amaral LA (1999). "Small-world networks: Evidence for a crossover picture". Phys. Rev. Lett. 82 (15): 3180–3183. S2CID 119398712.
- Dorogovtsev SN, Mendes JF (2000). "Exactly solvable analogy of small-world networks". Europhys. Lett. 50 (1): 1–7. S2CID 11334862.
- Milgram S (1967). "The Small World Problem". Psychology Today. 1 (1): 60–67.
- Newman M (2003). "The Structure and Function of Complex Networks". SIAM Review. 45 (2): 167–256.
- Ravid D,
External links
- Dynamic Proximity Networks by Seth J. Chandler, The Wolfram Demonstrations Project.
- Small-World Networks entry on Scholarpedia (by Mason A. Porter)