Phase transition in the detection of modules in sparse networks

Stochastic block models.

We consider networks of $N$ nodes. Each node $i$ has a hidden label $t_{i}\in\{1,\ldots,q\}$, specifying which of $q$ groups it is a member of. These labels are chosen independently, where $n_{a}$ is the probability that a given node has label $a\in\{1,\ldots,q\}$ (normalized so that $\sum_{a=1}^{q}n_{a}=1$). If $N_{a}$ is the number of nodes in each group, we have $n_{a}=\lim_{N\to\infty}N_{a}/N$.

Once the group assignment is chosen, the model generates a graph $G$ as follows. For each pair of nodes $i,j$ with $i<j$, we put an edge between $i$ and $j$ independently with probability $p_{t_{i},t_{j}}$, leaving them unconnected with probability $1-p_{t_{i},t_{j}}$. We call $p_{ab}$ the affinity matrix. Since we are interested in the sparse case where $p_{ab}=O(1/N)$, we will use the rescaled affinity matrix $c_{ab}=Np_{ab}$ and assume that $c_{ab}=O(1)$ in the limit $N\to\infty$.

Bayesian inference for block models.

Bayesian inference has been applied to community detection before. However, except for some very specific generative models NewmanLeicht07 , the likelihood function must be computed approximately, either through Monte Carlo sampling (e.g. ClausetMoore08 ) or variational methods HofmanWiggins08 . The crucial contribution of our work is that the quantities that follow from Bayesian inference can be computed exactly in the thermodynamic limit using the cavity method, or on real finite networks using the BP algorithm in time roughly linear in the size of the network. The probability that the model parameters take a given set of values $\{\theta\}=(q,\{n_{a}\},\{c_{ab}\})$, conditioned on the topology of the network $G$, is

The sum is over all possible group assignments $\{t_{i}\}$, where $t_{i}\in\{1,\ldots,q\}$ for each node $i$. The prior $P(\{\theta\})$ includes all graph-independent information about the values of the parameters. We will assume there is no such information available and hence this prior is uniform. In that case, maximizing $P(\{\theta\}\mid G)$ over $\{\theta\}$ is equivalent to maximizing the sum $\sum_{\{t_{i}\}}P(G,\{t_{i}\}\mid\{\theta\})$.

The function $P(G,\{t_{i}\}\mid\{\theta\})$ is called the likelihood. It is the probability that the model would produce the group assignment $\{t_{i}\}$ and the network $G$, assuming that its parameters are $\{\theta\}$. We can write the likelihood exactly for many different generative models; for the stochastic block model defined above, it is

Thus $P(\{\theta\}\mid G)$ is proportional to the partition sum $Z(\{\theta\})$ of a generalized Potts model, with Hamiltonian

There is a strong $O(1)$ interaction between connected nodes, and a weak $O(1/N)$ one between unconnected nodes. The $\log n_{t_{i}}$ play the role of local fields, enforcing the prior distribution $\{n_{a}\}$ on group assignments.

Inferring the parameters $\{\theta\}$ is equivalent to minimizing the free energy $f(\{\theta\})=-\log{Z(\{\theta\})}/N$ associated with (2). If $f(\{\theta\})$ has a non-degenerate minimum, then, from the saddle point method, $\{\theta\}$ is with high probability exactly the set of parameters used in the generation of the network. In that case, inferring the parameters of the underlying model is possible.

It can be proven in general NishimoriBook01 that this marginalization maximizes the number of correctly labeled nodes in the thermodynamic limit, and that it is a better choice than using the ground state of (2). Furthermore, a configuration chosen according to the Boltzmann distribution has, asymptotically, the correct group sizes and the correct number of edges between each pair of groups, while for the ground state this is not true; finding the minimum bisection, for instance, creates the illusion of two groups even in a completely random graph coppersmith . Moreover marginalization is algorithmically easier than searching for the ground state. The expected number of correctly labeled nodes can be estimated as $\sum_{i}\nu_{i}(t_{i}^{*})$, even without knowing the original assignment.

Belief Propagation.

We could estimate the free energy using Monte Carlo (MC) sampling, and we do this for comparison. But a faster algorithm is Belief Propagation (BP), known in physics as the cavity method MezardParisi01 ; MezardMontanari07 . It is exact in the thermodynamic limit as long as the network is locally treelike, and as long as connected correlations decay rapidly as a function of topological distance.

To derive the BP equations YedidiaFreeman03 ; MezardMontanari07 , one introduces “messages” $\psi^{i\to j}_{t_{i}}$ and $\psi^{j\to i}_{t_{j}}$ for each pair of nodes $(i,j)$. These are conditional marginals in the cavity method. For instance, $\psi^{i\to j}_{t_{i}}$ is the probability that $i$ would be in group $t_{i}$ if $j$ were removed from the network. Assuming conditional independence between the neighbors of each node and neglecting lower order terms, the messages must be a fixed point of a consistency equation,

