2026-07-23T21:02:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9474 2024-03-06T10:43:50Z ddc:004 open_access

Parallel and I/O-efficient Randomisation of Massive Networks using Global Curveball Trades Carstens, Corrie Jacobien Hamann, Michael Meyer, Ulrich Penschuck, Manuel Tran, Hung Wagner, Dorothea Graph randomisation Curveball I/O-efficiency Parallelism 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Corrie Jacobien Carstens and Michael Hamann and Ulrich Meyer and Manuel Penschuck and Hung Tran and Dorothea Wagner 2018 Is Part Of LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2018.11 urn:nbn:de:0030-drops-94745 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.11 eng https://creativecommons.org/licenses/by/3.0/legalcode