License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2018.11
URN: urn:nbn:de:0030-drops-94745
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9474/
Go to the corresponding LIPIcs Volume Portal

Carstens, Corrie Jacobien ; Hamann, Michael ; Meyer, Ulrich ; Penschuck, Manuel ; Tran, Hung ; Wagner, Dorothea

Parallel and I/O-efficient Randomisation of Massive Networks using Global Curveball Trades

pdf-format:
LIPIcs-ESA-2018-11.pdf (1.0 MB)

Abstract

Graph randomisation is a crucial task in the analysis and synthesis of networks. It is typically implemented as an edge switching process (ESMC) repeatedly swapping the nodes of random edge pairs while maintaining the degrees involved [Mihail and Zegura, 2003]. Curveball is a novel approach that instead considers the whole neighbourhoods of randomly drawn node pairs. Its Markov chain converges to a uniform distribution, and experiments suggest that it requires less steps than the established ESMC [Carstens et al., 2016]. Since trades however are more expensive, we study Curveball's practical runtime by introducing the first efficient Curveball algorithms: the I/O-efficient EM-CB for simple undirected graphs and its internal memory pendant IM-CB. Further, we investigate global trades [Carstens et al., 2016] processing every node in a single super step, and show that undirected global trades converge to a uniform distribution and perform superior in practice. We then discuss EM-GCB and EM-PGCB for global trades and give experimental evidence that EM-PGCB achieves the quality of the state-of-the-art ESMC algorithm EM-ES [M. Hamann et al., 2017] nearly one order of magnitude faster.

BibTeX - Entry

@InProceedings{carstens_et_al:LIPIcs:2018:9474,
  author =	{Corrie Jacobien Carstens and Michael Hamann and Ulrich Meyer and Manuel Penschuck and Hung Tran and Dorothea Wagner},
  title =	{{Parallel and I/O-efficient Randomisation of Massive Networks using Global Curveball Trades}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Yossi Azar and Hannah Bast and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9474},
  URN =		{urn:nbn:de:0030-drops-94745},
  doi =		{10.4230/LIPIcs.ESA.2018.11},
  annote =	{Keywords: Graph randomisation, Curveball, I/O-efficiency, Parallelism}
}

Keywords: Graph randomisation, Curveball, I/O-efficiency, Parallelism
Collection: 26th Annual European Symposium on Algorithms (ESA 2018)
Issue Date: 2018
Date of publication: 14.08.2018
Supplementary Material: Stable versions of IM-CB and EM-GCB are released as part of NetworKit (http://network-analysis.info).

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI