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

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

6 Citations (Scopus)

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
EditorsD. Gleich, J. Komjáthy, N. Litvak
Place of PublicationCham
PublisherSpringer
Pages54-65
Number of pages12
ISBN (Electronic)978-3-319-26784-5
ISBN (Print)978-3-319-26783-8
DOIs
Publication statusPublished - 9 Dec 2015
Externally publishedYes

Publication series

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

Fingerprint Dive into the research topics of 'Upper bounds for number of removed edges in the erased configuration model'. Together they form a unique fingerprint.

Cite this