Phases of Small Worlds: A Mean Field Formulation

Abstract

A network is said to have the properties of a small world if a suitably defined average distance between any two nodes is proportional to the logarithm of the number of nodes, $N$. In this paper, we present a novel derivation of the small-world property for Gilbert-Erdös-Renyi random networks. We employ a mean field approximation that permits the analytic derivation of the distribution of shortest paths that exhibits logarithmic scaling away from the phase transition, inferable via a suitably interpreted order parameter. We begin by framing the problem in generality with a formal generating functional for undirected weighted random graphs with arbitrary disorder, recovering the result that the free energy associated with an ensemble of Gilbert graphs corresponds to a system of non-interacting fermions identified with the edge states. We then present a mean field solution for this model and extend it to more general realizations of network randomness. For a two family class of stochastic block models that we refer to as dimorphic networks, which allow for links within the different families to be drawn from two independent discrete probability distributions, we find the mean field approximation maps onto a spin chain combinatorial problem and again yields useful approximate analytic expressions for mean path lengths. Dimorophic networks exhibit a richer phase structure, where distinct small world regimes separate in analogy to the spinodal decomposition of a fluid. We find that is it possible to induce small world behavior in sub-networks that by themselves would not be in the small-world regime.

arXiv comment21 pages, 3 appendices, 13 figures, version to appear in Journal of Statistical Physics

References in corpus (22)

• Emergence of scaling in random networks
• Random graphs with arbitrary degree distributions and their applications
• The spread of epidemic disease on networks
• Renormalization group analysis of the small-world network model
• Scale-Free Networks are Ultrasmall
• The statistical mechanics of networks
• Mean-field solution of the small-world network model
• The Statistical Physics of Real-World Networks
• Structure of shells in complex networks
• Metric structure of random networks
• Unbiased sampling of network ensembles
• Universal scaling of distances in complex networks
• Fractal Boundaries of Complex Networks
• Analytical results for the distribution of shortest path lengths in random networks
• Distance distribution in configuration model networks
• Revealing the Micro-Structure of the Giant Component in Random Graph Ensembles
• A simple, distance-dependent formulation of the Watts-Strogatz model for directed and undirected small-world networks
• The distribution of shortest path lengths in a class of node duplication network models
• The distribution of shortest path lengths in subcritical Erdős-Rényi networks
• Distribution of shortest cycle lengths in random networks
• Broadband Macroscopic Cortical Oscillations Emerge from Intrinsic Neuronal Response Failures
• Analytical results for the distribution of shortest path lengths in directed random networks that grow by node duplication

Cited by in corpus (3)

• The mean and variance of the distribution of shortest path lengths of random regular graphs
• The distribution of shortest path lengths on trees of a given size in subcritical Erdos-Renyi networks
• Resistance distance distribution in large sparse random graphs