Search

The stochastic block model is one of the most studied network models for community detection, and fitting its likelihood function on large-scale networks is known to be challenging. One prominent work that overcomes this computational challenge is the fast pseudo-likelihood approach proposed by Amini et al. for fitting stochastic block models to large sparse networks. However, this approach does not have convergence guarantee, and may not be well suited for small and medium scale networks. In this article, we propose a novel likelihood based approach that decouples row and column labels in the likelihood function, enabling a fast alternating maximization. This new method is computationally efficient, performs well for both small- and large-scale networks, and has provable convergence guarantee. We show that our method provides strongly consistent estimates of communities in a stochastic block model. We further consider extensions of our proposed method to handle networks with degree heterogeneity and bipartite properties. for this article are available online. [ABSTRACT FROM AUTHOR]

The stochastic block model (SBM) is widely employed as a canonical model for network community detection. Recovering community labels under SBM is not a trivial task, since its theoretical optimization problem is NP‐hard. To solve this problem, numerous statistical methods have been developed in the literature, most of which are, however, not applicable to large‐scale networks. To overcome this limitation, in this paper, we propose a split likelihood (SL) framework, under which we provide a fast converging algorithm, named the SL algorithm, with significant advantages in terms of both community detection accuracy and computational efficiency. Moreover, to deal with networks with hub nodes or those with substantial degrees of variation within communities, we develop a variant of the SL algorithm, named the conditional SL (CSL) algorithm. We present the computational and statistical properties of the proposed algorithm. Then, we demonstrate the superiority of the proposed methods through a large amount of numerical experiments as well as two empirical analyses on real‐world networks. [ABSTRACT FROM AUTHOR]

Multi‐layer networks are often used to represent multiple types of relationships between nodes in network studies. In this paper, we investigate the community detection problem in multi‐layer networks. Specifically, we consider the multi‐layer stochastic block model (MLSBM), which assumes that the community memberships are shared across all network layers, while other model parameters can be different between different layers. Variational methods have been developed to fit the MLSBM, but they do not scale well to very large networks. Inspired by the iterative pseudo‐likelihood maximization strategy for single networks, we develop a pseudo‐likelihood based algorithm to fit the MLSBM and estimate the community labels, and we also extend the proposed algorithm to the degree‐corrected case to deal with degree heterogeneity. The proposed algorithms are fast and can cope with multi‐layer networks with up to millions of nodes. The advantages of the proposed methods in both community detection and computational efficiency are demonstrated by numerical studies. [ABSTRACT FROM AUTHOR]