Large Graph Sampling

Sampling Large Scale Complex Systems
Studying structural and functional characteristics of large scale graphs (or networks) has been a challenging task due to the related computational overhead. Hence, most studies consult to sampling to gather necessary information to estimate various features of these big networks. On the other hand, using a best effort approach to graph sampling within the constraints of an application domain may not always produce accurate estimates. In fact, the mismatch between the characteristics of interest and the utilized network sampling methodology may result in incorrect inferences about the studied characteristics of the underlying system. In this project we investigate the sources of information loss in a sampling process; identify the fundamental factors that need to be carefully considered in a sampling design; demonstrate the mismatch between the sampling design and graph characteristics of interest; and develop alternative estimators for various characteristics of different graph types.