Efficient and exact sampling of simple graphs with given arbitrary degree sequence.

Area of Science:

• Network science
• Computational mathematics
• Statistical modeling

Background:

• Uniform sampling of network structures is crucial for simulating network properties across various fields.
• Current methods like Markov-Chain Monte Carlo and the Configuration Model have limitations in control and efficiency.
• Existing techniques suffer from unknown mixing times or uncontrolled rejections, hindering reliable network analysis.

Purpose of the Study:

• To develop an efficient algorithm for generating statistically independent graph samples from a given degree sequence.
• To provide a method that allows for flexible measurement of network observables, either uniformly or with a desired distribution.
• To overcome the limitations of existing graph sampling techniques, ensuring sample generation without rejections or back-tracking.

Main Methods:

• An efficient, polynomial-time algorithm is proposed for generating graph samples.
• The algorithm assigns weights to each sample, enabling diverse measurement strategies.
• Statistical reasoning based on the central limit theorem is used to analyze sample weight distributions.

Main Results:

• The algorithm generates statistically independent graph samples with arbitrary degree sequences.
• It guarantees sample production without rejections or back-tracking, improving efficiency.
• For large networks and degree sequences with numerous realizations, sample weights are expected to follow a lognormal distribution.

Conclusions:

• The proposed algorithm offers a robust and efficient solution for sampling network realizations.
• It provides enhanced control over sampling distributions for network observable measurements.
• The method is demonstrated to be effective for networks with power-law and binomial degree distributions.