Community detection in sparse random networks

DOI10.1214/14-AAP1080zbMath1326.05145arXiv1405.1478MaRDI QIDQ894814

Ery Arias-Castro, Nicolas Verzelen

Publication date: 24 November 2015

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

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

zbMATH Keywords

community detectionminimax hypothesis testingscan statisticErdős-Rényi random graphlargest connected componentdetecting a dense subgraphplanted subgraph problem

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Random graphs (graph-theoretic aspects) (05C80) Minimax procedures in statistical decision theory (62C20) Density (toughness, etc.) (05C42)

Related Items

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, Detection thresholds for the \(\beta\)-model on sparse graphs, Hypothesis testing in sparse weighted stochastic block model, Test dense subgraphs in sparse uniform hypergraph, 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, Testing correlation of unlabeled random graphs, Spectral clustering in the dynamic stochastic block model, Cliques in rank-1 random graphs: the role of inhomogeneity, Two-sample Hypothesis Testing for Inhomogeneous Random Graphs, Detecting a planted community in an inhomogeneous random graph, Optimality and sub-optimality of PCA. I: Spiked random matrix models, Detecting a botnet in a network, Sharp local minimax rates for goodness-of-fit testing in multivariate binomial and Poisson families and in multinomials, Computational barriers in minimax submatrix detection

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Belief propagation, robust reconstruction and optimal recovery of block models
• Optimal detection of sparse principal components in high dimension
• Community detection in sparse random networks
• Bayesian anomaly detection methods for social networks
• Counting connected graphs inside-out
• Moment inequalities for functions of independent random variables
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• Community detection in dense random networks
• Random Graphs and Complex Networks
• A nonparametric view of network models and Newman–Girvan and other modularities
• On the Limiting Distribution of a Graph Scan Statistic
• Almost all cubic graphs are Hamiltonian
• Almost all regular graphs are hamiltonian
• Community structure in social and biological networks
• Finding Hidden Cliques in Linear Time with High Probability
• Testing Statistical Hypotheses