Estimation of the number of vertices of different degrees in a graph

The problem of estimating the numbers of vertices of different degrees in the unknown graph by using the sample information is considered and unbiased estimators are given and their variance-covariance matrix is shown to depend on a set of intrinsic graph parameters.

Abstract

An unknown graph is partially observed by selecting a vertex sample and observing the edges in the subgraph induced by the sample. The sample is selected by either simple random sampling or Bernoulli sampling. We consider the problem of estimating the numbers of vertices of different degrees in the unknown graph by using the sample information. Unbiased estimators are given and their variance-covariance matrix is shown to depend on a set of intrinsic graph parameters which can hardly be satisfactorily estimated from the sample information without further assumptions. In particular, the problem of estimating the number of isolates (vertices of degree zero) is considered in some detail.