A spanning tree approach to social network sampling with degree constraints

Abstract

Online social networks (OSNs) have become increasingly popular on the web in recent years. There are millions of users on these networks, and they generate a great deal of interaction among them. Network sampling is often used to study and measure OSNs, which produce a small, accessible network with a limited number of edges and nodes. In this paper, two algorithms are proposed to sample OSNs. The first algorithm finds several spanning trees with the highest number of nodes that satisfy a given degree constraint from randomly chosen root nodes; edges and nodes of computed spanning trees are ranked based on how often they appear in them. Finally, a fraction of the highly ranked nodes and edges are considered in the sampled network. Second, a partial spanning tree algorithm is proposed in place of a full spanning tree algorithm to improve the performance of the first algorithm. We conduct several experiments on well-known real networks to determine the performance of the proposed sampling algorithms. As a result of the experiments, the proposed algorithms outperformed some of the baseline and recently presented algorithms in terms of the Kolmogorov-Smirnov (KS) test, Skew Divergence (SD) distance, and Normalized Distance (ND).