Counting graphs and null models of complex networks: Configuration model and extensions

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

1 Citaat (Scopus)
1 Downloads (Pure)

Samenvatting

Due to its ease of use, as well as its enormous flexibility in its degree structure, the configuration model has become the network model of choice in many disciplines. It has the wonderful property, that, conditioned on being simple, it is a uniform random graph with the prescribed degrees. This is a beautiful example of a general technique called the probabilistic method that was pioneered by Erdős. It allows us to count rather precisely how many graphs there are with various degree structures. As a result, the configuration model is often used as a null model in network theory, so as to compare real-world network data to. When the degrees are sufficiently light-tailed, the asymptotic probability of simplicity for the configuration model can be explicitly computed. Unfortunately, when the degrees vary rather extensively and vertices with very high degrees are present, this method fails. Since such degree sequences are frequently reported in empirical work, this is a major caveat in network theory. In this survey, we discuss recent results for the configuration model, including asymptotic results for typical distances in the graph, asymptotics for the number of self-loops and multiple edges in the finite-variance case. We also discuss a possible fix to the problem of non-simplicity, and what the effect of this fix is on several graph statistics. Further, we discuss a generalization of the configuration model that allows for the inclusion of community structures. This model removes the flaw of the locally tree-like nature of the configuration model, and gives a much improved fit to real-world networks.

Originele taal-2Engels
TitelGraph-Theoretic Concepts in Computer Science
Subtitel43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers
RedacteurenH.L. Bodleander, G.J. Woeginger
Plaats van productieDordrecht
UitgeverijSpringer
Pagina's1-17
Aantal pagina's17
ISBN van elektronische versie978-3-319-68704-9
ISBN van geprinte versie978-3-319-68704-9
DOI's
StatusGepubliceerd - 2017
Evenement43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2017) - Kapellerput, Eindhoven, Nederland
Duur: 21 jul 201723 jul 2017
http://www.win.tue.nl/wg2017/

Publicatie series

NaamLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10520 LNCS
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349

Workshop

Workshop43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2017)
Verkorte titelWG 2017
LandNederland
StadEindhoven
Periode21/07/1723/07/17
Internet adres

Vingerafdruk Duik in de onderzoeksthema's van 'Counting graphs and null models of complex networks: Configuration model and extensions'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    van der Hofstad, R. W. (2017). Counting graphs and null models of complex networks: Configuration model and extensions. In H. L. Bodleander, & G. J. Woeginger (editors), Graph-Theoretic Concepts in Computer Science: 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers (blz. 1-17). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10520 LNCS). Springer. https://doi.org/10.1007/978-3-319-68705-6_1