Community detection in dense random networks
From MaRDI portal
Abstract: We formalize the problem of detecting a community in a network into testing whether in a given (random) graph there is a subgraph that is unusually dense. We observe an undirected and unweighted graph on N nodes. Under the null hypothesis, the graph is a realization of an Erd"os-R'enyi graph with probability p0. Under the (composite) alternative, there is a subgraph of n nodes where the probability of connection is p1 > p0. We derive a detection lower bound for detecting such a subgraph in terms of N, n, p0, p1 and exhibit a test that achieves that lower bound. We do this both when p0 is known and unknown. We also consider the problem of testing in polynomial-time. As an aside, we consider the problem of detecting a clique, which is intimately related to the planted clique problem. Our focus in this paper is in the quasi-normal regime where n p0 is either bounded away from zero, or tends to zero slowly.
Recommendations
- Community detection in sparse random networks
- Detecting a planted community in an inhomogeneous random graph
- Sharp detection boundaries on testing dense subhypergraph
- Hypothesis testing for automated community detection in networks
- The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
Cites work
- A Direct Formulation for Sparse PCA Using Semidefinite Programming
- A nonparametric view of network models and Newman–Girvan and other modularities
- A spatial scan statistic
- Bayesian anomaly detection methods for social networks
- Community detection in dense random networks
- Community structure in social and biological networks
- Detection boundary in sparse regression
- Detection of a signal of known shape in a multichannel system
- Detection of a sparse submatrix of a high-dimensional noisy matrix
- Emergence of Scaling in Random Networks
- Finding hidden cliques in linear time
- Finding hidden cliques in linear time with high probability
- Global testing under sparse alternatives: ANOVA, multiple comparisons and the higher criticism
- Higher criticism for detecting sparse heterogeneous mixtures.
- scientific article; zbMATH DE number 3571502 (Why is no real title available?)
- scientific article; zbMATH DE number 1380608 (Why is no real title available?)
- Innovated higher criticism for detecting sparse signals in correlated noise
- Introduction to nonparametric estimation
- Linear degree extractors and the inapproximability of max clique and chromatic number
- On Finding Dense Subgraphs
- Optimal detection of heterogeneous and heteroscedastic mixtures
- Optimal detection of sparse principal components in high dimension
- Random graphs.
- Some problems of hypothesis testing leading to infinitely divisible distributions
- Statistical algorithms and a lower bound for detecting planted cliques
- Statistical mechanics of complex networks
- Testing Statistical Hypotheses
- The dense \(k\)-subgraph problem
- The method of moments and degree distributions for network models
Cited in
(72)- Two-sample hypothesis testing for inhomogeneous random graphs
- Stability and minimax optimality of tangential Delaunay complexes for manifold reconstruction
- Community detection in degree-corrected block models
- Optimality and sub-optimality of PCA. I: Spiked random matrix models
- Computing exact \(p\)-values for community detection
- Detecting a planted community in an inhomogeneous random graph
- Testing degree corrections in stochastic block 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
- Testing community structure for hypergraphs
- 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
- Statistical and computational limits for sparse matrix detection
- Phase transitions in normalized cut of social networks
- Optimal testing for planted satisfiability problems
- Cliques in rank-1 random graphs: the role of inhomogeneity
- Distribution-free detection of a submatrix
- Detection of an anomalous cluster in a network
- Community detection in dense random networks
- Sharp detection boundaries on testing dense subhypergraph
- Network refinement: denoising complex networks for better community detection
- Concentration and stability of community-detecting functions on random networks
- Testing for high-dimensional geometry in random graphs
- Subgraph detection
- Parallel tempering for the planted clique problem
- scientific article; zbMATH DE number 7234180 (Why is no real title available?)
- Identifying Community Structures from Network Data via Maximum Likelihood Methods
- The k-Dense Method to Extract Communities from Complex Networks
- Statistical inference on random dot product graphs: a survey
- Statistical proof? The problem of irreproducibility
- Detecting communities is hard (and counting them is even harder)
- Recovering a hidden community beyond the Kesten-Stigum threshold in \(O(| E|\log^\ast| V|)\) time
- The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
- scientific article; zbMATH DE number 7255095 (Why is no real title available?)
- Test dense subgraphs in sparse uniform hypergraph
- Distribution-free, size adaptive submatrix detection with acceleration
- CONCENTRATION OF RANDOM GRAPHS AND APPLICATION TO COMMUNITY DETECTION
- Statistical guarantees for local graph clustering
- Probabilistic Community Detection With Unknown Number of Communities
- Network modularity in the presence of covariates
- Algorithms and Models for the Web-Graph
- How robust are reconstruction thresholds for community detection?
- Community detection via a triangle and edge combination conductance partitioning
- Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning
- Asymptotic Theory of Eigenvectors for Random Matrices With Diverging Spikes
- Power enhancement and phase transitions for global testing of the mixed membership stochastic block model
- Testing correlation of unlabeled random graphs
- Special invited paper: the SCORE normalization, especially for heterogeneous network and text data
- Community Detection in Partial Correlation Network Models
- Average Jaccard index of random graphs
- Heterogeneous dense subhypergraph detection
- Spectral clustering in the dynamic stochastic block model
- The low-degree hardness of finding large independent sets in sparse random hypergraphs
- Optimal and exact recovery on the general nonuniform hypergraph stochastic block model
- Counting stars is constant-degree optimal for detecting any planted subgraph
- Degree of balance in random signed graphs
- Information-theoretic limits for testing community structures in weighted networks
- Optimal Network Pairwise Comparison
- Sharp thresholds in inference of planted subgraphs
- Almost-linear planted cliques elude the Metropolis process
- Testing common degree-correction parameters of multilayer networks
- Detection of dense subhypergraphs by low-degree polynomials
- Analysis of singular subspaces under random perturbations
- Testing for latent structure via the Wilcoxon-Wigner random matrix of normalized rank statistics
- Functional central limit theorem for the principal eigenvalue of dynamic Erdős-Rényi random graphs
- Localized geometry detection in scale-free random graphs
- New methods for testing community structures in general networks
- Finding one community in a sparse graph
- Community detection in sparse random networks
This page was built for publication: Community detection in dense random networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2510823)
