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 originalnetwork for analysis goals. Sampling social network is referred to collect a small subgraph of original network with high propertysimilarities 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, wepropose a two-phase algorithm for sampling online social networks. At first phase, our algorithm iteratively constructsseveral set of minimum spanning trees (MST) of network. In the second phase, the proposed algorithm sorts vertices of MSTs andmerge them to form a sampled network. Several simulation experiments are conducted to examine the performance of the proposed algorithm on different networks. The obtained resultsare compared with counterpart algorithms in terms of KS-test and ND-test. From the results, it can be observed that theproposed algorithm outperforms the existing algorithms.

Keywords:

online social networks , social network analysis , network sampling , spanning tree