(top) (a) Learning curves of the model parameters that indicate the strength of the modular structures. The vertical axis represents the total variation of the affinity matrix elements from the mean value . The horizontal axis represents the number of steps in the EM algorithm. We considered examples for the SBMs with a simple community structure (circles) and a bipartite structure (rectangles), as shown in the inset. To detect these structures, we did not use the affinity matrix restricted to Eq. (); instead, we used the one with full degrees of freedom. (bottom) Second-order expansions of the right-hand side of Eq. () with the first moments () and () (gray curves). For the other parameters, we set and . The dashed line represents . The arrows in each figure show the update process of schematically.

(Top) Trajectories of parameter learning based on the M-step of the EM algorithm for various planted values of . This plot shows the upper-left region of the phase diagram shown in Fig. , and we consider the same labeled SBM as in Fig. . The arrows show the directions in which the estimated parameters move. () The trajectories of the estimates for the case that the planted values (shown in open symbols) are in the detectable region. The trajectory for the graph with the planted value is represented by blue circles; is represented by yellow squares; is represented by red diamonds; and is represented by green triangles, respectively. In all cases, the initial estimate is set as . The dotted line represents the line with slope . () The trajectories of the estimates in other cases. The trajectories with the planted values (red circles) and (cyan squares) are the cases in which the planted values (shown in open symbols) are in the undetectable region though the initial estimates are set as . The trajectories with the planted values (orange diamonds) and (purple triangles) are the cases in which is initially located in the undetectable region , though the planted values are in the detectable region. (Bottom) Spectra of the weighted nonbacktracking matrix in the complex plane with corresponding to () , () , and () . The solid line (red) represents the circle with radius .

Behavior of the EM algorithm in the simple community structure with three modules. The average degree of each edge-type is and . We consider two types of edges (). () Second-order expansion of the right-hand side of Eq. () with ; the dashed line represents . In the inset, matrix where and are represented by black and white, respectively. () Detectability phase-diagram. The dashed ellipse, shaded region, and circles represent the detectability threshold under the Nishimori condition, undetectable region of the EM algorithm, and results of the numerical experiments (the average is taken over five samples), respectively, as shown in Fig. . represents the point of the uniform random graph. () Trajectories of with various initial values in the phase space. The trajectory for the graph with the planted value corresponds to the blue circles; corresponds to the yellow squares; corresponds to the red diamonds; and corresponds to the green triangles. As in Fig. , the planted values are shown by open symbols. The dashed lines represent the lines with slopes , 1, and . For the numerical experiments, we use the labeled SBMs with .

Behavior of the EM algorithm in a noncommunity structure with two modules. The average degree of each edge type is and . () matrix where and are represented by black and white, respectively. We consider two types of edges (). () Detectability phase diagram. The dashed ellipse, shaded region, and circles represent the detectability threshold under the Nishimori condition, undetectable region of the EM algorithm, and results of the numerical experiments (the average is taken over five samples), respectively, as in Fig. . represents the point of the uniform random graph. () Trajectories of with various initial values in the phase space. The trajectory for the graph with the planted value corresponds to the blue circles; corresponds to the yellow squares; corresponds to the red diamonds; and corresponds to the green triangles. As in Fig. , the planted values are shown by open symbols. The dashed lines represent lines with slopes and 1. For the numerical experiments, we use the labeled SBMs with .

(a) Same detectability phase-diagram as in Fig. . The striped region represents the undetectable region that becomes detectable when the edges of are discarded. (b) Vertical histograms of the overlap distribution. The same labeled SBM as that in Fig.  is considered, and the instances with , , and are generated. The histograms of various values of are horizontally aligned (30 samples for each histogram). The ones in the detectable phase, i.e., , are indicated in blue, while the ones in the undetectable phase, i.e., , are in red. The white points (connected via dashed lines) indicate the medians of overlaps. The population of the success and failure changes at the critical value that we estimated.

Planted matrices (two left panels) and evolution of the deviation from the uninformative module-assignment distribution (two right panels). In each matrix, the colored elements represent , and the white elements represent . In the right panels, the mean value is represented as a white line, and its standard deviation is shown as a colored tie. The top panels correspond to the example given in Sec. , i.e., the simple community structure with , and we set as the planted model parameters. The middle panels correspond to the example given in Sec. , i.e., the simple community structure with , and we set as the planted model parameters. The bottom panels correspond to the example given in Sec. , i.e., the general structure of Fig. , and we set as the planted model parameters.