Estimating the number of connected components in a graph via subgraph sampling
From MaRDI portal
Publication:2174974
Abstract: Learning properties of large graphs from samples has been an important problem in statistical network analysis since the early work of Goodman cite{Goodman1949} and Frank cite{Frank1978}. We revisit a problem formulated by Frank cite{Frank1978} of estimating the number of connected components in a large graph based on the subgraph sampling model, in which we randomly sample a subset of the vertices and observe the induced subgraph. The key question is whether accurate estimation is achievable in the emph{sublinear} regime where only a vanishing fraction of the vertices are sampled. We show that it is impossible if the parent graph is allowed to contain high-degree vertices or long induced cycles. For the class of chordal graphs, where induced cycles of length four or above are forbidden, we characterize the optimal sample complexity within constant factors and construct linear-time estimators that provably achieve these bounds. This significantly expands the scope of previous results which have focused on unbiased estimators and special classes of graphs such as forests or cliques. Both the construction and the analysis of the proposed methodology rely on combinatorial properties of chordal graphs and identities of induced subgraph counts. They, in turn, also play a key role in proving minimax lower bounds based on construction of random instances of graphs with matching structures of small subgraphs.
For estimating properties of graphs, a certain set of vertices is sampled, where different sampling models, e.g. uniform and Bernoulli sampling models are considered. Inspecting then the induced subgraphs, information about the graph under consideration can be obtained. Here, this statistical method is used to estimate the number of connected components of a graph, e.g. for estimating the connectivity of a network. Minimax risk estimators are applied especially to chordal graphs and forests, cliques. Based on the parameters of the graph, main results of the work concern the minimal sample size to reach a given accuracy of the obtained estimates.
Recommendations
Cites work
- A Generalization of Sampling Without Replacement From a Finite Universe
- A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
- Algorithmic Aspects of Vertex Elimination on Graphs
- An Exponential Family of Probability Distributions for Directed Graphs
- Analysis of Boolean Functions
- Approximately counting triangles in sublinear time
- Approximating average parameters of graphs
- Approximating the Minimum Spanning Tree Weight in Sublinear Time
- Chordal graphs and the characteristic polynomial
- Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
- Estimating graph parameters via random walks with restarts
- Estimating the number of connected components in a graph via subgraph sampling
- Estimating the number of connected components in sublinear time
- scientific article; zbMATH DE number 3168330 (Why is no real title available?)
- scientific article; zbMATH DE number 3722700 (Why is no real title available?)
- scientific article; zbMATH DE number 3790470 (Why is no real title available?)
- scientific article; zbMATH DE number 3558711 (Why is no real title available?)
- scientific article; zbMATH DE number 3606505 (Why is no real title available?)
- scientific article; zbMATH DE number 854567 (Why is no real title available?)
- scientific article; zbMATH DE number 3273551 (Why is no real title available?)
- scientific article; zbMATH DE number 3392507 (Why is no real title available?)
- Introduction to nonparametric estimation
- Introduction to Property Testing
- Large deviations for sums of partly dependent random variables
- Large networks and graph limits
- Lower bounds for the probability of a union via chordal graphs
- Modeling social networks from sampled data
- On testing expansion in bounded-degree graphs
- On the Estimation of the Number of Classes in a Population
- Optimal prediction of the number of unseen species
- Property testing and its connection to learning and approximation
- Rate-optimal graphon estimation
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Snowball Sampling
- Statistical analysis of network data. Methods and models
- Subgraph counting identities and Ramsey numbers
- Sublinear-time algorithms for counting star subgraphs via edge sampling
- Topics at the Frontier of Statistics and Network Analysis
- Unique entity estimation with application to the Syrian conflict
Cited in
(12)- Sublinear-time algorithms for counting star subgraphs via edge sampling
- A statistical framework for modern network science
- Motif estimation via subgraph sampling: the fourth-moment phenomenon
- Estimating the number of connected components in a graph via subgraph sampling
- Estimating the number of connected components in sublinear time
- Edge estimation in the population of a binary tree using node-sampling
- Tight Bounds on Vertex Connectivity Under Sampling
- Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs
- Estimating global subgraph counts by sampling
- Estimation of spanning tree mean-edge using node sampling
- Sequential stratified regeneration: \textit{MCMC} for large state spaces with an application to subgraph count estimation
- Subsampling bootstrap of count features of networks
This page was built for publication: Estimating the number of connected components in a graph via subgraph sampling
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2174974)
