  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. 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.
  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 processing every node in a
graph during 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
nearly one order of magnitude faster.
