A two-phase sampling algorithm for social networks

摘要

In recent years, the data used for analysis of social networks become very huge and restrictive so that it can be used an appropriate and small sampled network of original network for analysis goals. Sampling social network is referred to collect a small subgraph of original network with high property similarities between them. Due to important impact of sampling on the social network analyses, many algorithms have been proposed in the field of network sampling. In this paper, we propose a two-phase algorithm for sampling online social networks. At first phase, our algorithm iteratively constructs several set of minimum spanning trees (MST) of network. In the second phase, the proposed algorithm sorts vertices of MSTs and merge them to form a sampled network. Several simulation experiments are conducted to examine the performance of the proposed algorithm on different networks. The obtained results are compared with counterpart algorithms in terms of KS-test and ND-test. From the results, it can be observed that the proposed algorithm outperforms the existing algorithms.