Parallel and I/O-efficient Randomisation of Massive Networks using Global Curveball Trades
share
Graph randomisation is an important task in the analysis and synthesis of networks. It is typically implemented as an iterative edge switching process swapping the endpoints of randomly selected edge pairs while maintaining the nodes' degrees. Curveball is a novel approach that considers the whole neighbourhoods of randomly drawn node pairs. It was shown that the underlying Markov chain converges to a uniform distribution, and experiments suggest that it requires less steps than the established edge switching process. We describe the first external memory Curveball algorithm EM-CB for simple undirected graphs and its internal memory counterpart IM-CB. Further, we introduce the notation of a global trade processing (almost) every node in a graph during a single super step, and show that global trades converge to a uniform distribution. We then discuss the parallel external memory algorithm EM-PGCB for global trades and give experimental evidence that EM-PGCB achieves the quality of the state-of-the-art external memory edge switching algorithm EM-ES nearly one order of magnitude faster.
READ FULL TEXT