TY - JOUR

T1 - Sharpest possible clustering bounds using robust random graph analysis

AU - Brugman, Judith

AU - van Leeuwaarden, Johan S.H.

AU - Stegehuis, Clara

PY - 2022/12

Y1 - 2022/12

N2 - Complex network theory crucially depends on the assumptions made about the degree distribution, while fitting degree distributions to network data is challenging, in particular for scale-free networks with power-law degrees. We present a robust assessment of complex networks that does not depend on the entire degree distribution, but only on its mean, range, and dispersion: summary statistics that are easy to obtain for most real-world networks. By solving several semi-infinite linear programs, we obtain tight (the sharpest possible) bounds for correlation and clustering measures, for all networks with degree distributions that share the same summary statistics. We identify various extremal random graphs that attain these tight bounds as the graphs with specific three-point degree distributions. We leverage the tight bounds to obtain robust laws that explain how degree-degree correlations and local clustering evolve as a function of node degrees and network size. These robust laws indicate that power-law networks with diverging variance are among the most extreme networks in terms of correlation and clustering, building a further theoretical foundation for the widely reported scale-free network phenomena such as correlation and clustering decay.

AB - Complex network theory crucially depends on the assumptions made about the degree distribution, while fitting degree distributions to network data is challenging, in particular for scale-free networks with power-law degrees. We present a robust assessment of complex networks that does not depend on the entire degree distribution, but only on its mean, range, and dispersion: summary statistics that are easy to obtain for most real-world networks. By solving several semi-infinite linear programs, we obtain tight (the sharpest possible) bounds for correlation and clustering measures, for all networks with degree distributions that share the same summary statistics. We identify various extremal random graphs that attain these tight bounds as the graphs with specific three-point degree distributions. We leverage the tight bounds to obtain robust laws that explain how degree-degree correlations and local clustering evolve as a function of node degrees and network size. These robust laws indicate that power-law networks with diverging variance are among the most extreme networks in terms of correlation and clustering, building a further theoretical foundation for the widely reported scale-free network phenomena such as correlation and clustering decay.

U2 - 10.1103/PhysRevE.106.064311

DO - 10.1103/PhysRevE.106.064311

M3 - Article

SN - 2470-0045

VL - 106

JO - Physical Review E

JF - Physical Review E

IS - 6

M1 - 064311

ER -