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 International Workshop on Algorithms and Models for the Web-Graph, WAW 2015 - Eindhoven, Netherlands
Duration: 10 Dec 201511 Dec 2015
Conference number: 12

Publication series

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

Workshop

Workshop12th International Workshop on Algorithms and Models for the Web-Graph, WAW 2015
Abbreviated titleWAW
CountryNetherlands
CityEindhoven
Period10/12/1511/12/15

Fingerprint

Upper bound
Configuration
Degree Distribution
Simple Graph
Power Law
Tauberian theorem
Model
Finite Size Effects
Speed of Convergence
Graph in graph theory
Vertex of a graph
Limiting Distribution
Complex Networks
Exponent
Scaling

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
van der Hoorn, W.L.F. / Upper bounds for number of removed edges in the erased configuration model. Algorithms and Models for the Web Graph: 12th International Workshop, WAW 2015, Eindhoven, The Netherlands, December 10-11, 2015, Proceedings. editor / David F. Gleich ; Julia Komjathy ; Nelly Litvak. Cham, Switzerland : Springer, 2015. pp. 54-65 (Lecture Notes in Computer Science).
@inproceedings{0ff740df3eae4063b89670f8fb193786,
title = "Upper bounds for number of removed edges in the erased configuration model",
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.",
keywords = "EWI-26777, IR-99368, METIS-315581",
author = "{van der Hoorn}, W.L.F.",
year = "2015",
month = "12",
day = "10",
doi = "10.1007/978-3-319-26784-5_5",
language = "English",
isbn = "978-3-319-26783-8",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "54--65",
editor = "Gleich, {David F.} and Julia Komjathy and Nelly Litvak",
booktitle = "Algorithms and Models for the Web Graph",

}

van der Hoorn, WLF 2015, Upper bounds for number of removed edges in the erased configuration model. in DF 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. Lecture Notes in Computer Science, vol. 9479, Springer, Cham, Switzerland, pp. 54-65, 12th International Workshop on Algorithms and Models for the Web-Graph, WAW 2015, Eindhoven, Netherlands, 10/12/15. https://doi.org/10.1007/978-3-319-26784-5_5

Upper bounds for number of removed edges in the erased configuration model. / van der Hoorn, W.L.F.

Algorithms and Models for the Web Graph: 12th International Workshop, WAW 2015, Eindhoven, The Netherlands, December 10-11, 2015, Proceedings. ed. / David F. Gleich; Julia Komjathy; Nelly Litvak. Cham, Switzerland : Springer, 2015. p. 54-65 (Lecture Notes in Computer Science; Vol. 9479).

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

TY - GEN

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

AU - van der Hoorn, W.L.F.

PY - 2015/12/10

Y1 - 2015/12/10

N2 - 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.

AB - 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.

KW - EWI-26777

KW - IR-99368

KW - METIS-315581

U2 - 10.1007/978-3-319-26784-5_5

DO - 10.1007/978-3-319-26784-5_5

M3 - Conference contribution

SN - 978-3-319-26783-8

T3 - Lecture Notes in Computer Science

SP - 54

EP - 65

BT - Algorithms and Models for the Web Graph

A2 - Gleich, David F.

A2 - Komjathy, Julia

A2 - Litvak, Nelly

PB - Springer

CY - Cham, Switzerland

ER -

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