Optimal subgraph structures in scale-free configuration models

Research output: Contribution to journalArticleAcademic

17 Downloads (Pure)

Abstract

Subgraphs reveal information about the geometry and functionalities of complex networks. For scale-free networks with unbounded degree fluctuations, we count the number of times a small connected graph occurs as a subgraph (motif counting) or as an induced subgraph (graphlet counting). We obtain these results by analyzing the configuration model with degree exponent $\tau\in(2,3)$ and introducing a novel class of optimization problems. For any given subgraph, the unique optimizer describes the degrees of the nodes that together span the subgraph. We find that every subgraph occurs typically between vertices with specific degree ranges. In this way, we can count and characterize {\it all} subgraphs. We refrain from double counting in the case of multi-edges, essentially counting the subgraphs in the {\it erased} configuration model.
Original languageEnglish
Article number1709.03466
Number of pages26
JournalarXiv
Issue number1709.03466
Publication statusPublished - 11 Sep 2017

Fingerprint

counting
configurations
apexes
exponents
optimization
geometry

Bibliographical note

26 pages, 6 figures

Cite this

@article{84fd716522fc4e70929a396aaf6a2d52,
title = "Optimal subgraph structures in scale-free configuration models",
abstract = "Subgraphs reveal information about the geometry and functionalities of complex networks. For scale-free networks with unbounded degree fluctuations, we count the number of times a small connected graph occurs as a subgraph (motif counting) or as an induced subgraph (graphlet counting). We obtain these results by analyzing the configuration model with degree exponent $\tau\in(2,3)$ and introducing a novel class of optimization problems. For any given subgraph, the unique optimizer describes the degrees of the nodes that together span the subgraph. We find that every subgraph occurs typically between vertices with specific degree ranges. In this way, we can count and characterize {\it all} subgraphs. We refrain from double counting in the case of multi-edges, essentially counting the subgraphs in the {\it erased} configuration model.",
keywords = "math.PR",
author = "{van der Hofstad}, R.W. and {van Leeuwaarden}, J.S.H. and C. Stegehuis",
note = "26 pages, 6 figures",
year = "2017",
month = "9",
day = "11",
language = "English",
journal = "arXiv",
publisher = "Cornell University Library",
number = "1709.03466",

}

Optimal subgraph structures in scale-free configuration models. / van der Hofstad, R.W.; van Leeuwaarden, J.S.H.; Stegehuis, C.

In: arXiv, No. 1709.03466, 1709.03466, 11.09.2017.

Research output: Contribution to journalArticleAcademic

TY - JOUR

T1 - Optimal subgraph structures in scale-free configuration models

AU - van der Hofstad, R.W.

AU - van Leeuwaarden, J.S.H.

AU - Stegehuis, C.

N1 - 26 pages, 6 figures

PY - 2017/9/11

Y1 - 2017/9/11

N2 - Subgraphs reveal information about the geometry and functionalities of complex networks. For scale-free networks with unbounded degree fluctuations, we count the number of times a small connected graph occurs as a subgraph (motif counting) or as an induced subgraph (graphlet counting). We obtain these results by analyzing the configuration model with degree exponent $\tau\in(2,3)$ and introducing a novel class of optimization problems. For any given subgraph, the unique optimizer describes the degrees of the nodes that together span the subgraph. We find that every subgraph occurs typically between vertices with specific degree ranges. In this way, we can count and characterize {\it all} subgraphs. We refrain from double counting in the case of multi-edges, essentially counting the subgraphs in the {\it erased} configuration model.

AB - Subgraphs reveal information about the geometry and functionalities of complex networks. For scale-free networks with unbounded degree fluctuations, we count the number of times a small connected graph occurs as a subgraph (motif counting) or as an induced subgraph (graphlet counting). We obtain these results by analyzing the configuration model with degree exponent $\tau\in(2,3)$ and introducing a novel class of optimization problems. For any given subgraph, the unique optimizer describes the degrees of the nodes that together span the subgraph. We find that every subgraph occurs typically between vertices with specific degree ranges. In this way, we can count and characterize {\it all} subgraphs. We refrain from double counting in the case of multi-edges, essentially counting the subgraphs in the {\it erased} configuration model.

KW - math.PR

M3 - Article

JO - arXiv

JF - arXiv

IS - 1709.03466

M1 - 1709.03466

ER -