Efficient Sampling of Ensembles of Large Graphs with Prescribed Degrees

Generating uniform ensembles of random graphs with prescribed structural constraints is essential for many network analyses. Unfortunately, problems with all known methods make it impractical to sample ensembles of large graphs. Recent advances that significantly improve direct construction or sequential importance sampling (SIS) methods will be discussed. SIS produces samples independently but not uniformly. Sampling uniformity can be achieved by reweighting. However, as the construction algorithms involve random multiplicative processes, the individual sample weights are generally log-normally distributed, implying that exponentially many samples are nominally required to calculate ensemble averages. Algorithmic improvements that substantially reduce the variance of the samples’ log-weights will be presented. Additionally, if the samples’ log-weight and the value of the quantity being measured can be assumed to have a bivariate normal distribution, then the efficiency of the sampling can be further improved by estimating the parameters of the distributions and using those estimates to estimate ensemble averages. With these improvements, prescribed degree scale-free networks with exponent $\gamma=2$ as large as a $10^6$ nodes can be effectively sampled.