Estimating the Size of a Large Network and its Communities from a Random Sample

Area of Science:

• Network Science
• Statistical Modeling
• Computer Science

Background:

• Real-world networks are often too large for direct study.
• Estimating global network properties, like the number of nodes, is crucial across various fields.
• Existing methods for population size estimation in networks have limitations.

Purpose of the Study:

• To develop an efficient algorithm for estimating the total population size and community sizes in large networks.
• To address the challenge of inferring global network properties from partial data.
• To compare the proposed algorithm's performance against established methods.

Main Methods:

• Utilized the population random graph model from the stochastic block model (SBM) with K communities.
• Developed the PopULation Size Estimation (PULSE) algorithm.
• Conducted extensive experiments to evaluate PULSE using varying sample sizes, K, and SBM parameters.

Main Results:

• PULSE accurately estimates both the total population size and the size of individual communities.
• Experimental results demonstrate the algorithm's effectiveness across diverse scenarios.
• PULSE significantly outperforms the network scale-up estimator.

Conclusions:

• PULSE provides an accurate and efficient solution for estimating population size in large, complex networks.
• The algorithm is robust and performs well under various network conditions.
• This work offers a valuable tool for network analysis in computer science, epidemiology, and beyond.