Estimation of Number of Communities in Assortative Sparse Networks
Most community detection algorithms assume the number of communities, K, to be known a priori. Of the various approaches that have been proposed to estimate K, the non-parametric method based on the spectral properties of the Bethe Hessian matrix has garnered much popularity for its simplicity, computational efficiency, and robustness to sparsity of data. Recently, its consistency for networks in semi-dense regimes with the expected degree greater than log(N) has been shown (N being the number of nodes in the network). In this paper, we show that the spectral method based on the Bethe Hessian matrix is in fact also consistent in sparse regimes with expected degree lesser than log(N) at any rate, thus establishing it as a method which is robust to a wide range of problem settings, regardless of the sparsity of networks.
Code (0)
등록된 구현이 없습니다.
Tasks
Community DetectionComputational EfficiencySimilar Papers 제목 키워드 기반
Detecting Latent Communities in Network Formation Models
This paper proposes a logistic undirected network formation model which allows for assortative matching on observed individual characteristics and the presence of edge-wise fixed effects. We model the coefficients of obs…
ClusteringregressionAssortative-Constrained Stochastic Block Models
Stochastic block models (SBMs) are often used to find assortative community structures in networks, such that the probability of connections within communities is higher than in between communities. However, classic SBMs…
Community DetectionStochastic Block ModelEfficient Online Inference for Bayesian Nonparametric Relational Models
Stochastic block models characterize observed network relationships via latent community memberships. In large social networks, we expect entities to participate in multiple communities, and the number of communities to …
Link PredictionVariational InferenceStatistical inference of assortative community structures
We develop a principled methodology to infer assortative communities in networks based on a nonparametric Bayesian formulation of the planted partition model. We show that this approach succeeds in finding statistically …
Community DetectionModel SelectionStochastic Block ModelMultilayer hypergraph clustering using the aggregate similarity matrix
We consider the community recovery problem on a multilayer variant of the hypergraph stochastic block model (HSBM). Each layer is associated with an independent realization of a d-uniform HSBM on N vertices. Given the si…
ClusteringStochastic Block Model