Abstract: Using random sampling algorithm to sample the social network can not represent the original network well. In order to solve the problem, a new algorithm based on the Dijkstra shortest path algorithm was proposed. Firstly, the Dijkstra algorithm was used to sample the shortest path between nodes in social network repeatedly. Then, the frequencies of edges in the extracted path were ordered, and the edges with the higher frequencies were selected to compose the sampling subgraph. The proposed algorithm solved some problems existing in the random sampling algorithm and achieved a good function of extraction of social network. The simulation experimental results show that the proposed sampling algorithm has less error and reflect the original network better than random sampling method.

Key words: social network, network sampling, Dijkstra algorithm, clustering coefficient

摘要： 针对社交网络中随机抽样算法抽样结果不能很好地代表原始网络的问题,设计了一种基于Dijkstra最短路径的抽样算法。首先,利用Dijkstra算法多次抽取社交网络中节点之间的最短路径;然后,对抽取到的路径中边出现的频率进行排序,选择较高频率的边组成抽样的子图。该算法解决了随机抽样算法存在的一些问题,实现了较好的生成抽取社交网络的功能。仿真实验结果表明,与随机抽样方法相比,所提抽样算法能减少抽样误差,更好地反映原始网络。

关键词: 社交网络, 网络抽样, Dijkstra算法, 聚类系数