Community detection by L₀-penalized graph Laplacian
It is known that community detection algorithms in network analysis aims at partitioning nodes into disjoint communities. Many real networks often contain outlier nodes that do not belong to any community. They just loosely connect to other nodes in the network and they often do not have a known number of communities. However most recent algorithms assume that the number of communities is known and even fewer algorithms can handle networks with outliers and unknown community numbers. The aim of the present paper is to present a method of detecting communities by maximizing a novel model-free tightness criterion which is closely related with the \(L_0\)-penalized graph Laplacian. To this direction the authors managed to develop an efficient algorithm based on the alternating direction method of multiplier in order to maximize this penalized Laplacian. Unlike many other community detection methods this method does not assume that the number of communities is known and can properly detect communities in networks with outliers. Under the degree corrected stochastic block model the authors managed to show that even for networks with outliers the maximization of the tightness criterion can extract communities with small misclassification rates in the case that the number of communities grows to infinity as the network size grows. Furthermore simulation and real data analysis show that the proposed method performs significantly better than existing methods since it can computationally efficiently recover the community structure with high resolution and accuracy.
- 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
- 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
- scientific article; zbMATH DE number 2100602 (Why is no real title available?)
- 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
- The (un)supervised NMF methods for discovering overlapping communities as well as hubs and outliers in networks
- Network vector autoregression with individual effects
- Outlier detection in networks with missing links
- Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
- scientific article; zbMATH DE number 7255095 (Why is no real title available?)
- Spectral properties for the Laplacian of a generalized Wigner matrix
- Fused community detection
- Optimization via low-rank approximation for community detection in networks
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)
