Estimating the Size of a Large Network and its Communities from a Random Sample
Most real-world networks are too large to be measured or studied directly and there is substantial interest in estimating global network properties from smaller sub-samples. One of the most important global properties is the number of vertices/nodes in the network. Estimating the number of vertices in a large network is a major challenge in computer science, epidemiology, demography, and intelligence analysis. In this paper we consider a population random graph G = (V, E) from the stochastic block model (SBM) with K communities/blocks. A sample is obtained by randomly choosing a subset W ⊆ V and letting G(W ) be the induced subgraph in G of the vertices in W . In addition to G(W ), we observe the total degree of each sampled vertex and its block membership. Given this partial information, we propose an efficient PopULation Size Estimation algorithm, called PULSE, that accurately estimates the size of the whole population as well as the size of each community. To support our theoretical analysis, we perform an exhaustive set of experiments to study the effects of sample size, K, and SBM model parameters on the accuracy of the estimates. The experimental results also demonstrate that PULSE significantly outperforms a widely-used method called the network scale-up estimator in a wide variety of scenarios.
The article "Estimating the Size of a Large Network and its Communities from a Random Sample" considers the problem of estimating the total number of vertices in a network given the subsample of the network and full degrees of the vertices in the subsample. The authors propose the algorithm which uses the stochastic block model (SBM) approximation of the network to estimate the number of vertices in each block and subsequently in the full network. The properties of the algorithm are demonstrated on a series of examples on model data.
The main idea of the article is to improve the estimation of the size of a network based on considering the SBM model instead of Erdos-Renyi model, which is considered in the baseline algorithm. This is a natural approach, which however leads to significant complications as a resultive likelihood is costly to evaluate due to massive summation. The authors overcome the problem by considering the joint posterior and sampling from this posterior via Gibbs sampling.  The general approach seems fair, however the computational limitations of the algorithm are not considered and it is not evident whether the algorithm achieves the goal of mimicking the respective distribution. I should note, that the theorems provided are stated as one of the main results of work, but in fact don't add significant value to the algorithm and the results. The first theorem states finite sample bias in the basic estimate, however finite sample unbiasness of the proposed algorithm is not showed. The second theorem states the tractability of obtained posterior, however the properties of the obtained algorithm itself are not theoretically accessed.  The experimental part seems to be proper comparison of two algorithms on different variants of model data, however no experiments on real data are considered. Real data is very important as any model for this data is an approximation, which for the SBM case will mean the necessity of choosing some number of blocks K. It is of interest to consider the work of the algorithm on the real data, especially considering that it is quite easy to perform the experiment on any type of real network just by sampling a part of it.  To sum up, I think that the paper presents a good effort in the interesting research direction, however theoretical results seem to be not supportive for the algorithm (while are underlined as important) and experimental part needs significant improvement.