Pseudo-likelihood methods for community detection in large sparse networks

By Arash Ali Amini, Aiyou Chen, Peter J. Bickel, Elizaveta Levina. 2012

442 citations recorded by the source corpus.

Many algorithms have been proposed for fitting network models with communities, but most of them do not scale well to large networks, and often fail on sparse networks. Here we propose a new fast pseudo-likelihood method for fitting the stochastic block model for networks, as well as a variant that allows for an arbitrary degree distribution by conditioning on degrees. We show that the algorithms perform well under a range of settings, including on very sparse networks, and illustrate on the example of a network of political blogs. We also propose spectral clustering with perturbations, a method of independent interest, which works well on sparse networks where regular spectral clustering fails, and use it to provide an initial value for pseudo-likelihood. We prove that pseudo-likelihood provides consistent estimates of the communities under a mild condition on the starting value, for the case of a block model with two communities.

Subfields: Statistical and Nonlinear Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/f80516343624df978ca4b1c3975c4ceed8f094b6

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Statistical and Nonlinear Physics

In Statistics and Probability

Citations in the corpus

Efficient discovery of overlapping communities in massive networks (2013, methodology): “The ﬁ rst is that many existing community detection algorithms assume that each node belongs to a single community (1, 3 – 7 , 14 – 16 The second dif ﬁ culty is that existing algorithms are too slow.”
A Comprehensive Survey on Community Detection With Deep Learning (2021, methodology): “Many traditional techniques, such as spectral clustering [31], [32] and statistical inference [33]–[35], have been applied to small networks and simple cases.”
Network quantile autoregression (2019, methodology): “(2011), Amini et al. (2013), and Sewell et al. (2017) using a block structure. Comparably, our proposed framework is related to the recent autoregressive models in large-scale social networks. Based on the cited literature, it is assumed that the behavioural patterns of network users are related to ”
Matrix estimation by Universal Singular Value Thresholding (2012, unknown): “lem in the stochastic blockmodel if k ≪ n, with no further conditions required. (The method will not work very well for sparse graphs, however; for recent advances on estimation in sparse graphs, see [7].) Theorem 2.3. For a stochastic blockmodel with k blocks, MSE(Mˆ)≤C r k n , where C is a constan”
Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel (2013, background): “[2]) which applies SC to the perturbed adjacency matrix Aper = A+a11 .”
A useful variant of the Davis--Kahan theorem for statisticians (2014, methodology): “(2011), Amini et al. (2013) and Bhattacharyya and Bickel (2014) use the Davis–Kahan sin θ theorem as a way of providing theoretical justification for spectral clustering in community detection with network data. Here, the matrices of interest include graph Laplacians and adjacency matrices, both of ”