Optimal subgraph structures in scale-free configuration models

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademic

33 Downloads (Pure)


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.
Originele taal-2Engels
Aantal pagina's26
Nummer van het tijdschrift1709.03466
StatusGepubliceerd - 11 sep 2017

Bibliografische nota

26 pages, 6 figures


  • math.PR

Vingerafdruk Duik in de onderzoeksthema's van 'Optimal subgraph structures in scale-free configuration models'. Samen vormen ze een unieke vingerafdruk.

Citeer dit