![Small-world-network-example](https://upload.wikimedia.org/wikipedia/commons/3/37/Small-world-network-example.png)
A small-world network is a type of
mathematical graph in which most nodes are not neighbors of one another, but the neighbors of any given node are likely to be neighbors of each other and most nodes can be reached from every other node by a small number of hops or steps. Specifically, a small-world network is defined to be a network where the
typical
Typical may refer to:
* ''Typical'' (album), Peter Hammill
* "Typical" (song), song by MuteMath
*"Typical", song by Frazier Chorus from ''Sue'', 1987
*''Typical'', story collection by Padgett Powell, 1991
See also
*''Typical Rick
''Typical R ...
distance ''L'' between two randomly chosen nodes (the number of steps required) grows proportionally to the
logarithm
In mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a number to the base is the exponent to which must be raised, to produce . For example, since , the ''logarithm base'' 10 of ...
of the number of nodes ''N'' in the network, that is:
:
while the
global clustering coefficient is not small.
In the context of a social network, this results in the
small world phenomenon
The 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 suggeste ...
of strangers being linked by a short chain of
acquaintance
The concept of interpersonal relationship involves social associations, connections, or affiliations between two or more people. Interpersonal relationships vary in their degree of intimacy or self-disclosure, but also in their duration, in t ...
s. Many empirical graphs show the small-world effect, including
social networks
A social network is a social structure made up of a set of social actors (such as individuals or organizations), sets of dyadic ties, and other social interactions between actors. The social network perspective provides a set of methods for a ...
, wikis such as Wikipedia,
gene networks, and even the underlying architecture of the
Internet
The Internet (or internet) is the global system of interconnected computer networks that uses the Internet protocol suite (TCP/IP) to communicate between networks and devices. It is a '' network of networks'' that consists of private, pub ...
. It is the inspiration for many
network-on-chip architectures in contemporary
computer hardware.
A certain category of small-world networks were identified as a class of
random graph
In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs ...
s by
Duncan Watts
Duncan James Watts (born February 20, 1971) is a sociologist and a professor at the University of Pennsylvania. He was formerly a principal researcher at Microsoft Research in New York City, and is known for his work on small-world networks.
...
and
Steven Strogatz
Steven Henry Strogatz (), born August 13, 1959, is an American mathematician and the Jacob Gould Schurman Professor of Applied Mathematics at Cornell University.
He is known for his work on nonlinear systems, including contributions to the study o ...
in 1998. They noted that graphs could be classified according to two independent structural features, namely the
clustering coefficient
In graph theory, a clustering coefficient is a measure of the 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 ...
, and average node-to-node
distance
Distance is a numerical or occasionally qualitative measurement of how far apart objects or points are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria (e.g. "two counties over"). ...
(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. This work was followed by many studies, including exact results (Barrat and Weigt, 1999; Dorogovtsev and
Mendes
Mendes ( grc-gre, Μένδης, '' gen''.: ), the Greek name of the ancient Egyptian city of Djedet, also known in ancient Egypt as Per-Banebdjedet ("The Domain of the Ram Lord of Djedet") and Anpet, is known today as Tell El-Ruba ( ar, تل ا ...
; Barmpoutis and Murray, 2010).
Properties of small-world networks
Small-world networks tend to contain
cliques
A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...
, 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
In graph theory, a clustering coefficient is a measure of the 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 ...
. 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
A fat-tailed distribution is a probability distribution that exhibits a large skewness or kurtosis, relative to that of either a normal distribution or an exponential distribution. In common usage, the terms fat-tailed and heavy-tailed are someti ...
. 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.
:
:if
(
and
), network is small-world. However, this metric is known to perform poorly because it is heavily influenced by the network's size.
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
:
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 ''L''
''r'' 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
:
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'' ≈ ''L''
''r''.
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 brain neurons,
voter networks, telephone call graphs, and airport networks. Cultural networks and word
co-occurrence network
Co-occurrence network, sometimes referred to as a semantic network, is a method to analyze text that includes a graphic visualization of potential relationships between people, organizations, concepts, biological organisms like bacteria or othe ...
s have also been shown to be small-world networks.
Networks of
connected proteins have small world properties such as power-law obeying degree distributions. Similarly
transcriptional networks, in which the nodes are
gene
In biology, the word gene (from , ; "... Wilhelm Johannsen coined the word gene to describe the Mendelian units of heredity..." meaning ''generation'' or ''birth'' or ''gender'') can have several different meanings. The Mendelian gene is a b ...
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
In another example, the famous theory of "
six degrees of separation
Six degrees of separation is the idea that all people are six or fewer social connections away from each other. As a result, a chain of "friend of a friend" statements can be made to connect any two people in a maximum of six steps. It is also k ...
" 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
Albert Einstein ( ; ; 14 March 1879 – 18 April 1955) was a German-born theoretical physicist, widely acknowledged to be one of the greatest and most influential physicists of all time. Einstein is best known for developing the theory ...
and
Alexander the Great
Alexander III of Macedon ( grc, Ἀλέξανδρος, Alexandros; 20/21 July 356 BC – 10/11 June 323 BC), commonly known as Alexander the Great, was a king of the ancient Greek kingdom of Macedon. He succeeded his father Philip II to ...
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
In biology, a mutation is an alteration in the nucleic acid sequence of the genome of an organism, virus, or extrachromosomal DNA. Viral genomes contain either DNA or RNA. Mutations result from errors during DNA replication, DNA or viral repl ...
or
viral infection
A viral disease (or viral infection) occurs when an organism's body is invaded by pathogenic viruses, and infectious virus particles (virions) attach to and enter susceptible cells.
Structural Characteristics
Basic structural characteristics, ...
.
In a small world network with a degree distribution following a
power-law, deletion of a random node rarely causes a dramatic increase in
mean-shortest path length (or a dramatic decrease in the
clustering coefficient
In graph theory, a clustering coefficient is a measure of the 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 ...
). 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
Chicago O'Hare International Airport , sometimes referred to as, Chicago O'Hare, or simply O'Hare, is the main international airport serving Chicago, Illinois, located on the city's Northwest Side, approximately northwest of the Loop busines ...
, 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.
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, which will not only produce 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
In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid fo ...
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
In graph theory, a Moore graph is a regular graph whose girth (the shortest cycle length) is more than twice its diameter (the distance between the farthest two vertices). If the degree of such a graph is and its diameter is , its girth must ...
.
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.
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.
For strong enough constraints, scale-free networks can even become single-scale networks whose connectivity distribution is characterized as fast decaying.
It was also shown analytically that scale-free networks are ultra-small, meaning that the distance scales according to
.
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.
The small world network model is directly applicable to
affinity group
An affinity group is a group formed around a shared interest or common goal, to which individuals formally or informally belong. Affinity groups are generally precluded from being under the aegis of any governmental agency, and their purposes m ...
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.
[Finnegan, William "Affinity Groups and the Movement Against Corporate Globalization"] Clay Shirky
Clay Shirky (born 1964) is an American writer, consultant and teacher on the social and economic effects of Internet technologies and journalism.
In 2017 he was appointed Vice Provost of Educational Technologies of New York University (NYU), aft ...
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
The 1999 Seattle WTO protests, sometimes referred to as the Battle of Seattle, were a series of protests surrounding the WTO Ministerial Conference of 1999, when members of the World Trade Organization (WTO) convened at the Washington State Co ...
.
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 invariance
In physics, mathematics and statistics, 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, and thus represent a universality.
The technical term ...
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. 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
Freenet is a peer-to-peer platform for censorship-resistant, anonymous communication. It uses a decentralized distributed data store to keep and deliver information, and has a suite of free software for publishing and communicating on the Web ...
peer-to-peer network has been shown to form a small-world network in simulation, 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
A brain is an organ that serves as the center of the nervous system in all vertebrate and most invertebrate animals. It is located in the head, usually close to the sensory organs for senses such as vision. It is the most complex organ in a ve ...
and the synchronization networks of cortical neurons 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. The network structure has been found in the mammalian cortex across species as well as in large scale imaging studies in humans. Advances in
connectomics
Connectomics is the production and study of connectomes: comprehensive maps of connections within an organism's nervous system. More generally, it can be thought of as the study of neuronal wiring diagrams with a focus on how structural connectivi ...
and
network neuroscience
Network, networking and networked may refer to:
Science and technology
* Network theory, the study of graphs as a representation of relations between discrete objects
* Network science, an academic field that studies complex networks
Mathematics
...
, have found the small-worldness of neural networks to be associated with efficient communication.
In neural networks, short pathlength between nodes and high clustering at network hubs supports efficient communication between brain regions at the lowest energetic cost.
The brain is constantly processing and adapting to new information and small-world network model supports the intense communication demands of neural networks. High clustering of nodes forms local networks which are often functionally related. Short path length between these hubs supports efficient global communication. 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.
Loss of small-world network structure has been found to indicate changes in cognition and increased risk of psychological disorders.
In addition to characterizing whole-brain functional and structural connectivity, specific neural systems, such as the visual system, exhibit small-world network properties.
A small-world network of neurons can exhibit
short-term memory. A computer model developed by
Sara Solla
Sara A. Solla is an Argentine-American physicist and neuroscientist whose research applies ideas from statistical mechanics to problems involving neural networks, machine learning, and neuroscience. She is a professor of physics and of physiology ...
had two stable states, a property (called
bistability) thought to be important in
memory
Memory is the faculty of the mind by which data or information is encoded, stored, and retrieved when needed. It is the retention of information over time for the purpose of influencing future action. If past events could not be remembered ...
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). Small world neuronal networks have also been used as models to understand
seizures
An epileptic seizure, informally known as a seizure, is a period of symptoms due to abnormally excessive or synchronous neuronal activity in the brain. Outward effects vary from uncontrolled shaking movements involving much of the body with l ...
.
See also
*
*
*
*
*
*
*
* - mathematical theory of networks
*
*
*
*
*
* –
systems on chip modeled on small-world networks
*
Zachary's karate club
References
Further reading
Books
*
*
*
*
Journal articles
*
*
*
*
*
*
pdf*
External links
Dynamic Proximity Networksby Seth J. Chandler,
The Wolfram Demonstrations Project
The Wolfram Demonstrations Project is an organized, open-source collection of small (or medium-size) interactive programs called Demonstrations, which are meant to visually and interactively represent ideas from a range of fields. It is hos ...
.
Small-World Networksentry on Scholarpedia (by Mason A. Porter)
{{Online social networking
Networks
Graph families
fr:Petit monde