  In this paper, we propose a new graph sampling method for online social
networks that achieves the following. First, a sample graph should reflect the
ratio between the number of nodes and the number of edges of the original
graph. Second, a sample graph should reflect the topology of the original
graph. Third, sample graphs should be consistent with each other when they are
sampled from the same original graph. The proposed method employs two
techniques: hierarchical community extraction and densification power law. The
proposed method partitions the original graph into a set of communities to
preserve the topology of the original graph. It also uses the densification
power law which captures the ratio between the number of nodes and the number
of edges in online social networks. In experiments, we use several real-world
online social networks, create sample graphs using the existing methods and
ours, and analyze the differences between the sample graph by each sampling
method and the original graph.
