Information-theoretic Limits for Community Detection in Network Models
We analyze the information-theoretic limits for the recovery of node labels in several network models. This includes the Stochastic Block Model, the Exponential Random Graph Model, the Latent Space Model, the Directed Preferential Attachment Model, and the Directed Small-world Model. For the Stochastic Block Model, the non-recoverability condition depends on the probabilities of having edges inside a community, and between different communities. For the Latent Space Model, the non-recoverability condition depends on the dimension of the latent space, and how far and spread are the communities in the latent space. For the Directed Preferential Attachment Model and the Directed Small-world Model, the non-recoverability condition depends on the ratio between homophily and neighborhood size. We also consider dynamic versions of the Stochastic Block Model and the Latent Space Model.
This article proves information theoretic lower bounds for the community detection problem in a range of network models. For the SBM, this has been previously achieved in works of Mossel-Neeman-Sly, Coja-Oghlan, Abbe-Sandon etc. The authors of the current paper plant community structure (two randomly assigned communities) in various other models such as latent space models, preferential attachment models, small-world models etc. and prove similar information theoretic lower bounds. The proofs employ  (not surprisingly) Fano's inequality in carefully restricted submodels.   However, the authors only prove lower bounds, it is not clear if these are tight (it is for the SBM), and if so what (preferably polynomial time) algorithms can achieve them. There are a host of other interesting questions to ask. For example, is there an information-computation gap for larger number of communities as in the case of the SBM?  I found the paper interesting and believe that it is a good contribution to the community detection literature.  Here are some comments/suggestions for the authors:  1. Repetition of the sentences "we are interested in information theoretic limits. Thus, we define the Markov Chain Y* --> A --> Y. Using Fano's inequality..." before every theorem is not necessary. Say it once in the beginning perhaps. Similarly, the sentence "The use of restricted ensembles..." is repeated in page 4, line 138. 2. Page 1, line 33: "several social networks" should be "several social network models". 3. Page 3, line 98: "In a" should be "In an". 4. Page 7, line 230: "classic Small-world" should be "classic small-world phenomenon". 5. Add commas after the if clauses in the theorems (at end of the displayed equations). 6. Since your particular ERGM is essentially an SBM with different parametrization, results of Mossel-Neeman-Sly should apply. So, you should add that the corresponding lower bound is tight for this subclass. 7. Since you have more than a page left within the NIPS page limit, it would be nice if you could say something about algorithms that could be used for community extraction in these models and/or what has been done in the literature and in what parameter regimes they are successful.