2015/12/15 by Amin Jalali, Qiyang Han, Jalali, Amin +5
Computer Science · Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #FOS: Computer and information sciences #Machine Learning (stat.ML) #Peer-to-Peer Network Technologies #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.1512.04937
openalex publication_date 2015/12/15 · openalex created_date 2022/09/11 · openalex updated_date 2026/07/28
The Stochastic Block Model (SBM) is a widely used random graph model for\nnetworks with communities. Despite the recent burst of interest in recovering\ncommunities in the SBM from statistical and computational points of view, there\nare still gaps in understanding the fundamental information theoretic and\ncomputational limits of recovery. In this paper, we consider the SBM in its\nfull generality, where there is no restriction on the number and sizes of\ncommunities or how they grow with the number of nodes, as well as on the\nconnection probabilities inside or across communities. This generality allows\nus to move past the artifacts of homogenous SBM, and understand the right\nparameters (such as the relative densities of communities) that define the\nvarious recovery thresholds. We outline the implications of our generalizations\nvia a set of illustrative examples. For instance, \log n is considered to be\nthe standard lower bound on the cluster size for exact recovery via convex\nmethods, for homogenous SBM. We show that it is possible, in the right\ncircumstances (when sizes are spread and the smaller the cluster, the denser),\nto recover very small clusters (up to \√(\log n) size), if there are just\na few of them (at most polylogarithmic in n).\n