Fast Sequential Creation of Random Realizations of Degree Sequences

Area of Science:

• Graph theory
• Computational mathematics
• Network science

Background:

• Generating random graph realizations from large degree sequences presents computational challenges.
• Markov chain Monte Carlo (MCMC) methods are fast but suffer from memory constraints for large graphs.

Purpose of the Study:

• To develop efficient and scalable methods for creating random graph realizations.
• To address the termination time limitations of sequential importance sampling (SIS) schemes.

Main Methods:

• Focus on sequential importance sampling (SIS) schemes for random graph generation.
• Introduction of a novel sampling method designed to guarantee termination.
• Comparison of the new method's speed with existing Markov chain Monte Carlo (MCMC) techniques.

Main Results:

• The proposed sampling method guarantees termination for random graph realization.
• Achieves computational speed comparable to the MCMC method.
• Overcomes memory constraints associated with MCMC for large graphs.

Conclusions:

• The new sampling method offers an efficient and scalable solution for generating large random graphs.
• Provides a practical alternative to MCMC for large-scale graph realization problems.
• Ensures reliable and timely completion of random graph generation tasks.