Community detection in sparse random networks
From MaRDI portal
Publication:894814
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
community detection; minimax hypothesis testing; scan statistic; Erdős-Rényi random graph; largest connected component; detecting a dense subgraph; planted subgraph problem
05C82: Small world graphs, complex networks (graph-theoretic aspects)
05C80: Random graphs (graph-theoretic aspects)
62C20: Minimax procedures in statistical decision theory
05C42: Density (toughness, etc.)
Related Items
Test dense subgraphs in sparse uniform hypergraph, Asymptotic Theory of Eigenvectors for Random Matrices With Diverging Spikes, Testing correlation of unlabeled random graphs, Two-sample Hypothesis Testing for Inhomogeneous Random Graphs, Spectral clustering in the dynamic stochastic block model, Finding one community in a sparse graph, Community detection in sparse random networks, Detection thresholds for the \(\beta\)-model on sparse graphs, Optimality and sub-optimality of PCA. I: Spiked random matrix models, Detecting a planted community in an inhomogeneous random graph, Detecting a botnet in a network, Sharp local minimax rates for goodness-of-fit testing in multivariate binomial and Poisson families and in multinomials, Tensor clustering with planted structures: statistical optimality and computational limits, Uniform estimation in stochastic block models is slow, Computational barriers to estimation from low-degree polynomials, Hypothesis testing in sparse weighted stochastic block model, Statistical limits of spiked tensor models, Cliques in rank-1 random graphs: the role of inhomogeneity, Computational barriers in minimax submatrix detection, Sharp detection boundaries on testing dense subhypergraph
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item