社交网络随机游走抽样的误差修正算法研究
王永强
董云泉
南京信息工程大学电子与信息工程学院 南京 210044
摘要：如何对在线社交网络的用户数进行高效、精确估计是网络科学领域的一个基本的问题.基于随机游走抽样的估计算法通过随机访问部分网络用户和统计各用户重复访问次数,实现对社交网络用户数的估计.然而当前的各种社交网络用户数估计算法的估计误差都非常大.研究发现,造成估计结果相对误差偏大的主要原因是网络中低度节点所产生的"虚假碰撞".因此,该研究在基于随机游走抽样的估计算法的基础上提出一种基于碰撞计数的修正算法,通过去除低度节点产生的"虚假碰撞",进而提高算法估计的准确性.通过使用真实社交网络数据集进行实验验证,结果表明,与传统的基于随机游走抽样估计算法相比,误差修正算法可以有效地减小估计的相对误差.
关键词：在线社交网络估计误差随机游走抽样误差修正
分类号：TP391(计算技术、计算机技术)
资助基金：国家自然科学基金(62071237)
论文发表日期：2025-11-20
在线出版日期：2026-01-28（本平台首次上网日期，不代表文献的发表时间）
页数：7( 2995-3000,3012 )
英文信息