Resistance distance distribution in large sparse random graphs

Abstract

We consider an Erdos-Renyi random graph consisting of N vertices connected by randomly and independently drawing an edge between every pair of them with probability c/N so that at N->infinity one obtains a graph of finite mean degree c. In this regime, we study the distribution of resistance distances between the vertices of this graph and develop an auxiliary field representation for this quantity in the spirit of statistical field theory. Using this representation, a saddle point evaluation of the resistance distance distribution is possible at N->infinity in terms of an 1/c expansion. The leading order of this expansion captures the results of numerical simulations very well down to rather small values of c; for example, it recovers the empirical distribution at c=4 or 6 with an overlap of around 90%. At large values of c, the distribution tends to a Gaussian of mean 2/c and standard deviation sqrt{2/c^3}. At small values of c, the distribution is skewed toward larger values, as captured by our saddle point analysis, and many fine features appear in addition to the main peak, including subleading peaks that can be traced back to resistance distances between vertices of specific low degrees and the rest of the graph. We develop a more refined saddle point scheme that extracts the corresponding degree-differentiated resistance distance distributions. We then use this approach to recover analytically the most apparent of the subleading peaks that originates from vertices of degree 1. Rather intuitively, this subleading peak turns out to be a copy of the main peak, shifted by one unit of resistance distance and scaled down by the probability for a vertex to have degree 1. We comment on a possible lack of smoothness in the true N->infinity distribution suggested by the numerics.

arXiv commentv2: expanded version, accepted for publication in J. Stat. Mech

References in corpus (23)

• Quantum Field Theory in the Large N Limit: a review
• Damage and fluctuations induce loops in optimal transport networks
• Theory of resistor networks: The two-point resistance
• Metrics for Graph Comparison: A Practitioner's Guide
• Solution of the 2-star model of a network
• Geodesic Distance in Planar Graphs
• Spectra of Euclidean Random Matrices
• Random incidence matrices: moments of the spectral density
• Finite size correction to the spectrum of regular random graphs: an analytical solution
• Distribution of diameters for Erdös-Rényi random graphs
• Analytical results for the distribution of shortest path lengths in random networks
• Distance distribution in configuration model networks
• The distribution of shortest path lengths in subcritical Erdős-Rényi networks
• Heterogeneous micro-structure of percolation in sparse networks
• Fluctuation spectra of large random dynamical systems reveal hidden structure in ecological networks
• On Random Matrix Averages Involving Half-Integer Powers of GOE Characteristic Polynomials
• The two-star model: exact solution in the sparse regime and condensation transition
• Distribution networks achieve uniform perfusion through geometric self-organization
• Random walk hitting times and effective resistance in sparsely connected Erdős-Rényi random graphs
• Concentration of the Kirchhoff index for Erdos-Renyi graphs
• Analytic solution of the two-star model with correlated degrees
• Phases of Small Worlds: A Mean Field Formulation
• Tradeoffs between energy efficiency and mechanical response in fluid flow networks