### Abstract

Original language | English |
---|---|

Title of host publication | Algorithms and Models for the Web Graph |

Subtitle of host publication | 12th International Workshop, WAW 2015, Eindhoven, The Netherlands, December 10-11, 2015, Proceedings |

Editors | David F. Gleich, Julia Komjathy, Nelly Litvak |

Place of Publication | Cham, Switzerland |

Publisher | Springer |

Pages | 54-65 |

Number of pages | 12 |

ISBN (Electronic) | 978-3-319-26784-5 |

ISBN (Print) | 978-3-319-26783-8 |

DOIs | |

Publication status | Published - 10 Dec 2015 |

Event | 12th Workshop on Algorithms and Models for the Web Graph, WAW 2015: workshop and winter school - Eurandom, Eindhoven, Netherlands Duration: 7 Dec 2015 → 11 Dec 2015 Conference number: 12 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer |

Volume | 9479 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 12th Workshop on Algorithms and Models for the Web Graph, WAW 2015 |
---|---|

Abbreviated title | WAW 2015 |

Country | Netherlands |

City | Eindhoven |

Period | 7/12/15 → 11/12/15 |

### Fingerprint

### Keywords

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

### Cite this

*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

}

*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 Workshop on Algorithms and Models for the Web Graph, WAW 2015, Eindhoven, Netherlands, 7/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.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-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 -