Community detection by L₀-penalized graph Laplacian

DOI10.1214/18-EJS1445zbMATH Open1404.62067arXiv1706.10273MaRDI QIDQ1639201FDOQ1639201

Authors: Chong Chen, Ruibin Xi, Nan Lin 

Publication date: 12 June 2018

Published in: Electronic Journal of Statistics (Search for Journal in Brave)

Abstract: Community detection in network analysis aims at partitioning nodes in a network into $K$ disjoint communities. Most currently available algorithms assume that $K$ is known, but choosing a correct $K$ 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 $L_0$ penalty. Unlike most community detection methods, our method does not require a known $K$ 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.

Full work available at URL: https://arxiv.org/abs/1706.10273

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

zbMATH Keywords

consistencyoutliersocial networkspectral clusteringgene regulatory networkdegree corrected stochastic block modelmissclassification

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Multivariate analysis (62H99) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Social networks; opinion dynamics (91D30)

Cites Work

• A nonparametric view of network models and Newman–Girvan and other modularities
• Estimation and Prediction for Stochastic Blockstructures
• Spectral clustering and the high-dimensional stochastic blockmodel
• Pseudo-likelihood methods for community detection in large sparse networks
• Likelihood-based model selection for stochastic block models
• Consistency of community detection in networks under degree-corrected stochastic block models
• Consistency of spectral clustering in stochastic block models
• Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
• Title not available (Why is that?)
• Probability Inequalities for Sums of Bounded Random Variables
• Uncovering latent structure in valued graphs: a variational approach
• The eigenvalues of random symmetric matrices
• Fast community detection by SCORE
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Stochastic blockmodels with a growing number of classes
• Impact of regularization on spectral clustering

Cited In (7)

• Optimization via low-rank approximation for community detection in networks
• Title not available (Why is that?)
• Spectral properties for the Laplacian of a generalized Wigner matrix
• The (un)supervised NMF methods for discovering overlapping communities as well as hubs and outliers in networks
• 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)