Renormalization Group Analysis of the Small-World Network Model

By Mark Newman, Duncan J. Watts. 1999

We study the small-world network model, which mimics the transition between regular-lattice and random-lattice behavior in social networks of increasing size. We contend that the model displays a normal continuous phase transition with a divergent correlation length as the degree of randomness tends to zero. We propose a real-space renormalization group transformation for the model and demonstrate that the transformation is exact in the limit of large system size. We use this result to calculate the exact value of the single critical exponent for the system, and to derive the scaling form for the average number of "degrees of separation" between two nodes on the network as a function of the three independent variables. We confirm our results by extensive numerical simulation. Appears in Phys. Lett. A 263, 341-346 (1999).

Subfields: Graph Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Graph Learning

Citations in the corpus

Neural Execution Engines: Learning to Execute Subroutines (2020, background): “• Newman–Watts–Strogatz random graphs [20]: First create a ring of n nodes, where each node is connected to its k nearest neighbors (or k − 1 neighbors if k is odd).”
Exact controllability of complex networks (2013, background): “For example, we find that for random [43] and small-world networks [6, 44] with identical link weights, the measure of controllability is a non-monotonic function of link density with largest controllability occurring in the intermediate region.”
Evolution of networks (2001, background): “x† describing the crossover between two limiting regimes [133, 134, 135, 139, 140, 142, 143, 144, 145, 146].”
The Structure and Function of Complex Networks (2003, methodology): “In Section VI we look at the “small-world model” of Watts and Strogatz [416] and its generalizations.”
Models of the Small World (2000, methodology): “After Newman and Watts (1999b) and Newman et al. (2000). see that it takes about 10 shortcuts to reduce the average vertex vertex distance by a factor of two, and 100 to reduce it by a factor of ten.”
An analysis of the fixation probability of a mutant on special classes of non-directed graphs (2008, methodology): “This has the benet of extending to larger more complex graphical systems, such as the small world networks of Bollobas & Chung (1988) (see also Durrett (2007), Newman et al. (2006), Newman & Watts (1999) and Watts & Strogatz (1998)).”
Complex networks: small-world, scale-free and beyond (2003, unknown): “Aiming to describe a transition from a regular lattice to a random graph, Watts and Strogatz [5] introduced an interesting small-world network model, referred to as WS small-world model.”
Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality. (2000, methodology): “…modeling techniques [4,5,6], exact solutions [7,8,9,10,11,12], Monte Carlo simulation [13,14,15,16], scaling and renormalization group methods [14,15,16], mean-ﬁeld theory [17,18], percolation theory [19,20,21], the replica method [22], generating functions [19,21,23], and a host of other…”
Evolutionary Dynamics on Graphs - the Effect of Graph Structure and Initial Placement on Mutant Spread (2011, methodology): “The introduced approximation methods have the benefit of extending to larger more complex graphical systems, such as the small world networks of (Bollobás and Chung, 1988; Durrett, 2007; Newman, Barabási and Watts, 2006; Newman and Watts, 1999; Watts and Strogatz, 1998).”
Characterizing the synchronizability of small-world dynamical networks (2004, background): “According to the stability theory of linear time-varying systems [18], if , then, the linear time-varying system (17) is exponentially stable about its zero solution.”