Detectability thresholds of general modular graphs

We investigate the detectability thresholds of various modular structures in the stochastic block model. Our analysis reveals how the detectability threshold is related to the details of the modular pattern, including the hierarchy of the clusters. We show that certain planted structures are impossible to infer regardless of their fuzziness.

Figure 1

Affinity matrices of various modular structures. The elements in gray have higher connection probabilities.

Figure 2

Fraction of correctly classified vertices for the structure of Fig. 1. The size of the graph is $N=30000$, and each cluster is equal in size. The connected diamonds (purple), triangles (orange), and circles (cyan) represent the results of the algorithm in Sec. 3 for the average degrees $c=4,5$, and 6, respectively. The dashed vertical lines are the detectability thresholds predicted in (21) for $c=5$ and 6. The shadows represent the standard deviations of 10 samples.

Figure 3

Fraction of correctly classified vertices for the structure of Fig. 1 with error bars. The dashed vertical and horizontal lines represent the estimate of the detectability threshold (25) and $1/3$, respectively. The size of the graph is $N=30000$ with average degree $c=6$ and each cluster has the same size. The shadow represents the standard deviation of 10 samples.