Distribution of shortest cycle lengths in random networks
arXiv:1712.00098 · doi:10.1103/PhysRevE.96.062307
Abstract
We present analytical results for the distribution of shortest cycle lengths (DSCL) in random networks. The approach is based on the relation between the DSCL and the distribution of shortest path lengths (DSPL). We apply this approach to configuration model networks, for which analytical results for the DSPL were obtained before. We first calculate the fraction of nodes in the network which reside on at least one cycle. Conditioning on being on a cycle, we provide the DSCL over ensembles of configuration model networks with degree distributions which follow a Poisson distribution (Erdos-Rényi network), degenerate distribution (random regular graph) and a power-law distribution (scale-free network). The mean and variance of the DSCL are calculated. The analytical results are found to be in very good agreement with the results of computer simulations.
arXiv comment44 pages, 11 figures
References in corpus (30)
- Emergence of scaling in random networks
- Statistical mechanics of complex networks
- Epidemic spreading in scale-free networks
- Epidemic processes in complex networks
- Random graphs with arbitrary degree distributions and their applications
- Scale-Free Networks are Ultrasmall
- Average path length in random networks
- Average path length in uncorrelated random networks with hidden variables
- Betweenness centrality correlation in social networks
- Structure-based control of complex networks with nonlinear dynamics
- Structure of shells in complex networks
- Articulation Points in Complex Networks
- Loops of any size and Hamilton cycles in random scale-free networks
- Metric structure of random networks
- How to Compute Loop Corrections to Bethe Approximation
- Looplessness in networks is linked to trophic coherence
- Distance distribution in random graphs and application to networks exploration
- Fractal Boundaries of Complex Networks
- On the number of circuits in random graphs
- Analytical results for the distribution of shortest path lengths in random networks
- Distance distribution in configuration model networks
- Circuits in random graphs: from local trees to global loops
- An algorithm for counting circuits: application to real-world and random graphs
- The distribution of shortest path lengths in a class of node duplication network models
- Ranking by Loops: a new approach to categorization
- Statistics of cycles in large networks
- Finding long cycles in graphs
- Broadband Macroscopic Cortical Oscillations Emerge from Intrinsic Neuronal Response Failures
- Percolation and Loop Statistics in Complex Networks
- Replica methods for loopy sparse random graphs
Cited by in corpus (17)
- Revealing the Micro-Structure of the Giant Component in Random Graph Ensembles
- The distribution of shortest path lengths in subcritical Erdős-Rényi networks
- Dynamical systems on large networks with predator-prey interactions are stable and exhibit oscillations
- Statistical analysis of articulation points in configuration model networks
- The mean and variance of the distribution of shortest path lengths of random regular graphs
- Analytical results for the distribution of cover times of random walks on random regular graphs
- Analytical results for the distribution of first hitting times of random walks on random regular graphs
- Analytical results for the distribution of first-passage times of random walks on random regular graphs
- Statistical analysis of edges and bredges in configuration model networks
- Phases of Small Worlds: A Mean Field Formulation
- Towards the cycle structures in complex network: A new perspective
- Characterizing cycle structure in complex networks
- Generating random networks that consist of a single connected component with a given degree distribution
- The distribution of shortest path lengths on trees of a given size in subcritical Erdos-Renyi networks
- A Gaussian integral that counts regular graphs
- Larger holes as narrower degree distributions in complex networks
- Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks