Watts–Strogatz model

Last updated
Watts-Strogatz small-world model generated by igraph and visualized by Cytoscape 2.5. 100 nodes. Watts-Strogatz small-world model 100nodes.png
Watts–Strogatz small-world model generated by igraph and visualized by Cytoscape 2.5. 100 nodes.

The Watts–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. [1] The model also became known as the (Watts) beta model after Watts used to formulate it in his popular science book Six Degrees .

Random graph Graph generated by a random process

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 lies at the intersection between graph theory and probability theory. From a mathematical perspective, random graphs are used to answer questions about the properties of typical graphs. Its practical applications are found in all areas in which complex networks need to be modeled – a large number of random graph models are thus known, mirroring the diverse types of complex networks encountered in different areas. In a mathematical context, random graph refers almost exclusively to the Erdős–Rényi random graph model. In other contexts, any graph model may be referred to as a random graph.

Small-world network

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 distance L between two randomly chosen nodes grows proportionally to the logarithm of the number of nodes N in the network, that is:

Average path length is a concept in network topology that is defined as the average number of steps along the shortest paths for all possible pairs of network nodes. It is a measure of the efficiency of information or mass transport on a network.

Contents

Rationale for the model

The formal study of random graphs dates back to the work of Paul Erdős and Alfréd Rényi. [2] The graphs they considered, now known as the classical or Erdős–Rényi (ER) graphs, offer a simple and powerful model with many applications.

Paul Erdős Hungarian mathematician and freelancer

Paul Erdős was a renowned Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. He was known both for his social practice of mathematics and for his eccentric lifestyle. He devoted his waking hours to mathematics, even into his later years—indeed, his death came only hours after he solved a geometry problem at a conference in Warsaw.

Alfréd Rényi was a Hungarian mathematician who made contributions in combinatorics, graph theory, number theory but mostly in probability theory.

Erdős–Rényi model

In the mathematical field of graph theory, the Erdős–Rényi model is either of two closely related models for generating random graphs. They are named after mathematicians Paul Erdős and Alfréd Rényi, who first introduced one of the models in 1959, while Edgar Gilbert introduced the other model contemporaneously and independently of Erdős and Rényi. In the model of Erdős and Rényi, all graphs on a fixed vertex set with a fixed number of edges are equally likely; in the model introduced by Gilbert, each edge has a fixed probability of being present or absent, independently of the other edges. These models can be used in the probabilistic method to prove the existence of graphs satisfying various properties, or to provide a rigorous definition of what it means for a property to hold for almost all graphs.

However the ER graphs do not have two important properties observed in many real-world networks:

  1. They do not generate local clustering and triadic closures. Instead, because they have a constant, random, and independent probability of two nodes being connected, ER graphs have a low clustering coefficient.
  2. They do not account for the formation of hubs. Formally, the degree distribution of ER graphs converges to a Poisson distribution, rather than a power law observed in many real-world, scale-free networks. [3]

The Watts and Strogatz model was designed as the simplest possible model that addresses the first of the two limitations. It accounts for clustering while retaining the short average path lengths of the ER model. It does so by interpolating between a randomized structure close to ER graphs and a regular ring lattice. Consequently, the model is able to at least partially explain the "small-world" phenomena in a variety of networks, such as the power grid, neural network of C. elegans, networks of movie actors, or fat-metabolism communication in budding yeast. [4]

Lattice (group) subgroup of a real vector space or a Lie group

In geometry and group theory, a lattice in is a subgroup of the additive group which is isomorphic to the additive group , and which spans the real vector space . In other words, for any basis of , the subgroup of all linear combinations with integer coefficients of the basis vectors forms a lattice. A lattice may be viewed as a regular tiling of a space by a primitive cell.

<i>Caenorhabditis elegans</i> free-living species of nematode

Caenorhabditis elegans is a free-living, transparent nematode, about 1 mm in length, that lives in temperate soil environments. It is the type species of its genus. The name is a blend of the Greek caeno- (recent), rhabditis (rod-like) and Latin elegans (elegant). In 1900, Maupas initially named it Rhabditides elegans, Osche placed it in the subgenus Caenorhabditis in 1952, and in 1955, Dougherty raised Caenorhabditis to the status of genus.

Algorithm

Watts-Strogatz graph Watts strogatz.svg
Watts–Strogatz graph

Given the desired number of nodes , the mean degree (assumed to be an even integer), and a special parameter , satisfying and , the model constructs an undirected graph with nodes and edges in the following way:

Degree (graph theory) number of edges incident to a given vertex in a node-link graph

In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, and in a multigraph, loops are counted twice. The degree of a vertex is denoted or . The maximum degree of a graph G, denoted by Δ(G), and the minimum degree of a graph, denoted by δ(G), are the maximum and minimum degree of its vertices. In the multigraph on the right, the maximum degree is 5 and the minimum degree is 0. In a regular graph, all degrees are the same, and so we can speak of the degree of the graph. A complete graph is a special kind of regular graph where all vertices,p ,have the maximum degree, p-1. A complete graph is denoted with the form Kp where p is the number of vertices in the graph.

  1. Construct a regular ring lattice, a graph with nodes each connected to neighbors, on each side. That is, if the nodes are labeled , there is an edge if and only if
  2. For every node take every edge connecting to its rightmost neighbors, that is every edge with , and rewire it with probability . Rewiring is done by replacing with where is chosen uniformly at random from all possible nodes while avoiding self-loops () and link duplication (there is no edge with at this point in the algorithm).

