基于随机游走的大规模图中节点对采样算法

• 作者: 叶东毅 吴春琼
• 来源期刊: 计算机应用研究
• 关键词: 图 随机游走 均匀顶点采样 社会网络
• 年，卷（期）: 2015,（4）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 1052-1055
• 页数: 4页
• 分类号: TP301.5
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2015.04.022

摘要

社会网络中的节点对采样可用于大规模社会网络的好友预测和用户兴趣识别.当整个网络的拓扑结构不完全或者随机选择用户的代价很高时,传统的均匀顶点采样方法的性能迅速下降.为此,提出了一种基于随机游走的大规模图中节点对采样算法.首先对社会网络的节点对采样进行了系统分析,对不同跳数下的节点对进行了定义;然后将社会网络转换成等价的网络图.新图中的顶点是原图中的边,新图中边的两个顶点是原图中含有相同顶点的两条边.最后,在新图上应用随机游走模型对节点对进行采样.实验结果表明,提出的方法统计误差小、执行效率高,性能明显优于均匀节点采样的相关算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	叶东毅	福州大学数学与计算机科学学院	112	1572	18.0	36.0
2	吴春琼	福州大学阳光学院	3	1	1.0	1.0