Estimating the number of connected components in a graph via subgraph sampling (Q2174974)

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.