Community detection in networks with unequal groups

Recently, a phase transition has been discovered in the network community detection problem below which no algorithm can tell which nodes belong to which communities with success any better than a random guess. This result has, however, so far been limited to the case where the communities have the same size or the same average degree. Here we consider the case where the sizes or average degrees differ. This asymmetry allows us to assign nodes to communities with better-than-random success by examining their local neighborhoods. Using the cavity method, we show that this removes the detectability transition completely for networks with four groups or fewer, while for more than four groups the transition persists up to a critical amount of asymmetry but not beyond. The critical point in the latter case coincides with the point at which local information percolates, causing a global transition from a less-accurate solution to a more-accurate one.

Figure 1

The overlap $Q$, Eq. (40), and the marginal overlap $Q_{\mu }$, Eq. (41), for belief propagation on networks generated by the stochastic block model with $q=2$ groups, $n={10}^5$ nodes, average degree $c=3$, and group sizes as given in Eqs. (37) and (38), as a function of $\epsilon =c_{\mathrm{in}}-c_{\mathrm{out}}$ for various values of $\delta$. Increasing $\delta$ (from bottom to top at the left of both panels) corresponds to greater differences between the group sizes and average degrees. The dashed lines in the left panel are the expected values in the weak-structure (i.e., $\epsilon =0$) limit, Eq. (42). Note how the sharp detectability transition disappears for $\delta >0$; both overlaps are smooth functions of the block model parameters.

Figure 2

The marginal overlap $Q_{\mu }$ (a) and log (base 10) of the convergence time (b) as a function of $\epsilon$ and $\delta$ for networks with $q=2$ groups, size $n={10}^5$, and average degree $c=3$. The overlap is a smooth function except at the detectability transition for equal-sized groups, which occurs when $\delta =0$ and $\epsilon =2\sqrt{c}$. This is also the only place where the convergence time diverges. Thus for $q=2$ and $\delta >0$ there is no detectability transition. In both panels $\delta$ of each line is increasing from bottom to top.

Figure 3

The overlap $Q$ for belief propagation on fully disassortative networks generated by the stochastic block model with $q=5$ groups, $n={10}^5$ nodes, and various values of $\delta$ (increasing from bottom to top) as indicated, as a function of average degree $c$. In panel (a) we initialize the beliefs with uniform random values; in panel (b) we initialize them with the true (planted) communities. For small values of $\delta$ there is a range of $c$ where the latter initialization gives a higher overlap, indicating a second and better fixed point with a small basin of attraction. In particular, for $\delta =0$ the coexistence region corresponds to $12.8<c<16$.

Figure 4

The overlap $Q$ (a) and log (base 10) of the convergence time (b) as a function of $c$ and $\delta$ for totally disassortative networks with $q=5$ groups and $n={10}^5$ nodes. The beliefs are initialized with random values in both panels. The first-order hard-easy transition is visible as a line in the $c-\delta$ plane where the overlap jumps discontinuously and the convergence time diverges. The height of the discontinuity decreases with increasing $\delta$ until we reach a critical point at which it vanishes at a second-order transition. Above this point the overlap is a smooth function of $c$ and $\delta$ and there is no detectability transition.

Figure 5

Phase diagram in the $c-\delta$ plane for the $q=5$ fully disassortative case described in the text. The blue curve shows where the near-trivial fixed point becomes unstable (also called the Kestum-Stigum or hard-easy transition); the green curve is the point at which the accurate fixed point disappears. The gray area between the two is the coexistence region in which both fixed points are stable and belief propagation can converge to either depending on the initial conditions. The red curve is the condensation transition at which the likelihoods cross over; the black dot is the critical point above which there is no phase transition behavior at all.

Figure 6

The overlap $Q$ and marginal overlap $Q_{\mu }$ achieved by belief propagation on networks with $q=2$ groups, average degree $c=8$, and $\delta =0.6$, as a function of $\epsilon =c_{\mathrm{in}}-c_{\mathrm{out}}$. The black (middle) curve in each panel shows the result of iterating belief propagation until it converges to a fixed point as in Fig. 1; the other curves show the overlap after 1 (top and bottom curves) and 2 (second top and second bottom curves) iterations. The lower curves in each panel use initial messages ${\mu }_a^{i\to j}={\gamma }_a$ equal to the prior probabilities of the groups as discussed in Sec. 4b; the upper curves use initial messages ${\mu }_a^{i\to j}={\delta }_{a,s_i}$ corresponding to the planted communities. Each measurement is averaged over 10 different networks of size $n={10}^5$.

Figure 7

The overlap $Q$ and marginal overlap $Q_{\mu }$ for belief propagation on fully disassortative networks generated by the stochastic block model with $q=5$ groups and $\delta =0.05$, as a function of the average degree $c$. The two black curves in the middle of each panel show the final converged result starting from the prior initialization and planted initialization respectively. The other curves show the results of belief propagation after $t=1,2,4,8$ iterations (red, cyan, green, and blue curves respectively, i.e., from top to bottom for upper four curves and from bottom to top for lower four curves) starting from each initialization. The converged result consists of one network at each point, and each measurement of the finite-step data is averaged over five different networks of size $n={10}^5$.