mlsanityData to 7 Oct 2026

Dynamic Network Sampling for Community Detection

arXiv 2208.13921 ↗First posted 29 Aug 2022cs.SI math.ST stat.COcited by 0

Not on the map. Why?

Abstract (arXiv)

We propose a dynamic network sampling scheme to optimize block recovery for stochastic blockmodel (SBM) in the case where it is prohibitively expensive to observe the entire graph. Theoretically, we provide justification of our proposed Chernoff-optimal dynamic sampling scheme via the Chernoff information. Practically, we evaluate the performance, in terms of block recovery, of our method on several real datasets from different domains. Both theoretically and practically results suggest that our method can identify vertices that have the most impact on block structure so that one can only check whether there are edges between them to save significant resources but still recover the block structure.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 16 of its 39 references that are in the map. First posted on arXiv 29 Aug 2022.

Builds on

16 of 39 references.

References · 16

  1. 2019Multi-scale Attributed Node Embeddingcited by 543
  2. 2020Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Modelscited by 116
  3. 2016Community detection in networks: A user guidecited by 105
  4. 2017Statistical inference on random dot product graphs: a surveycited by 70
  5. 2017A statistical interpretation of spectral embedding: the generalised random dot product graphcited by 55
  6. 2014Covariate-assisted spectral clusteringcited by 29
  7. 2018On a 'Two Truths' Phenomenon in Spectral Graph Clusteringcited by 24
  8. 2013Perfect Clustering for Stochastic Blockmodel Graphs via Adjacency Spectral Embeddingcited by 23
  9. 2015Community Detection and Classification in Hierarchical Stochastic Blockmodelscited by 23
  10. 2016Limit theorems for eigenvectors of the normalized Laplacian for random graphscited by 17
  11. 2018Pairwise Covariates-adjusted Block Model for Community Detectioncited by 8
  12. 2014Community Detection via Random and Adaptive Samplingcited by 7
4 more
  1. 2019Vertex Nomination, Consistent Estimation, and Adversarial Modificationcited by 7
  2. 2019Spectral inference for large Stochastic Blockmodels with nodal covariatescited by 6
  3. 2020On spectral algorithms for community detection in stochastic blockmodel graphs with vertex covariatescited by 4
  4. 2016Likelihood Inference for Large Scale Stochastic Blockmodels with Covariates based on a Divide-and-Conquer Parallelizable Algorithm with Communicationcited by 3

Built on by

Not cited yet.