Power-law relations in random networks with communities

Research output: Contribution to journalArticleAcademicpeer-review

9 Citations (Scopus)
75 Downloads (Pure)

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 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
Number of pages12
JournalPhysical Review E
Volume94
Issue number1
DOIs
Publication statusPublished - 2016

Fingerprint

Random Networks
Power Law
Community Structure
Configuration
Exponent
Giant Component
Network Modeling
configurations
exponents
Degree Distribution
Graph Model
Random Graphs
Complete Graph
Community
Model

Cite this

@article{837ad5002ca44b33858cf344c1c8cbc0,
title = "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 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.",
author = "C. Stegehuis and {van der Hofstad}, R.W. and {van Leeuwaarden}, J.S.H.",
year = "2016",
doi = "10.1103/PhysRevE.94.012302",
language = "English",
volume = "94",
journal = "Physical Review E",
issn = "2470-0045",
publisher = "American Physical Society",
number = "1",

}

Power-law relations in random networks with communities. / Stegehuis, C.; van der Hofstad, R.W.; van Leeuwaarden, J.S.H.

In: Physical Review E, Vol. 94, No. 1, 012302, 2016.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Power-law relations in random networks with communities

AU - Stegehuis, C.

AU - van der Hofstad, R.W.

AU - van Leeuwaarden, J.S.H.

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

U2 - 10.1103/PhysRevE.94.012302

DO - 10.1103/PhysRevE.94.012302

M3 - Article

C2 - 27575143

VL - 94

JO - Physical Review E

JF - Physical Review E

SN - 2470-0045

IS - 1

M1 - 012302

ER -