Estimating the number of connected components in a graph via subgraph sampling
From MaRDI portal
Publication:2174974
DOI10.3150/19-BEJ1147zbMath1440.62043arXiv1801.04339MaRDI QIDQ2174974
Publication date: 27 April 2020
Published in: Bernoulli (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1801.04339
number of connected componentsestimation methodschordal graphs forests cliquesvertex sampling subgraph counts
Applications of graph theory (05C90) Sampling theory, sample surveys (62D05) Minimax procedures in statistical decision theory (62C20)
Related Items
Motif estimation via subgraph sampling: the fourth-moment phenomenon, Estimating the number of connected components in a graph via subgraph sampling, A statistical framework for modern network science
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Rate-optimal graphon estimation
- Lower bounds for the probability of a union via chordal graphs
- Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
- Modeling social networks from sampled data
- Statistical analysis of network data. Methods and models
- Subgraph counting identities and Ramsey numbers
- Unique entity estimation with application to the Syrian conflict
- Sublinear-time algorithms for counting star subgraphs via edge sampling
- Chordal graphs and the characteristic polynomial
- Estimating the number of connected components in a graph via subgraph sampling
- Estimating the number of connected components in sublinear time
- On Testing Expansion in Bounded-Degree Graphs
- Property testing and its connection to learning and approximation
- Snowball Sampling
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Approximating average parameters of graphs
- An Exponential Family of Probability Distributions for Directed Graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
- Approximately Counting Triangles in Sublinear Time
- Optimal prediction of the number of unseen species
- Large deviations for sums of partly dependent random variables
- Analysis of Boolean Functions
- Approximating the Minimum Spanning Tree Weight in Sublinear Time
- Introduction to Property Testing
- Topics at the Frontier of Statistics and Network Analysis
- On the Estimation of the Number of Classes in a Population
- A Generalization of Sampling Without Replacement From a Finite Universe
- Introduction to nonparametric estimation
