Larger holes as narrower degree distributions in complex networks

Abstract

Although the analysis of loops is not so much because of the complications, it has already been found that heuristically enhancing loops decreases the variance of degree distributions for improving the robustness of connectivity. While many real scale-free networks are known to contain shorter loops such as triangles, it remains to investigate the distributions of longer loops in more wide class of networks. We find a relation between narrower degree distributions and longer loops in investigating the lengths of the shortest loops in various networks with continuously changing degree distributions, including three typical types of realistic scale-free networks, classical Erdös-Rényi random graphs, and regular networks. In particular, we show that narrower degree distributions contain longer shortest loops, as a universal property in a wide class of random networks. We suggest that the robustness of connectivity is enhanced by constructing long loops of O(log N).

24 pages, 17 figures, 2 tables

References in corpus (23)

• Emergence of scaling in random networks
• The structure and function of complex networks
• The structure of scientific collaboration networks
• Random graphs with arbitrary degree distributions and their applications
• Classes of behavior of small-world networks
• Network robustness and fragility: Percolation on random graphs
• Mean-field theory for scale-free random networks
• Self-similar community structure in organisations
• Breakdown of the Internet under intentional attack
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
• Organization of Growing Random Networks
• Generation of uncorrelated random scale-free networks
• Network dismantling
• Message passing methods on complex networks
• A loop enhancement strategy for network robustness
• Distribution of shortest cycle lengths in random networks
• Statistical analysis of articulation points in configuration model networks
• The mean and variance of the distribution of shortest path lengths of random regular graphs
• Emergence of Robust and Efficient Networks in a Family of Attachment Models
• Statistical analysis of edges and bredges in configuration model networks
• The Fate of Articulation Points and Bredges in Percolation
• Universal vulnerability in strong modular networks with various degree distributions between inequality and equality
• Vulnerable Connectivity Caused by Local Communities in Spatial Networks