Properties

The underlying lattice structure of the model produces a locally clustered network, while the randomly rewired links dramatically reduce the average path lengths. The algorithm introduces about of such non-lattice edges. Varying makes it possible to interpolate between a regular lattice () and a structure close to an Erdős–Rényi random graph with at . It does not approach the actual ER model since every node will be connected to at least other nodes.

The three properties of interest are the average path length, the clustering coefficient, and the degree distribution.

Average path length

For a ring lattice, the average path length is and scales linearly with the system size. In the limiting case of , the graph approaches a random graph with , while not actually converging to it. In the intermediate region , the average path length falls very rapidly with increasing , quickly approaching its limiting value.

Clustering coefficient

For the ring lattice the clustering coefficient [5] , and so tends to as grows, independently of the system size. [6] In the limiting case of the clustering coefficient is of the same order as the clustering coefficient for classical random graphs, and is thus inversely proportional to the system size. In the intermediate region the clustering coefficient remains quite close to its value for the regular lattice, and only falls at relatively high . This results in a region where the average path length falls rapidly, but the clustering coefficient does not, explaining the "small-world" phenomenon.

If we use the Barrat and Weigt [6] measure for clustering defined as the fraction between the average number of edges between the neighbors of a node and the average number of possible edges between these neighbors, or, alternatively,
then we get

Degree distribution

The degree distribution in the case of the ring lattice is just a Dirac delta function centered at . The degree distribution for can be written as, [6]

where is the number of edges that the node has or its degree. Here , and . The shape of the degree distribution is similar to that of a random graph and has a pronounced peak at and decays exponentially for large . The topology of the network is relatively homogeneous, meaning that all nodes are of similar degree.

Limitations

The major limitation of the model is that it produces an unrealistic degree distribution. In contrast, real networks are often scale-free networks inhomogeneous in degree, having hubs and a scale-free degree distribution. Such networks are better described in that respect by the preferential attachment family of models, such as the Barabási–Albert (BA) model. (On the other hand, the Barabási–Albert model fails to produce the high levels of clustering seen in real networks, a shortcoming not shared by the Watts and Strogatz model. Thus, neither the Watts and Strogatz model nor the Barabási–Albert model should be viewed as fully realistic.)

The Watts and Strogatz model also implies a fixed number of nodes and thus cannot be used to model network growth.

See also

Related Research Articles

Scale-free network network whose degree distribution follows a power law

A scale-free network is a network whose degree distribution follows a power law, at least asymptotically. That is, the fraction P(k) of nodes in the network having k connections to other nodes goes for large values of k as

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 characterised by a relatively high density of ties; this likelihood tends to be greater than the average probability of a tie randomly established between two nodes.

Complex network network with non-trivial topological features

In the context of network theory, a complex network is a graph (network) with non-trivial topological features—features that do not occur in simple networks such as lattices or random graphs but often occur in graphs modelling of real systems. The study of complex networks is a young and active area of scientific research inspired largely by the empirical study of real-world networks such as computer networks, technological networks, brain networks and social networks.

In network theory, a giant component is a connected component of a given random graph that contains a finite fraction of the entire graph's vertices.

Barabási–Albert model

The Barabási–Albert (BA) model is an algorithm for generating random scale-free networks using a preferential attachment mechanism. Several natural and human-made systems, including the Internet, the world wide web, citation networks, and some social networks are thought to be approximately scale-free and certainly contain few nodes with unusually high degree as compared to the other nodes of the network. The BA model tries to explain the existence of such nodes in real networks. The algorithm is named for its inventors Albert-László Barabási and Réka Albert and is a special case of a more general model called Price's model.

Bose–Einstein condensation (network theory) Occurrence in network theory

Bose–Einstein condensation in networks is a phase transition observed in complex networks that can be described by the Bianconi-Barabási model. This phase transition predicts a "winner-takes-all" phenomena in complex networks and can be mathematically mapped to the mathematical model explaining Bose–Einstein condensation in physics.

Assortativity, or assortative mixing is a preference for a network's nodes to attach to others that are similar in some way. Though the specific measure of similarity may vary, network theorists often examine assortativity in terms of a node's degree. The addition of this characteristic to network models more closely approximates the behaviors of many real world networks.

Network science academic field

Network science is an academic field which studies complex networks such as telecommunication networks, computer networks, biological networks, cognitive and semantic networks, and social networks, considering distinct elements or actors represented by nodes and the connections between the elements or actors as links. The field draws on theories and methods including graph theory from mathematics, statistical mechanics from physics, data mining and information visualization from computer science, inferential modeling from statistics, and social structure from sociology. The United States National Research Council defines network science as "the study of network representations of physical, biological, and social phenomena leading to predictive models of these phenomena."

Evolving networks

Evolving Networks are networks that change as a function of time. They are a natural extension of network science since almost all real world networks evolve over time, either by adding or removing nodes or links over time. Often all of these processes occur simultaneously, such as in social networks where people make and lose friends over time, thereby creating and destroying edges, and some people become part of new social networks or leave their networks, changing the nodes in the network. Evolving network concepts build on established network theory and are now being introduced into studying networks in many diverse fields.

In social network analysis, the co-stardom network represents the collaboration graph of film actors i.e. movie stars. The co-stardom network can be represented by an undirected graph of nodes and links. Nodes correspond to the movie star actors and two nodes are linked if they co-starred (performed) in the same movie. The links are un-directed, and can be weighted or not depending on the goals of study. If the number of times two actors appeared in a movie is needed, links are assigned weights. The co-stardom network can also be represented by a bipartite graph where nodes are of two types: actors and movies. And edges connect different types of nodes if they have a relationship. Initially the network was found to have a small-world property. Afterwards, it was discovered that it exhibits a scale-free (power-law) behavior.

Synchronization networks are also often known as "networks of coupled dynamical systems". Both of these refer to networks connecting oscillators, where oscillators are nodes that emit a signal with somewhat regular frequency, and are also capable of receiving a signal.

Hierarchical network model

Hierarchical network models are iterative algorithms for creating networks which are able to reproduce the unique properties of the scale-free topology and the high clustering of the nodes at the same time. These characteristics are widely observed in nature, from biology to language to some social networks.

Evolving networks are dynamic networks which change in time. In each period t there are new nodes and edges that join the network while the old ones disappear. Such dynamic behaviour is characteristic for most real-world networks, regardless of their range - global or local. However, networks differ not only in their range but also in their topological structure. It is possible to distinguish:

Robustness, the ability to withstand failures and perturbations, is a critical attribute of many complex systems including complex networks.

Hub (network science)

In network science, a hub is a node with a number of links that greatly exceeds the average. Emergence of hubs is a consequence of a scale-free property of networks. While hubs cannot be observed in a random network, they are expected to emerge in scale-free networks. The uprise of hubs in scale-free networks is associated with power-law distribution. Hubs have a significant impact on the network topology. Hubs can be found in many real networks, such as Brain Network or Internet.

Evolution of a random network is a dynamical process, usually leading to emergence of giant component accompanied with striking consequences on the network topology. To quantify this process, there is a need of inspection on how the size of the largest connected cluster within the network, , varies with . Networks change their topology as they evolve, undergoing phase transitions. Phase transitions are generally known from physics, where it occurs as matter changes state according to its thermal energy level, or when ferromagnetic properties emerge in some materials as they are cooling down. Such phase transitions take place in matter because it is a network of particles, and as such, rules of network phase transition directly apply to it. Phase transitions in networks happen as links are added to a network, meaning that having N nodes, in each time increment, a link is placed between a randomly chosen pair of them. The transformation from a set of disconnected nodes to a fully connected network is called the evolution of a network.

Configuration model

In network science, the configuration model is a method for generating random networks from given degree sequence. It is widely used as a reference model for real-life social networks, because it allows the user to incorporate arbitrary degree distributions.

References

  1. Watts, D. J.; Strogatz, S. H. (1998). "Collective dynamics of 'small-world' networks" (PDF). Nature. 393 (6684): 440–442. Bibcode:1998Natur.393..440W. doi:10.1038/30918. PMID   9623998.
  2. Erdos, P. (1960). "Publications Mathematicae 6, 290 (1959); P. Erdos, A. Renyi". Publ. Math. Inst. Hung. Acad. Sci. 5: 17.
  3. Ravasz, E. (30 August 2002). "Hierarchical Organization of Modularity in Metabolic Networks". Science. 297 (5586): 1551–1555. arXiv: cond-mat/0209244 Lock-green.svg. Bibcode:2002Sci...297.1551R. doi:10.1126/science.1073374.
  4. Al-Anzi, Bader; Arpp, Patrick; Gerges, Sherif; Ormerod, Christopher; Olsman, Noah; Zinn, Kai (2015). "Experimental and Computational Analysis of a Large Protein Network That Controls Fat Storage Reveals the Design Principles of a Signaling Network". PLOS Computational Biology. 11 (5): e1004264. Bibcode:2015PLSCB..11E4264A. doi:10.1371/journal.pcbi.1004264. PMC   4447291 Lock-green.svg. PMID   26020510.
  5. Albert, R., Barabási, A.-L. (2002). "Statistical mechanics of complex networks". Reviews of Modern Physics. 74 (1): 47–97. arXiv: cond-mat/0106096 Lock-green.svg. Bibcode:2002RvMP...74...47A. doi:10.1103/RevModPhys.74.47.
  6. 1 2 3 Barrat, A.; Weigt, M. (2000). "On the properties of small-world network models" (PDF). European Physical Journal B. 13 (3): 547–560. arXiv: cond-mat/9903411 Lock-green.svg. doi:10.1007/s100510050067 . Retrieved 2008-02-26.