Community detection by L₀-penalized graph Laplacian
From MaRDI portal
Publication:1639201
Abstract: Community detection in network analysis aims at partitioning nodes in a network into disjoint communities. Most currently available algorithms assume that is known, but choosing a correct is generally very difficult for real networks. In addition, many real networks contain outlier nodes not belonging to any community, but currently very few algorithm can handle networks with outliers. In this paper, we propose a novel model free tightness criterion and an efficient algorithm to maximize this criterion for community detection. This tightness criterion is closely related with the graph Laplacian with penalty. Unlike most community detection methods, our method does not require a known and can properly detect communities in networks with outliers. Both theoretical and numerical properties of the method are analyzed. The theoretical result guarantees that, under the degree corrected stochastic block model, even for networks with outliers, the maximizer of the tightness criterion can extract communities with small misclassification rates even when the number of communities grows to infinity as the network size grows. Simulation study shows that the proposed method can recover true communities more accurately than other methods. Applications to a college football data and a yeast protein-protein interaction data also reveal that the proposed method performs significantly better.
Recommendations
- Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
- The (un)supervised NMF methods for discovering overlapping communities as well as hubs and outliers in networks
- A spectral method for community detection in moderately sparse degree-corrected stochastic block models
- Fused community detection
- Community detection in degree-corrected block models
Cites work
- scientific article; zbMATH DE number 2100602 (Why is no real title available?)
- A nonparametric view of network models and Newman–Girvan and other modularities
- Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
- Consistency of community detection in networks under degree-corrected stochastic block models
- Consistency of spectral clustering in stochastic block models
- Estimation and Prediction for Stochastic Blockstructures
- Fast community detection by SCORE
- Impact of regularization on spectral clustering
- Likelihood-based model selection for stochastic block models
- Probability Inequalities for Sums of Bounded Random Variables
- Pseudo-likelihood methods for community detection in large sparse networks
- Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
- Spectral clustering and the high-dimensional stochastic blockmodel
- Stochastic blockmodels with a growing number of classes
- The eigenvalues of random symmetric matrices
- Uncovering latent structure in valued graphs: a variational approach
Cited in
(7)- Optimization via low-rank approximation for community detection in networks
- scientific article; zbMATH DE number 7255095 (Why is no real title available?)
- The (un)supervised NMF methods for discovering overlapping communities as well as hubs and outliers in networks
- Spectral properties for the Laplacian of a generalized Wigner matrix
- Network vector autoregression with individual effects
- Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
- Fused community detection
This page was built for publication: Community detection by \(L_{0}\)-penalized graph Laplacian
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1639201)
