KIT | KIT-Bibliothek | Impressum | Datenschutz

Parallel and I/O-efficient randomisation of massive networks using global curveball trades

Carstens, C. J.; Hamann, M. 1; Meyer, U.; Penschuck, M.; Tran, H.; Wagner, D. 1
1 Karlsruher Institut für Technologie (KIT)

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 [23]. 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 [6]. 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 [6] 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 EMPGCB for global trades and give experimental evidence that EM-PGCB achieves the quality of the state-of-the-art ESMC algorithm EM-ES [15] nearly one order of magnitude faster.


Verlagsausgabe §
DOI: 10.5445/IR/1000086340
Veröffentlicht am 12.10.2018
Originalveröffentlichung
DOI: 10.4230/LIPIcs.ESA.2018.11
Scopus
Zitationen: 8
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2018
Sprache Englisch
Identifikator ISBN: 978-3-9597708-1-1
ISSN: 1868-8969
urn:nbn:de:swb:90-863407
KITopen-ID: 1000086340
Erschienen in 26th European Symposium on Algorithms, ESA 2018; Helsinki; Finland; 20 August 2018 through 22 August 2018
Verlag Schloss Dagstuhl - Leibniz-Zentrum für Informatik (LZI)
Serie Leibniz International Proceedings in Informatics, LIPIcs ; 112
Schlagwörter Graph randomisation, Curveball, I/O-efficiency, Parallelism
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page