Community detection in dense random networks

DOI10.1214/14-AOS1208zbMath1305.62035arXiv1302.7099MaRDI QIDQ2510823

Nicolas Verzelen, Ery Arias-Castro

Publication date: 4 August 2014

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

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

zbMATH Keywords

community detectionminimax hypothesis testingscan statisticErdős-Rényi random graphplanted clique problemdetecting a dense subgraphsparse eigenvalue problemdense \(k\)-subgraph problem

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Hypothesis testing in multivariate analysis (62H15) Minimax procedures in statistical decision theory (62C20) Detection theory in information and communication theory (94A13)

Related Items (34)

Tensor clustering with planted structures: statistical optimality and computational limits ⋮ Asymptotic Theory of Eigenvectors for Random Matrices With Diverging Spikes ⋮ Uniform estimation in stochastic block models is slow ⋮ Computational barriers to estimation from low-degree polynomials ⋮ Stability and minimax optimality of tangential Delaunay complexes for manifold reconstruction ⋮ Unnamed Item ⋮ Hypothesis testing in sparse weighted stochastic block model ⋮ Test dense subgraphs in sparse uniform hypergraph ⋮ Distribution-free detection of a submatrix ⋮ Statistical limits of spiked tensor models ⋮ Sharp detection boundaries on testing dense subhypergraph ⋮ Finding one community in a sparse graph ⋮ Community detection in sparse random networks ⋮ Power enhancement and phase transitions for global testing of the mixed membership stochastic block model ⋮ Testing correlation of unlabeled random graphs ⋮ Statistical proof? The problem of irreproducibility ⋮ Statistical and computational limits for sparse matrix detection ⋮ Spectral clustering in the dynamic stochastic block model ⋮ Parallel tempering for the planted clique problem ⋮ Statistical inference on random dot product graphs: a survey ⋮ Optimal testing for planted satisfiability problems ⋮ Distribution-Free, Size Adaptive Submatrix Detection with Acceleration ⋮ Recovering a hidden community beyond the Kesten–Stigum threshold in O(|E|log^*|V|) time ⋮ Cliques in rank-1 random graphs: the role of inhomogeneity ⋮ Two-sample Hypothesis Testing for Inhomogeneous Random Graphs ⋮ Community detection in dense random networks ⋮ Detecting a planted community in an inhomogeneous random graph ⋮ Optimality and sub-optimality of PCA. I: Spiked random matrix models ⋮ Testing for high-dimensional geometry in random graphs ⋮ Network Modularity in the Presence of Covariates ⋮ Testing degree corrections in stochastic block models ⋮ Detecting a botnet in a network ⋮ Unnamed Item ⋮ Sharp local minimax rates for goodness-of-fit testing in multivariate binomial and Poisson families and in multinomials

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Innovated higher criticism for detecting sparse signals in correlated noise
• Optimal detection of sparse principal components in high dimension
• The method of moments and degree distributions for network models
• Global testing under sparse alternatives: ANOVA, multiple comparisons and the higher criticism
• Bayesian anomaly detection methods for social networks
• Some problems of hypothesis testing leading to infinitely divisible distributions
• Higher criticism for detecting sparse heterogeneous mixtures.
• Detection boundary in sparse regression
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• Community detection in dense random networks
• Detection of a signal of known shape in a multichannel system
• Linear degree extractors and the inapproximability of max clique and chromatic number
• A nonparametric view of network models and Newman–Girvan and other modularities
• Statistical mechanics of complex networks
• Emergence of Scaling in Random Networks
• Optimal Detection of Heterogeneous and Heteroscedastic Mixtures
• On Finding Dense Subgraphs
• A spatial scan statistic
• Community structure in social and biological networks
• Finding Hidden Cliques in Linear Time with High Probability
• Testing Statistical Hypotheses
• Statistical algorithms and a lower bound for detecting planted cliques
• A Direct Formulation for Sparse PCA Using Semidefinite Programming
• Introduction to nonparametric estimation
• The dense \(k\)-subgraph problem

This page was built for publication: Community detection in dense random networks