Laplacian spectra of complex networks and random walks on them: Are scale-free architectures really important?

Abstract

We study the Laplacian operator of an uncorrelated random network and, as an application, consider hopping processes (diffusion, random walks, signal propagation, etc.) on networks. We develop a strict approach to these problems. We derive an exact closed set of integral equations, which provide the averages of the Laplacian operator's resolvent. This enables us to describe the propagation of a signal and random walks on the network. We show that the determining parameter in this problem is the minimum degree $q_m$ of vertices in the network and that the high-degree part of the degree distribution is not that essential. The position of the lower edge of the Laplacian spectrum ${\lambda }_c$ appears to be the same as in the regular Bethe lattice with the coordination number $q_m$. Namely, ${\lambda }_c>0$ if $q_m>2$, and ${\lambda }_c=0$ if $q_m\le 2$. In both these cases the density of eigenvalues $\rho (\lambda )\to 0$ as $\lambda \to {\lambda }_c+0$, but the limiting behaviors near ${\lambda }_c$ are very different. In terms of a distance from a starting vertex, the hopping propagator is a steady moving Gaussian, broadening with time. This picture qualitatively coincides with that for a regular Bethe lattice. Our analytical results include the spectral density $\rho (\lambda )$ near ${\lambda }_c$ and the long-time asymptotics of the autocorrelator and the propagator.

25 pages, 4 figures

References in corpus (6)

• Delays, connection topology, and synchronization of coupled chaotic maps
• Synchronization processes in complex networks
• Localization Transition of Biased Random Walks on Random Networks
• Bounding network spectra for network design
• Preferential Behaviour and Scaling in Diffusive Dynamics on Networks
• Constrained spin dynamics description of random walks on hierarchical scale-free networks

Cited by in corpus (21)

• Turing patterns in network-organized activator-inhibitor systems
• Random walks and search in time-varying networks
• Random walks on weighted networks
• Spectral and Dynamical Properties in Classes of Sparse Networks with Mesoscopic Inhomogeneities
• Random walks on complex trees
• Collective Relaxation Dynamics of Small-World Networks
• Trapping in dendrimers and regular hyperbranched polymers
• The spectral dimension of simplicial complexes: a renormalization group theory
• Immunization Strategies Based on the Overlapping Nodes in Networks with Community Structure
• Pattern Formation on Networks with Reactions: A Continuous Time Random Walk Approach
• Scaling of mean first-passage time as efficiency measure of nodes sending information on scale-free Koch networks
• Equivalence of replica and cavity methods for computing spectra of sparse random matrices
• Origin of the hub spectral dimension in scale-free networks
• Localization transition, Lifschitz tails and rare-region effects in network models
• Multi-scale Laplacian community detection in heterogeneous networks
• Network evolution towards optimal dynamical performance
• Fast Algorithm for Relaxation Processes in Big-data Systems
• Giant component in a configuration-model power-law graph with a variable number of links
• Why lockdown : On the spread of SARS-CoV-2 in India, a network approach
• Exact Spectral Dimension of the Random Surface
• Statistics of remote regions of networks