Giuseppe Gabriele Glaviano — University of Palermo #
Unbiased Randomization of Weighted Bipartite Networks with Exact Degree and Strength Sequences #
In the context of complex networks, designing a null model that preserves certain properties of the original network is a fundamental problem. While for binary bipartite networks, the problem has been solved by the Curveball algorithm, which preserves the degree of each node exactly, for weighted bipartite networks, finding a null model that strictly preserves some features of the original network is still an open challenge. We developed a microcanonical algorithm that preserves exactly the degree and the strength of each node in a weighted bipartite network. The algorithm is based on an edge-swap procedure that combines three different moves: weight shuffling, simple edge swap, and bridge edge swap. The algorithm has been built to guarantee that the underlying transition matrix of the Monte Carlo Markov chain is symmetric, which is a crucial property to obtain an unbiased sample of random graphs. We also empirically validated our algorithm, showing that it produces an unbiased sampling of graphs. Finally, we also provide a heuristic method to estimate the mixing time of the MCMC.