基于蒙特卡洛的PageRank增量算法研究

发布时间：2021-03-06 21:44

　　网络是表征系统内在联系模式的一种强有力的通用方式。生活中的许多系统都可以抽象成网络数据的形式。随着互联网以及社交网络的快速发展,对于网络的研究和分析也变得越来越重要。其中有关中心性的概念受到了很大的关注,即在一个网络中哪些节点是最重要或最核心的。1998年,谷歌提出了一种更加合理的中心性度量方法,PageRank算法,并将其应用在谷歌搜索引擎上。这一举动不仅令谷歌搜索引擎大受欢迎,也使得PageRank算法广为人知,并被广泛地应用于社会学、物理学和计算机科学等领域。然而在实际应用和研究中,许多网络的规模往往非常庞大,并且一直处于动态变化之中。在这样一种情形下,针对静态网络的PageRank算法将不足以满足我们的需求,特别是当我们想要实时的跟踪网络的PageRank值的时候。因此,我们迫切需要一种能够通过增量迭代,从而高效地跟踪大规模动态网络PageRank值的算法。现有的PageRank增量算法分为聚合划分类算法和蒙特卡洛类算法。理论研究已表明聚合划分类算法无法做到不累计误差地更新,因此本文专注于蒙特卡洛类算法。而以往的蒙特卡洛类算法忽视了随机游走会多次访问同一节点或者多次经过同一条边... 

【文章来源】：武汉大学湖北省 211工程院校 985工程院校 教育部直属院校

【文章页数】：60 页

【学位级别】：硕士

【部分图文】：

网络G(t)和添加了边e(1,4)的网络G(t+1)

图2.1中的网络的边列表 图 2.4: 图2.1中的网络的邻接表

【参考文献】：
期刊论文
[1]IncPR:一种基于增量计算的并行PageRank算法[J]. 姜双双,廖群,杨愚鲁,李涛.  计算机研究与发展. 2016(08)
[2]PageRank算法研究[J]. 黄德才,戚华春.  计算机工程. 2006(04)



本文编号：3067868