Small-world network
Encyclopedia
In mathematics
, physics
and sociology
, 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:
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 graph
s 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
(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 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
; Barmpoutis and Murray, 2010). Braunstein et al found that for weighted ER networks where the weights have a very broad distribution, the optimal path scales becomes significantly longer as
L~N1/3.
, 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
). 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. Networks with power law degree distribution are also known as scale-free network
s. Graphs of very different topology qualify as small-world networks as long as they satisfy the two definitional requirements above.
Cohen and Havlin
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~LogLog N.
,
voter networks, telephone call graphs, and social influence networks.
Networks of connected proteins
have small world properties such as power-law obeying degree distributions. Similarly transcriptional network
s, in which the nodes are gene
s, and they are linked if one gene has an up or down-regulatory genetic influence on the other, have small world network properties.
For 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 favour of finding small-world networks.
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. 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, 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.
.
Small-world networks can also be introduced with time-delay, which will not only produces fractals but also
chaos under the right conditions, or transition to chaos in dynamics networks.
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., 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
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. 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. 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.
of the phenomenon in the earth sciences.
A small-world network of neurons can exhibit short-term memory
. A computer model developed by Solla et al.
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.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, physics
Physics
Physics is a natural science that involves the study of matter and its motion through spacetime, along with related concepts such as energy and force. More broadly, it is the general analysis of nature, conducted in order to understand how the universe behaves.Physics is one of the oldest academic...
and sociology
Sociology
Sociology is the study of society. It is a social science—a term with which it is sometimes synonymous—which uses various methods of empirical investigation and critical analysis to develop a body of knowledge about human social activity...
, a small-world network is a type of mathematical graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
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:
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
Internet
The Internet is a global system of interconnected computer networks that use the standard Internet protocol suite to serve billions of users worldwide...
, wikis such as Wikipedia, and gene networks
Gene regulatory network
A gene regulatory network or genetic regulatory network is a collection of DNA segments in a cell whichinteract with each other indirectly and with other substances in the cell, thereby governing the rates at which genes in the network are transcribed into mRNA.In general, each mRNA molecule goes...
all exhibit small-world network characteristics.
A certain category of small-world networks were identified as a class of random graph
Random graph
In mathematics, a random graph is a graph that is generated by some random process. The theory of random graphs lies at the intersection between graph theory and probability theory, and studies the properties of typical random graphs.-Random graph models:...
s by Duncan Watts
Duncan J. Watts
Duncan J. Watts is an Australian researcher and a principal research scientist at Yahoo! Research, where he directs the Human Social Dynamics group. He is also a past external faculty member of the Santa Fe Institute and a former professor of sociology at Columbia University, where he headed the...
and Steven Strogatz
Steven Strogatz
Steven Henry Strogatz is an American mathematician and the Jacob Gould Schurman Professor of Applied Mathematics at Cornell University...
in 1998. They noted that graphs could be classified according to two independent structural features, namely the clustering coefficient
Clustering coefficient
In graph theory, a clustering coefficient is a measure of degree to which nodes in a graph tend to cluster together. Evidence suggests that in most real-world networks, and in particular social networks, nodes tend to create tightly knit groups characterised by a relatively high density of ties...
, and average node-to-node distance
Distance (graph theory)
In the mathematical field of graph theory, the distance between two vertices in a graph is the number of edges in a shortest path connecting them. This is also known as the geodesic distance...
(also known as average shortest path length). Purely random graphs, built according to the Erdős–Rényi (ER) model
Erdos–Rényi model
In graph theory, the Erdős–Rényi model, named for Paul Erdős and Alfréd Rényi, is either of two models for generating random graphs, including one that sets an edge between each pair of nodes with equal probability, independently of the other edges...
, 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
Watts and Strogatz model
The Watts and Strogatz model is a random graph generation model that produces graphs with small-world properties, including short average path lengths and high clustering. It was proposed by Duncan J. Watts and Steven Strogatz in their joint 1998 Nature paper...
, 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
José Fernando Ferreira Mendes
José F.F. Mendes is a Portuguese physicist and professor of physics at University of Aveiro .Was Head of Physics Department from December 2004 to February 2010...
; Barmpoutis and Murray, 2010). Braunstein et al found that for weighted ER networks where the weights have a very broad distribution, the optimal path scales becomes significantly longer as
L~N1/3.
Properties of small-world networks
Small-world networks tend to contain cliquesClique (graph theory)
In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...
, 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
Degree (graph theory)
In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted \deg. The maximum degree of a graph G, denoted by Δ, and the minimum degree of a graph, denoted by δ, are the maximum and minimum 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
Airline hub
An airline hub is an airport that an airline uses as a transfer point to get passengers to their intended destination. It is part of a hub and spoke model, where travelers moving between airports not served by direct flights change planes en route to their destinations...
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
Heavy-tailed distribution
In probability theory, heavy-tailed distributions are probability distributions whose tails are not exponentially bounded: that is, they have heavier tails than the exponential distribution...
distribution. Specifically, if a network has a degree-distribution which can be fit
Goodness of fit
The goodness of fit of a statistical model describes how well it fits a set of observations. Measures of goodness of fit typically summarize the discrepancy between observed values and the values expected under the model in question. Such measures can be used in statistical hypothesis testing, e.g...
with a power law distribution, it is taken as a sign that the network is small-world. Networks with power law degree distribution are also known as scale-free network
Scale-free network
A scale-free network is a network whose degree distribution follows a power law, at least asymptotically. That is, the fraction P of nodes in the network having k connections to other nodes goes for large values of k as...
s. Graphs of very different topology qualify as small-world networks as long as they satisfy the two definitional requirements above.
Cohen and Havlin
Shlomo Havlin
Shlomo Havlin is a Professor in the Department of Physics at Bar-Ilan University, Ramat-Gan, Israel. He served as President of the Israel Physical Society , Dean of Faculty of Exact Sciences , Chairman, Department of Physics .-Biography:Professor Shlomo Havlin was born in Jerusalem, Israel...
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~LogLog N.
Examples of small-world networks
Small-world properties are found in many real-world phenomena, including road maps, food chains, electric power grids, metabolite processing networks, networks of brain neuronsNeural Networks
Neural Networks is the official journal of the three oldest societies dedicated to research in neural networks: International Neural Network Society, European Neural Network Society and Japanese Neural Network Society, published by Elsevier...
,
voter networks, telephone call graphs, and social influence networks.
Networks of connected proteins
Protein-protein interaction
Protein–protein interactions occur when two or more proteins bind together, often to carry out their biological function. Many of the most important molecular processes in the cell such as DNA replication are carried out by large molecular machines that are built from a large number of protein...
have small world properties such as power-law obeying degree distributions. Similarly transcriptional network
Transcriptional regulation
Transcriptional regulation is the change in gene expression levels by altering transcription rates. -Regulation of transcription:Regulation of transcription controls when transcription occurs and how much RNA is created...
s, in which the nodes are gene
Gene
A gene is a molecular unit of heredity of a living organism. It is a name given to some stretches of DNA and RNA that code for a type of protein or for an RNA chain that has a function in the organism. Living beings depend on genes, as they specify all proteins and functional RNA chains...
s, and they are linked if one gene has an up or down-regulatory genetic influence on the other, have small world network properties.
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.For example, the famous theory of "six degrees of separation
Six degrees of separation
Six degrees of separation refers to the idea that everyone is on average approximately six steps away, by way of introduction, from any other person on Earth, so that a chain of, "a friend of a friend" statements can be made, on average, to connect any two people in six steps or fewer...
" between people tacitly presumes that the domain of discourse
Domain of discourse
In the formal sciences, the domain of discourse, also called the universe of discourse , is the set of entities over which certain variables of interest in some formal treatment may range...
is the set of people alive at any one time. The number of degrees of separation between Albert Einstein
Albert Einstein
Albert Einstein was a German-born theoretical physicist who developed the theory of general relativity, effecting a revolution in physics. For this achievement, Einstein is often regarded as the father of modern physics and one of the most prolific intellects in human history...
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 favour of finding small-world networks.
Network robustness
It is hypothesized by some researchers such as BarabásiAlbert-Laszlo Barabasi
Albert-László Barabási is a physicist, best known for his work in the research of network theory. He is the former Emil T...
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
Mutation
In molecular biology and genetics, mutations are changes in a genomic sequence: the DNA sequence of a cell's genome or the DNA or RNA sequence of a virus. They can be defined as sudden and spontaneous changes in the cell. Mutations are caused by radiation, viruses, transposons and mutagenic...
or viral infection
Virus
A virus is a small infectious agent that can replicate only inside the living cells of organisms. Viruses infect all types of organisms, from animals and plants to bacteria and archaea...
.
In a power law
Power law
A power law is a special kind of mathematical relationship between two quantities. When the frequency of an event varies as a power of some attribute of that event , the frequency is said to follow a power law. For instance, the number of cities having a certain population size is found to vary...
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
Clustering coefficient
In graph theory, a clustering coefficient is a measure of degree to which nodes in a graph tend to cluster together. Evidence suggests that in most real-world networks, and in particular social networks, nodes tend to create tightly knit groups characterised by a relatively high density of ties...
). This follows from the fact that most shortest paths between nodes flow through hubs
Spoke-hub distribution paradigm
The hub-and-spoke distribution paradigm is a system of connections arranged like a chariot wheel, in which all traffic moves along spokes connected to the hub at the center...
, 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
Spoke-hub distribution paradigm
The hub-and-spoke distribution paradigm is a system of connections arranged like a chariot wheel, in which all traffic moves along spokes connected to the hub at the center...
, the probability of deleting an important node is very low. For example, if the small airport in Sun Valley, Idaho
Sun Valley, Idaho
Sun Valley is a resort city in Blaine County in the central part of the U.S. state of Idaho, adjacent to the city of Ketchum, lying within the greater Wood River valley. Tourists from around the world enjoy its skiing, hiking, ice skating, trail riding, tennis, and cycling. The population was 1,427...
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. 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, such as Chicago's O'Hare airport
O'Hare International Airport
Chicago O'Hare International Airport , also known as O'Hare Airport, O'Hare Field, Chicago Airport, Chicago International Airport, or simply O'Hare, is a major airport located in the northwestern-most corner of Chicago, Illinois, United States, northwest of the Chicago Loop...
, 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
P53
p53 , is a tumor suppressor protein that in humans is encoded by the TP53 gene. p53 is crucial in multicellular organisms, where it regulates the cell cycle and, thus, functions as a tumor suppressor that is involved in preventing cancer...
, 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 mechanismWatts and Strogatz model
The Watts and Strogatz model is a random graph generation model that produces graphs with small-world properties, including short average path lengths and high clustering. It was proposed by Duncan J. Watts and Steven Strogatz in their joint 1998 Nature paper...
.
Small-world networks can also be introduced with time-delay, which will not only produces fractals but also
chaos under the right conditions, or transition to chaos in dynamics networks.
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
Distance (graph theory)
In the mathematical field of graph theory, the distance between two vertices in a graph is the number of edges in a shortest path connecting them. This is also known as the geodesic distance...
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., 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
Diffusion-limited aggregation
Diffusion-limited aggregation is the process whereby particles undergoing a random walk due to Brownian motion cluster together to form aggregates of such particles. This theory, proposed by Witten and Sander in 1981, is applicable to aggregation in any system where diffusion is the primary means...
, pattern formation
Pattern formation
The science of pattern formation deals with the visible, orderly outcomes of self-organisation and the common principles behind similar patterns....
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.The small world network model is directly applicable to affinity group
Affinity group
An Affinity group is usually a small group of activists who work together on direct action.Affinity groups are organized in a non-hierarchical manner, usually using consensus decision making, and are often made up of trusted friends...
theory represented in sociological arguments by William Finnegan
William Finnegan
William Finnegan is a staff writer at The New Yorker and well-known author of works of international journalism. He has specially addressed issues of racism and conflict in Southern Africa and politics in Mexico and South America, as well as poverty among youth in the United States, and is...
. 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. Clay Shirky
Clay Shirky
Clay Shirky is an American writer, consultant and teacher on the social and economic effects of Internet technologies. He has a joint appointment at New York University as a Distinguished Writer in Residence at the Arthur L. Carter Journalism Institute and Assistant Arts Professor in the New...
argues that the larger the social network created through small world networking, the more valuable the nodes of high connectivity within the network. 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. The seismic network in the Southern California region may be a small-world network. The examples above occur on very different spatial scales, demonstrating the scale invarianceScale invariance
In physics and mathematics, scale invariance is a feature of objects or laws that do not change if scales of length, energy, or other variables, are multiplied by a common factor...
of the phenomenon in the earth sciences.
Small-world neural networks in the brain
Both, anatomical connections in the brain and the synchronization networks of cortical neurons exhibit small-world topology.A small-world network of neurons can exhibit short-term memory
Short-term memory
Short-term memory is the capacity for holding a small amount of information in mind in an active, readily available state for a short period of time. The duration of short-term memory is believed to be in the order of seconds. A commonly cited capacity is 7 ± 2 elements...
. A computer model developed by Solla et al.
had two stable states, a property (called bistability) thought to be important in memory
Memory
In psychology, memory is an organism's ability to store, retain, and recall information and experiences. Traditional studies of memory began in the fields of philosophy, including techniques of artificially enhancing 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.
Small World with a Distribution of Link length
The WS model include a uniform distribution of long range links. When the distribution of link length follow a power law distribution, the mean distance between two sites changes depending on the pwer of the distribution.See also
- Erdős–Rényi (ER) modelErdos–Rényi modelIn graph theory, the Erdős–Rényi model, named for Paul Erdős and Alfréd Rényi, is either of two models for generating random graphs, including one that sets an edge between each pair of nodes with equal probability, independently of the other edges...
- Erdős numberErdos numberThe Erdős number describes the "collaborative distance" between a person and mathematician Paul Erdős, as measured by authorship of mathematical papers.The same principle has been proposed for other eminent persons in other fields.- Overview :...
- Scale-free networkScale-free networkA scale-free network is a network whose degree distribution follows a power law, at least asymptotically. That is, the fraction P of nodes in the network having k connections to other nodes goes for large values of k as...
- Six degrees of Kevin BaconSix Degrees of Kevin BaconSix Degrees of Kevin Bacon is a trivia game based on the concept of the small world phenomenon and rests on the assumption that any individual involved in the Hollywood, California film industry can be linked through his or her film roles to actor Kevin Bacon within six steps. The name of the game...
- Small world experimentSmall world experimentThe small world experiment comprised several experiments conducted by Stanley Milgram and other researchers examining the average path length for social networks of people in the United States. The research was groundbreaking in that it suggested that human society is a small world type network...
- Social networkSocial networkA social network is a social structure made up of individuals called "nodes", which are tied by one or more specific types of interdependency, such as friendship, kinship, common interest, financial exchange, dislike, sexual relationships, or relationships of beliefs, knowledge or prestige.Social...
- Watts and Strogatz ModelWatts and Strogatz modelThe Watts and Strogatz model is a random graph generation model that produces graphs with small-world properties, including short average path lengths and high clustering. It was proposed by Duncan J. Watts and Steven Strogatz in their joint 1998 Nature paper...
Books
- Fowler, JHJames H. FowlerJames H. Fowler is an American social scientist specializing in social networks, cooperation, political participation, and genopolitics...
. (2005) "Turnout in a Small World," in Alan Zuckerman, ed., Social Logic of Politics, Temple University Press, 269-287
Journal articles
pdf http://firstmonday.org/issues/issue9_9/ravid/index.htmlExternal links
- Dynamic Proximity Networks by Seth J. Chandler, The Wolfram Demonstrations Project.