EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Bart De Clerck, Filip Van Utterbeeck, Luis E.C. Rocha

ACM Computing Surveys · 31.01.2027 · 59 (1) · 1-34

DOI: 10.1145/3842740 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Computing Surveys, online erschienen am 30.10.2026. Verfasst von Bart De Clerck und 2 weiteren Autor:innen. Die Arbeit nennt 92 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Research Foundation - Flanders, Belgian Special Research Fund.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • Research Foundation - Flanders
  • Belgian Special Research Fund

Zitieren

APA

Clerck, B. D., Utterbeeck, F. V., & Rocha, L. E. (2027). Degree-Preserving Randomization Methods for Network Analysis: Models, Algorithms, and Applications. ACM Computing Surveys, 59(1), 1-34. https://doi.org/10.1145/3842740

Vancouver

Clerck BD, Utterbeeck FV, Rocha LE. Degree-Preserving Randomization Methods for Network Analysis: Models, Algorithms, and Applications. ACM Computing Surveys. 2027;59(1):1-34. doi:10.1145/3842740

BibTeX
@article{Clerck2027,
  author = {Clerck, Bart De and Utterbeeck, Filip Van and Rocha, Luis E.C.},
  title = {Degree-Preserving Randomization Methods for Network Analysis: Models, Algorithms, and Applications},
  journal = {ACM Computing Surveys},
  year = {2027},
  volume = {59},
  number = {1},
  pages = {1--34},
  doi = {10.1145/3842740}
}
Kostenlos starten →