We present an asymptotically exact analysis of the problem of detecting communities in sparse random networks. Our results are also applicable to detection of functional modules, partitions, and colorings in noisy planted models. Using a cavity method analysis, we unveil a phase transition from a region where the original group assignment is undetectable to one where detection is possible. In some cases, the detectable region splits into an algorithmically hard region and an easy one. Our approach naturally translates into a practical algorithm for detecting modules in sparse networks, and learning the parameters of the underlying model. PACS numbers: 64.60.aq,89.75.Hc,75.10.Hk In many networks, ranging from online communities to food webs, metabolic networks, and genetic regulatory networks, there are communities or modules that play distinct functional roles. A fundamental problem is to detect these communities and understand what role they play in the network's structure and dynamics. In social networks, these communities are often assortative, meaning that there is a higher density of connections within communities than between them, and many approaches to detecting these communities have been proposed (see e.g. [1]). In other networks, however, these modules may consist of nodes with few connections to each other, but which connect to the rest of the network in similar ways. In this Letter we analyze a random generative model for sparse modular networks, known as the stochastic block model. It provides a useful playground for theoretical ideas and the analysis of algorithms, and is a popular model for functional modules in real networks. Using the cavity method developed in the physics of disordered systems [2, 3] we exactly analyze the detectability of these modules in the limit of large sparse networks. As a function of the parameters, we compute the phase diagram and locate the associated phase transitions. We distinguish between a detectable phase where it is possible to learn the model's parameters and the group assignments of the nodes, and a non-intuitive undetectable phase where learning is impossible because the network's topology does not retain enough information about the original group memberships. The existence of a phase where a certain class of algorithms is unable to detect communities was previously predicted [4], but its location was only found approximately (and its size overestimated). In addition, unlike previous works based on finding a ground state, i.e., minimizing a cost function associated with a group assignment [4, 5] , our analysis is more general as it relies on the properties of the entire Boltzmann distribution of group assignments. We also unveil a transition from an algorithmically "hard" phase, where, we believe, no polynomial algorithm for learning the groups and parameters exists, to an "easy" phase where polynomial algorithms do exist. In the latter phase, we show that Belief Propagation (BP) [6] works on large networks in essentially linear time as a function of their size. BP was previously proposed for community detection [7] without, however, the ability to learn the parameters of the underlying model. Our approach also provides a natural measure of the significance of the modules in the network, since it computes the marginal probability that a given node belongs to a given group. If the network does not contain any modules, our method correctly infers this fact by making these marginals uniform. This is an aspect missing in the vast majority of the present approaches to community detection. Our theoretical understanding and algorithm are also applicable to real world networks, as we discuss briefly at the end of this paper (and in detail elsewhere). Moreover our approach is not restricted by the details of the generative model, and is easily generalized to more elaborate models (e.g., those of [8]). Stochastic block models. We consider networks of N nodes. Each node i has a hidden label t i ∈ {1, . . . , 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 ∈ {1, . . . , q} (normalized so that q a=1 n a = 1). If N a is the number of nodes in each group, we have n a = lim N →∞ 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 ti,tj , leaving them unconnected with probability 1 − p ti,tj . 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 = N p ab and assume that c ab = O(1) in the limit N → ∞.
SBM models have seen a resurged interest recently due to the conjecture of REF ) that hypotheses phase transition for weak recovery case (the one we are interested in this paper) and the existence of the information-computation gap for 4 communities in the symmetric case.
Phase transition in the detection of modules in sparse networks
Phys. Rev. Lett. 107, 065701 (2011)
Physics Computer Science Medicine