Estimation of structural properties of online social networks at the extreme

Sampling is a commonly used technique for studying structural properties of online social networks (OSNs). Due to privacy, business, and performance concerns, OSN service providers impose limitations on data access for third parties. The implication of this practice is that one needs to come up with an applicable sampling scheme that can function under these limitations to efficiently estimate structural properties of interest. In this paper, we study how accurately some important properties of graphs can be estimated under a limited data access model. More specifically, we consider random neighbor access (RNA) model as a rather limited data access model in OSNs. In the RNA model, the only query available to get data from the studied graph is the random neighbor query which returns the id of a random neighbor for a given vertex id. We propose various sampling schemes and estimators for average degree and network size under the RNA model. We conduct extensive experiments on both real world OSN graphs and synthetic graphs (1) to measure the performance of the proposed estimators and (2) to identify the factors affecting the accuracy of our estimators. We find that while the average degree estimators can make accurate estimations with reasonable sample sizes despite the extreme data access limitations of the RNA model, network size estimators require quite large sample sizes for accurate estimations.