Power-law relations in random networks with communities

Abstract

Most random graph models are locally tree-like - do not contain short cycles - rendering them unfit for modeling networks with a community structure. We introduce the hierarchical configuration model (HCM), a generalization of the configuration model that includes community structures, while properties such as the size of the giant component, and the size of the giant percolating cluster under bond percolation can still be derived analytically. Viewing real-world networks as realizations of the HCM, we observe two previously unobserved power-law relations: between the number of edges inside a community and the community sizes, and between the number of edges going out of a community and the community sizes. We also relate the power-law exponent $\tau$ of the degree distribution with the power-law exponent of the community size distribution $\gamma$. In the special case of extremely dense communities (e.g., complete graphs), this relation takes the simple form $\tau =\gamma -1$.

arXiv comment13 pages, 11 figures

References in corpus (22)

• Fast unfolding of communities in large networks
• The structure and function of complex networks
• Community detection in graphs
• Power-law distributions in empirical data
• Finding community structure in very large networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Maps of random walks on complex networks reveal community structure
• The diameter of the world wide web
• Functional cartography of complex metabolic networks
• Random graphs with arbitrary degree distributions and their applications
• Network robustness and fragility: Percolation on random graphs
• Defining and identifying communities in networks
• Community detection algorithms: a comparative analysis
• Self-similar community structure in organisations
• Breakdown of the Internet under intentional attack
• Large-scale topological and dynamical properties of Internet
• Random graphs with clustering
• Random graphs containing arbitrary distributions of subgraphs
• Degree-degree correlations in random graphs with heavy-tailed degrees
• Uncovering disassortativity in large scale-free networks
• Distances in random graphs with finite variance degrees
• First passage percolation on random graphs with finite mean degrees

Cited by in corpus (8)

• Epidemic spreading on complex networks with community structures
• Critical window for the configuration model: finite third moment degrees
• Clustering Spectrum of scale-free networks
• Random intersection graphs with communities
• Explosion and distances in scale-free percolation
• Stylized facts in social networks: Community-based static modeling
• Mesoscopic scales in hierarchical configuration models
• Corrected mean-field model for random sequential adsorption on random geometric graphs