基于在线社交网络的JPS跳跃并行顶点采样方法

JPS Jump Parallel Vertex Sampling Method Based on Online Social Network

针对现有在线社交网络(OSNs)采样方法无法有效地应用于低连通性的社交网络,且采集的样本顶点平均度严重偏离原始社交网络、顶点过度采样等问题,本文基于蒙特卡罗随机游走(MHRW)采样方法,引入双重跳跃策略、并行机制和顶点缓存区,提出一种跳跃无偏并行顶点(JPS)采样方法。将在线社交网络数据集建模为包含顶点和边的社交图进行模拟采样,利用Python/Matplotlib绘图库绘制采集的样本顶点属性图。实验结果表明,该采样方法更有效地应用于不同连通强度的社交图,提高了采样过程中的顶点更新率,降低了样本顶点的平均度偏差且能够更快速地收敛。

In view of problems that the existing online social networks(OSNs)sampling methods cannot be effectively applied to low connectivity social networks,and the average degree of sample vertices seriously deviates from the original social network,vertex over sampling,based on the Metropolis-Hasting Random Walk(MHRW)sampling method,a Jump unbiased Parallel vertex Sampling(JPS)method is proposed by introducing double jump strategy,parallel mechanism and vertex buffer.The online social network data set is modeled as a social graph with vertices and edges for simulation sampling,and the sample vertex attribute graph is drawn by using Python/Matplotlib drawing library.The experimental results show that the sampling method is more effective for social graph with different connectivity,which improves the update rate of vertices in the sampling process,reduces the average deviation of sample vertices and can converge more quickly.