Degree-Preserving Randomization Methods for Network Analysis: Models, Algorithms, and Applications

Graph randomization techniques are essential tools for network analysis, enabling researchers to assess the statistical significance of observed network properties and distinguish meaningful patterns from random fluctuations. However, the wide range of available methods and tools can create confusion, particularly regarding their assumptions, biases, and applicability. This survey provides a review of graph randomization approaches, with a focus on degree preserving methods implemented in popular software tools such as graph-tool, igraph, MaxEntropyGraphs.jl, NEMtropy, Networkit, NetworkX, and statnet/ergm. We evaluate these methods through case studies spanning undirected, directed, and bipartite graphs. Our findings reveal notable discrepancies in outcomes depending on the chosen randomization method: certain stub-matching implementations can introduce systematic degree biases, default MCMC iteration counts can be both insufficient and vastly excessive, and the assumption of normally distributed metrics can lead to incorrect significance assessments. We benchmark computational scaling across graph sizes ranging from 10 3 to 10 5 nodes, apply a systematic convergence diagnostics procedure to MCMC-based methods, and synthesize our findings into actionable tool selection guidance. Practical guidelines for method selection and recommendations to enhance reproducibility and transparency in network analysis are provided.