for each edge $(i,j)$. Here $\partial i$ is the set of $i$’s neighbors, the field $h_{t_{i}}=\frac{1}{N}\sum_{k}\sum_{t_{k}}c_{t_{k}t_{i}}\psi_{t_{k}}^{k}$ summarizes the influence of the non-edges, and $Z^{i\to j}$ is a normalizing factor. We start with random messages, and iterate (3) until we reach a fixed point. This typically takes just a few iterations, and each step takes linear, $O(N)$, time.

The marginals corresponding to the BP fixed point are $\nu_{i}(t_{i})=(1/Z^{i})\,n_{t_{i}}e^{-h_{t_{i}}}\prod_{j\in\partial i}\left[\sum_{t_{j}}c_{t_{j}t_{i}}\psi_{t_{j}}^{j\to i}\right]$, and the free energy is

where $Z^{ij}=\sum_{a>b}c_{ab}(\psi^{i\to j}_{a}\psi_{b}^{j\to i}+\psi^{i\to j}_{b}\psi_{a}^{j\to i})+\sum_{a}c_{aa}\psi^{i\to j}_{a}\psi_{a}^{j\to i}$. For more details, see YedidiaFreeman03 ; MezardMontanari07 . Requiring that $f_{\rm BP}(\{\theta\})$ is stationary we update the parameters to their most-likely values given the fixed point

and $n^{\prime}_{a}=\sum_{i}\nu_{i}(a)/N$. Starting with a suitable initial value $\{\theta_{0}\}$, we compute $\{\theta^{\prime}\}$ and iterate until convergence (see Fig. 1), as in the expectation-maximization algorithm DempsterLaird77 . To learn the number of groups $q$, we run the algorithm with several values of $q^{\prime}$. The free energy $f_{\rm BP}$ decreases with $q$ and then stays constant for $q^{\prime}\geq q$.

Phase diagrams.

(where $S_{q}$ is the permutation group) is zero, and the original assignment is undetectable. Generalizing AchlioptasCoja-Oghlan08-focs ; KrzakalaZdeborova09 , one can show there is essentially no difference between a graph produced by the block model and a completely random graph of the same average degree; the free energy of the two ensembles is asymptotically identical.

A third situation arises if $f_{\rm BP}{{\{\theta}\}}$ has both a paramagnetic fixed point and the ordered fixed point at the true $\{\theta\}$. In this case, the two phases co-exist and the detectability transition is first-order; see Fig. 2 on the right. The phase transition is located by comparing the free energies of the two phases. However, even if the ordered fixed point has a lower free energy, it is not easy to find it unless the initial messages are close to the true group assignment. All but an exponentially small set of initial messages will lead to the paramagnetic fixed point. This situation is typical of mean-field first-order phase transitions. In fact, recent results about random optimization problems show that finding the lower-free-energy phase in this case is an extremely hard problem FranzMezard01 ; KrzakalaZdeborova09 .

Only when the paramagnetic phase is no longer locally stable does inference become easy. We can compute the location of the transition to this easily-detectable phase analytically by analyzing how a small random perturbation to the paramagnetic fixed point propagates as the BP equations are iterated MezardMontanari06 ; KrzakalaZdeborova09 . It follows that for

the original group assignment is dynamically attractive and hence many algorithms, e.g. MC or BP, will converge to it. Note that it is typically still hard to compute the ground state of (2), even though we can compute the marginals, and therefore the optimal estimate of the group assignment, asymptotically exactly.

Real-world networks.

Our algorithm is not restricted to large random networks; it is applicable to real networks as well. We tested it on the “Karate Club” network Zachary77 , a common benchmark for community detection. For $q=2$, BP leads to two different fixed points. One corresponds to the actual known division into two groups. The other has a smaller free energy and thus a larger likelihood, and splits the network into high-degree nodes and low-degree nodes as found in KarrerNewman10 . These two fixed points correspond to two local minima of $f_{\rm BP}$ for $q=2$, and depending on the initial value $\{\theta_{0}\}$ BP converges to one or the other. For $q>2$, our algorithm converges to fixed points with yet lower values of $f_{\rm BP}$. For $q=4$ the best fixed point corresponds to a splitting of the two actual groups into high-degree and low-degree subgroups.

The results obtained with MC, which can be easily equilibrated for such a small network, are almost identical to those of BP in terms of the parameters and marginals, and identical in terms of the estimated group assignments. This demonstrates that BP is a useful approach even on real, finite networks that are far from trees.

Conclusion.

We have presented a principled and asymptotically exact analysis of the detection of communities in networks generated by the stochastic block model. There is a strict limit on detectability due to a transition from a phase where the free energy landscape lets us infer the model’s parameters, to a phase where it does not. In some cases the communities are detectable, but the problem is hard because the attractive region around the correct fixed point is exponentially small. Our analysis comes with an associated learning algorithm, which for large sparse networks generated from the model is able to learn the number of groups, their exact sizes, and the affinity matrix $p_{ab}$. Our approach and our algorithm are easily generalized to other local generative models, and we will investigate its performance on a variety of real-world networks in the future.

Acknowledgments.

We are grateful to Mark Newman for helpful discussions. C.M. is funded by the McDonnell Foundation.

References