关键词: 在线社交网络, 顶点采样, 蒙特卡罗随机游走（MHRW）, 双重跳跃, 无偏, 并行机制

Abstract: 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.

Key words: online social network, vertex sampling, Metropolis-Hasting Random Walk (MHRW), double jump, unbiased, parallel mechanism