Power-law relations in random networks with communities

Clara Stegehuis*, Remco Van Der Hofstad, Johan S.H. Van Leeuwaarden

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

10 Citations (Scopus)
8 Downloads (Pure)


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 HCM, we observe two previously undiscovered 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 τ of the degree distribution with the power-law exponent of the community-size distribution γ. In the case of extremely dense communities (e.g., complete graphs), this relation takes the simple form τ=γ-1.

Original languageEnglish
Article number012302
JournalPhysical Review E
Issue number1
Publication statusPublished - 5 Jul 2016
Externally publishedYes


Dive into the research topics of 'Power-law relations in random networks with communities'. Together they form a unique fingerprint.

Cite this