Reviews: Information-theoretic Limits for Community Detection in Network Models

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.