社交网络子图采样算法

Subgraph Sampling Algorithm of Social Network

摘要: 在线社交网络(Online Social Networks, OSNs)数据量庞大，如何以低成本采样获取具有代表性的子图成为当前一个研究热点。现有的大部分采样算法仅仅体现在样本列表的无偏特性上，很多情况下，其采样样本构造的诱导子图难以代表原图结构。本文对各种类型的OSN提出了一种新的采样方法，该算法在原有的随机游走算法基础上重新计算了采样跳转概率，修正采样诱导子图的偏差，使其能够更出色地代表原图。同时，本文的采样算法通过计算权重的方式采集邻接节点，省去了自循环过程，从而大幅度提高了采样效率。实验结果表明，本论文提出的采样算法在度分布、聚类系数、传递性、同配性各个方面综合对比，采样获取的子图更加接近原图的属性结构。最后，该算法在大多数情况下，其性能与表现均优于现有采样算法。

Abstract: Online Social Networks (OSNs) maintain a huge amount of data, and how to sample the most representative subgraphs at a lower cost becomes an important research topic. Most of the existing sampling algorithms are only embodied in the unbiased characteristics of the sample list. In many cases, the induced subgraphs constructed from the sampled samples are difficult to represent the original graph structure. This paper proposes a new sampling method for various types of OSNs. This algorithm recalculates the sampling jump probability on the basis of the original random walk algorithm, and corrects the deviation of the sampling-induced subgraph, as a result, it can better represent the original graph. At the same time, the sampling algorithm in this paper collects the adjacent nodes by calculating the weight, eliminating the self-circulation process and greatly improving the sampling efficiency. The experimental results show that the sampling algorithm proposed in this paper is more close to the original image attribute structure in terms of degree distribution, cluster, transitivity, and assortativity. Finally, in most cases, the algorithm perfects better than the existing sampling algorithm.