Randomization algorithms for large sparse networks.

Area of Science:

• Network science
• Computational graph theory
• Statistical modeling

Background:

• Generating surrogate networks is crucial for hypothesis testing in network analysis.
• Preserving network properties like edge weights and vertex strengths during surrogate generation is challenging.
• Existing methods may lack efficiency or flexibility in handling diverse constraints.

Purpose of the Study:

• To introduce CycleSampler, an efficient property-preserving Markov chain Monte Carlo method.
• To enable the generation of surrogate networks with constrained edge weights and preserved vertex strengths.
• To support surrogate network generation where both edge and vertex strengths are interval-constrained.

Main Methods:

• CycleSampler utilizes a Markov chain Monte Carlo approach.
• The method accommodates two primary constraint types: interval-constrained edge weights with exact vertex strength preservation, and interval-constrained edge and vertex strengths.
• Applicable to both undirected and directed graphs.

Main Results:

• CycleSampler demonstrates efficiency in generating property-preserving surrogate networks.
• Empirical validation on real-world datasets confirms the method's performance.
• An R implementation with C components is provided.

Conclusions:

• CycleSampler offers an efficient and flexible solution for generating constrained surrogate networks.
• The method addresses key challenges in network analysis and hypothesis testing.
• The provided implementation facilitates practical application of the technique.