Upper bounds for number of removed edges in the erased configuration model

W.L.F. van der Hoorn

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)
2 Downloads (Pure)

Abstract

Models for generating simple graphs are important in the study of real-world complex networks. A well established example of such a model is the erased configuration model, where each node receives a number of half-edges that are connected to half-edges of other nodes at random, and then self-loops are removed and multiple edges are concatenated to make the graph simple. Although asymptotic results for many properties of this model, such as the limiting degree distribution, are known, the exact speed of convergence in terms of the graph sizes remains an open question. We provide a first answer by analyzing the size dependence of the average number of removed edges in the erased configuration model. By combining known upper bounds with a Tauberian Theorem we obtain upper bounds for the number of removed edges, in terms of the size of the graph. Remarkably, when the degree distribution follows a power-law, we observe three scaling regimes, depending on the power law exponent. Our results provide a strong theoretical basis for evaluating finite-size effects in networks.
Original languageEnglish
Title of host publicationAlgorithms and Models for the Web Graph
Subtitle of host publication12th International Workshop, WAW 2015, Eindhoven, The Netherlands, December 10-11, 2015, Proceedings
EditorsDavid F. Gleich, Julia Komjathy, Nelly Litvak
Place of PublicationCham, Switzerland
PublisherSpringer
Pages54-65
Number of pages12
ISBN (Electronic)978-3-319-26784-5
ISBN (Print)978-3-319-26783-8
DOIs
Publication statusPublished - 10 Dec 2015
Event12th Workshop on Algorithms and Models for the Web Graph, WAW 2015: workshop and winter school - Eurandom, Eindhoven, Netherlands
Duration: 7 Dec 201511 Dec 2015
Conference number: 12

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9479
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference12th Workshop on Algorithms and Models for the Web Graph, WAW 2015
Abbreviated titleWAW 2015
CountryNetherlands
CityEindhoven
Period7/12/1511/12/15

    Fingerprint

Keywords

  • EWI-26777
  • IR-99368
  • METIS-315581

Cite this

van der Hoorn, W. L. F. (2015). Upper bounds for number of removed edges in the erased configuration model. In D. F. Gleich, J. Komjathy, & N. Litvak (Eds.), Algorithms and Models for the Web Graph: 12th International Workshop, WAW 2015, Eindhoven, The Netherlands, December 10-11, 2015, Proceedings (pp. 54-65). (Lecture Notes in Computer Science; Vol. 9479). Cham, Switzerland: Springer. https://doi.org/10.1007/978-3-319-26784-5_5