Figure 1

Tests of the method on synthetic networks generated using the stochastic block model. (a) The diameter of the points represents the likelihood $P(k|A)$ of inferred values of $k$ as a function of true $k$ for networks with $k$ groups of size 250 nodes each. Each node has an average of 16 edges connecting it to its own group and eight edges to each other group. For each value of $k$, we performed ten runs of 2000 Monte Carlo sweeps each (plus 1000 for equilibration) and took our results from the run that found the highest average likelihood. Correct inference would place the most weight along the dashed diagonal line. (b) The fraction of runs detecting the correct number of groups in stochastic block models with $k=4$ groups of 250 nodes each and average degree 16, as a function of the strength of the community structure. The vertical dashed line represents the theoretical detectability threshold below which every algorithm must fail. Each point is an average over 1000 networks, and success is defined as assigning an absolute majority of the probability $P(k|A)$ to the correct value of $k$.