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.

arXiv comment25 pages, 4 figures

References in corpus (15)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Error and attack tolerance of complex networks
• Random graphs with arbitrary degree distributions and their applications
• Evolution of networks
• Delays, connection topology, and synchronization of coupled chaotic maps
• Synchronization processes in complex networks
• Ensemble averageability in network spectra
• Metric structure of random 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
• Exact clesed form of the return probability on the Bethe lattice
• Random Electrical Networks on Complete Graphs II: Proofs

Cited by in corpus (61)

• Networks beyond pairwise interactions: structure and dynamics
• Random walks and diffusion on networks
• Random Walks on Multiplex Networks
• Turing patterns in network-organized activator-inhibitor systems
• Turing patterns on networks
• Entropy measures for complex networks: Toward an information theory of complex topologies
• Global mean first-passage times of random walks on complex networks
• Random walks and search in time-varying networks
• First passage time for random walks in heterogeneous networks
• Random walks on weighted networks
• Spectral and Dynamical Properties in Classes of Sparse Networks with Mesoscopic Inhomogeneities
• Centrality Measures for Networks with Community Structure
• Random Walks on deterministic Scale-Free networks: Exact results
• Eigenvalue Spectra of Modular Networks
• Relating Topological Determinants of Complex Networks to Their Spectral Properties: Structural and Dynamical Effects
• Random walks on complex trees
• Spectral dimensions of hierarchical scale-free networks with shortcuts
• Collective Relaxation Dynamics of Small-World Networks
• Trapping in dendrimers and regular hyperbranched polymers
• Asymptotic analysis of first passage time in complex networks
• The spectral dimension of simplicial complexes: a renormalization group theory
• Bloggers Behavior and Emergent Communities in Blog Space
• Networking - A Statistical Physics Perspective
• Immunization Strategies Based on the Overlapping Nodes in Networks with Community Structure
• Close or connected? Distance and connectivity effects on transport in networks
• Structure of Cell Networks Critically Determines Oscillation Regularity
• Spectra of sparse regular graphs with loops
• Exact Coupling Threshold for Structural Transition in Interconnected Networks
• Pattern Formation on Networks with Reactions: A Continuous Time Random Walk Approach
• Spectral Properties of Directed Random Networks with Modular Structure
• Spectral analysis of deformed random networks
• Localization and universality of eigenvectors in directed random graphs
• The higher-order spectrum of simplicial complexes: a renormalization group approach
• Origin and implications of zero degeneracy in networks spectra
• Equivalence of replica and cavity methods for computing spectra of sparse random matrices
• Scaling of mean first-passage time as efficiency measure of nodes sending information on scale-free Koch networks
• Spectral properties of hyperbolic nano-networks with tunable aggregation of simplexes
• Origin of the hub spectral dimension in scale-free networks
• Reactive random walkers on complex networks
• Localization transition, Lifschitz tails and rare-region effects in network models
• Jamming and Correlation Patterns in Traffic of Information on Sparse Modular Networks
• Dynamics in the Sherrington-Kirkpatrick Ising spin glass at and above Tg
• Probing the Origins of Two-State Folding
• Topological Complexity of Frictional Interfaces: Friction Networks
• Random walks in directed modular networks
• Multi-scale Laplacian community detection in heterogeneous networks
• Sample-to-sample fluctuations in real-network ensembles
• Stretched exponential behavior and random walks on diluted hypercubic lattices
• Network evolution towards optimal dynamical performance
• Multiple structural transitions in interacting networks
• Fast Algorithm for Relaxation Processes in Big-data Systems
• Amplitude death and restoration in networks of oscillators with random-walk diffusion
• Giant component in a configuration-model power-law graph with a variable number of links
• Symmetry-based coarse-graining of evolved dynamical networks
• Network Extreme Eigenvalue - from Multimodal to Scale-free Network
• Reconstruction of evolved dynamic networks from degree correlations
• Why lockdown : On the spread of SARS-CoV-2 in India, a network approach
• Network theory approach for data evaluation in the dynamic force spectroscopy of biomolecular interactions
• Relevance of the minimum degree to dynamic fluctuation in strongly heterogeneous networks
• Exact Spectral Dimension of the Random Surface
• Statistics of remote regions of networks