Community detection in sparse random networks

DOI10.1214/14-AAP1080zbMATH Open1326.05145arXiv1405.1478MaRDI QIDQ894814FDOQ894814

Authors: Nicolas Verzelen, Ery Arias-Castro 

Publication date: 24 November 2015

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

Abstract: We consider Gaussian mixture models in high dimensions and concentrate on the twin tasks of detection and feature selection. Under sparsity assumptions on the difference in means, we derive information bounds and establish the performance of various procedures, including the top sparse eigenvalue of the sample covariance matrix and other projection tests based on moments, such as the skewness and kurtosis tests of Malkovich and Afifi (1973), and other variants which we were better able to control under the null.

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

Recommendations

• Community detection in dense random networks
• Community detection in the sparse hypergraph stochastic block model
• Finding one community in a sparse graph
• Detecting a planted community in an inhomogeneous random graph
• Detection thresholds for the \(\beta\)-model on sparse graphs

zbMATH Keywords

community detectionminimax hypothesis testingscan statisticlargest connected componentdetecting a dense subgraphplanted subgraph problemErdős-Rényi random graph

Mathematics Subject Classification ID

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

Cites Work

• A nonparametric view of network models and Newman–Girvan and other modularities
• Testing Statistical Hypotheses
• Random graphs and complex networks. Volume 1
• Belief propagation, robust reconstruction and optimal recovery of block models
• Community structure in social and biological networks
• Community detection in dense random networks
• Finding hidden cliques in linear time
• Title not available (Why is that?)
• Optimal detection of sparse principal components in high dimension
• Title not available (Why is that?)
• Finding hidden cliques in linear time with high probability
• Community detection in sparse random networks
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• Moment inequalities for functions of independent random variables
• Title not available (Why is that?)
• Almost all regular graphs are hamiltonian
• Almost all cubic graphs are Hamiltonian
• Bayesian anomaly detection methods for social networks
• Counting connected graphs inside-out
• Title not available (Why is that?)
• On the limiting distribution of a graph scan statistic
• Title not available (Why is that?)

Cited In (39)

• Computing exact \(p\)-values for community detection
• Testing correlation of unlabeled random graphs
• Optimization via low-rank approximation for community detection in networks
• Sharp local minimax rates for goodness-of-fit testing in multivariate binomial and Poisson families and in multinomials
• Statistical limits of spiked tensor models
• Identifying Community Structures from Network Data via Maximum Likelihood Methods
• Test dense subgraphs in sparse uniform hypergraph
• Community detection in the sparse hypergraph stochastic block model
• Computational barriers in minimax submatrix detection
• Tensor clustering with planted structures: statistical optimality and computational limits
• Hypothesis testing in sparse weighted stochastic block model
• The k-Dense Method to Extract Communities from Complex Networks
• Community detection on Euclidean random graphs
• CONCENTRATION OF RANDOM GRAPHS AND APPLICATION TO COMMUNITY DETECTION
• Uniform estimation in stochastic block models is slow
• Community detection in dense random networks
• Detecting a botnet in a network
• Computational barriers to estimation from low-degree polynomials
• Detection thresholds for the \(\beta\)-model on sparse graphs
• Concentration and stability of community-detecting functions on random networks
• Detecting a planted community in an inhomogeneous random graph
• The Small Community Phenomenon in Networks: Models, Algorithms and Applications
• Bounded Arboricity to Determine the Local Structure of Sparse Graphs
• Parameter Estimators of Sparse Random Intersection Graphs with Thinned Communities
• Cliques in rank-1 random graphs: the role of inhomogeneity
• Average Jaccard index of random graphs
• Title not available (Why is that?)
• Sharp detection boundaries on testing dense subhypergraph
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
• Probabilistic Community Detection With Unknown Number of Communities
• Spectral clustering in the dynamic stochastic block model
• Heterogeneous dense subhypergraph detection
• Two-sample hypothesis testing for inhomogeneous random graphs
• Title not available (Why is that?)
• How robust are reconstruction thresholds for community detection?
• Asymptotic Theory of Eigenvectors for Random Matrices With Diverging Spikes
• Optimality and sub-optimality of PCA. I: Spiked random matrix models
• Finding one community in a sparse graph
• Community detection in sparse random networks

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q894814)