• Open Access

Randomization algorithms for large sparse networks

Kai Puolamäki, Andreas Henelius, and Antti Ukkonen
Phys. Rev. E 99, 053311 – Published 30 May 2019

Abstract

In many domains it is necessary to generate surrogate networks, e.g., for hypothesis testing of different properties of a network. Generating surrogate networks typically requires that different properties of the network are preserved, e.g., edges may not be added or deleted and edge weights may be restricted to certain intervals. In this paper we present an efficient property-preserving Markov chain Monte Carlo method termed CycleSampler for generating surrogate networks in which (1) edge weights are constrained to intervals and vertex strengths are preserved exactly, and (2) edge and vertex strengths are both constrained to intervals. These two types of constraints cover a wide variety of practical use cases. The method is applicable to both undirected and directed graphs. We empirically demonstrate the efficiency of the CycleSampler method on real-world data sets. We provide an implementation of CycleSampler in R, with parts implemented in C.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
3 More
  • Received 16 November 2018
  • Revised 8 March 2019

DOI:https://doi.org/10.1103/PhysRevE.99.053311

Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI.

Published by the American Physical Society

Physics Subject Headings (PhySH)

Networks

Authors & Affiliations

Kai Puolamäki1,2,*, Andreas Henelius1,2,3,†, and Antti Ukkonen1,‡

  • 1Department of Computer Science, University of Helsinki, Finland
  • 2Aalto University, Helsinki, Finland
  • 3Finnish Institute of Occupational Health, Helsinki, Finland

  • *kai.puolamaki@helsinki.fi
  • andreas.henelius@helsinki.fi
  • antti.ukkonen@helsinki.fi

Article Text

Click to Expand

References

Click to Expand
Issue

Vol. 99, Iss. 5 — May 2019

Reuse & Permissions
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Reuse & Permissions

It is not necessary to obtain permission to reuse this article or its components as it is available under the terms of the Creative Commons Attribution 4.0 International license. This license permits unrestricted use, distribution, and reproduction in any medium, provided attribution to the author(s) and the published article's title, journal citation, and DOI are maintained. Please note that some figures may have been included with permission from other third parties. It is your responsibility to obtain the proper permission from the rights holder directly for these figures.

×

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×