Robust and computationally feasible community detection in the presence of arbitrary outlier nodes

DOI10.1214/14-AOS1290zbMath1328.62381arXiv1404.6000MaRDI QIDQ2352734

T. Tony Cai, Xiaodong Li

Publication date: 6 July 2015

Published in: The Annals of Statistics (Search for Journal in Brave)

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

zbMATH Keywords

SDP relaxation\(k\)-means clusteringdual certificaterobust community detection

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Clustering in the social and behavioral sciences (91C20)

Related Items (30)

Hierarchical Community Detection by Recursive Partitioning ⋮ Edgeworth expansions for network moments ⋮ All-in-one robust estimator of the Gaussian mean ⋮ Weighted Message Passing and Minimum Energy Flow for Heterogeneous Stochastic Block Models with Side Information ⋮ Community detection by \(L_{0}\)-penalized graph Laplacian ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Convexified modularity maximization for degree-corrected stochastic block models ⋮ Spectral clustering-based community detection using graph distance and node attributes ⋮ Community detection with structural and attribute similarities ⋮ Large volatility matrix analysis using global and national factor models ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Estimating mixed-memberships using the symmetric Laplacian inverse matrix ⋮ Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks ⋮ Vertex nomination, consistent estimation, and adversarial modification ⋮ Clustering heterogeneous financial networks ⋮ Outlier detection in networks with missing links ⋮ On semidefinite relaxations for the block model ⋮ Fusing data depth with complex networks: community detection with prior information ⋮ A Sparse Completely Positive Relaxation of the Modularity Maximization for Community Detection ⋮ Convex relaxation methods for community detection ⋮ Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing ⋮ Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees ⋮ Convex optimization for the densest subgraph and densest submatrix problems ⋮ Rate-optimal graphon estimation ⋮ Exact Clustering of Weighted Graphs via Semidefinite Programming ⋮ Covariate Regularized Community Detection in Sparse Graphs ⋮ Robust and computationally feasible community detection in the presence of arbitrary outlier nodes ⋮ Detecting Overlapping Communities in Networks Using Spectral Methods

Uses Software

• PhaseLift

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
• Pseudo-likelihood methods for community detection in large sparse networks
• Fast community detection by SCORE
• Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
• Guaranteed clustering and biclustering via semidefinite programming
• Spectral clustering and the high-dimensional stochastic blockmodel
• User-friendly tail bounds for sums of random matrices
• Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
• A note on an inequality involving the normal distribution
• The eigenvalues of random symmetric matrices
• Estimation and prediction for stochastic blockmodels for graphs with latent block structure
• Consistency of community detection in networks under degree-corrected stochastic block models
• Consistency of maximum-likelihood and variational estimators in the stochastic block model
• Consistency of spectral clustering in stochastic block models
• Role of normalization in spectral clustering for stochastic blockmodels
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Convex optimization for the planted \(k\)-disjoint-clique problem
• PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming
• Sparse Signal Recovery from Quadratic Measurements via Convex Programming
• A nonparametric view of network models and Newman–Girvan and other modularities
• Spectral redemption in clustering sparse networks
• Robust principal component analysis?
• Finding Planted Partitions in Random Graphs with General Degree Distributions
• Mixed membership stochastic blockmodels
• Mixture models and exploratory analysis in networks
• Estimation and Prediction for Stochastic Blockstructures
• Strong converse for identification via quantum channels
• Community structure in social and biological networks
• A Consistent Adjacency Spectral Embedding for Stochastic Blockmodel Graphs
• A Survey of Statistical Network Models
• Consistent Adjacency-Spectral Partitioning for the Stochastic Block Model When the Model Parameters Are Unknown
• Improved algorithms for the random cluster graph model
• Fundamentals of Computation Theory
• Spectral norm of random matrices

This page was built for publication: Robust and computationally feasible community detection in the presence of arbitrary outlier nodes