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

arXiv: https://arxiv.org/abs/1404.6000 · HTML: https://mlsanity.com/paper/1404.6000/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Apr 2014.

## Built on by (most cited first, 17 of 17)

- [Community detection for weighted bipartite networks](https://mlsanity.com/paper/2109.10319/) (2021)
- [Robust Estimation for Random Graphs](https://mlsanity.com/paper/2111.05320/) (2021)
- [Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions](https://mlsanity.com/paper/2305.10227/) (2023)
- [Community Detection in the Stochastic Block Model by Mixed Integer Programming](https://mlsanity.com/paper/2101.12336/) (2021)
- [Hypothesis Testing for Equality of Latent Positions in Random Graphs](https://mlsanity.com/paper/2105.10838/) (2021)
- [A useful criterion on studying consistent estimation in community detection](https://mlsanity.com/paper/2109.14950/) (2021)
- [Semi-Supervised Clustering with Inaccurate Pairwise Annotations](https://mlsanity.com/paper/2104.02146/) (2021)
- [Directed degree corrected mixed membership model and estimating community memberships in directed networks](https://mlsanity.com/paper/2109.07826/) (2021)
- [A Worker-Task Specialization Model for Crowdsourcing: Efficient Inference and Fundamental Limits](https://mlsanity.com/paper/2111.12550/) (2021)
- [When Does Bottom-up Beat Top-down in Hierarchical Community Detection?](https://mlsanity.com/paper/2306.00833/) (2023)
- [Transfer Learning on Edge Connecting Probability Estimation under Graphon Model](https://mlsanity.com/paper/2510.05527/) (2025)
- [Projection-based QLP Algorithm for Efficiently Computing Low-Rank Approximation of Matrices](https://mlsanity.com/paper/2103.07245/) (2021)
- [Adversarial contamination of networks in the setting of vertex nomination: a new trimming method](https://mlsanity.com/paper/2208.09710/) (2022)
- [A Sublinear-Time Spectral Clustering Oracle with Improved Preprocessing Time](https://mlsanity.com/paper/2310.17878/) (2023)
- [Selecting the Number of Communities for Weighted Degree-Corrected Stochastic Block Models](https://mlsanity.com/paper/2406.05340/) (2024)
- [SubSearch: Robust Estimation and Outlier Detection for Stochastic Block Models via Subgraph Search](https://mlsanity.com/paper/2506.03657/) (2025)
- [Flexible Online Representation Learning Based on Similarity Matching](https://mlsanity.com/paper/2606.01546/) (2026)

## Abstract (arXiv)

Community detection, which aims to cluster N nodes in a given graph into r distinct groups based on the observed undirected edges, is an important problem in network data analysis. In this paper, the popular stochastic block model (SBM) is extended to the generalized stochastic block model (GSBM) that allows for adversarial outlier nodes, which are connected with the other nodes in the graph in an arbitrary way. Under this model, we introduce a procedure using convex optimization followed by k-means algorithm with k=r. Both theoretical and numerical properties of the method are analyzed. A theoretical guarantee is given for the procedure to accurately detect the communities with small misclassification rate under the setting where the number of clusters can grow with N. This theoretical result admits to the best-known result in the literature of computationally feasible community detection in SBM without outliers. Numerical results show that our method is both computationally fast and robust to different kinds of outliers, while some popular computationally fast community detection algorithms, such as spectral clustering applied to adjacency matrices or graph Laplacians, may fail to retrieve the major clusters due to a small portion of outliers. We apply a slight modification of our method to a political blogs data set, showing that our method is competent in practice and comparable to existing computationally feasible methods in the literature. To the best of the authors' knowledge, our result is the first in the literature in terms of clustering communities with fast growing numbers under the GSBM where a portion of arbitrary outlier nodes exist.