单源SimRank计算优化及其在协同过滤中的应用

发布时间：2024-07-08 18:30

　　图作为一种表达对象与对象之间抽象关系的非线性数据结构,具有更加一般化的表达能力,在我们现实生活中扮演者重要的角色。近年来,随着互联网、云计算、物联网等技术的高速发展,数据增长的规模正在以前所未有的速度增加,“大数据”给各行各业带来了很大的机遇和挑战,同时图数据的规模也随着个性化推荐、信息检索、社交网络分析等应用的蓬勃发展变得越来越大。随着图数据规模的增大,人们发现庞大的图数据中蕴含着巨大的商业价值,基于图结构的各种互联网应用在近些年来层出不穷,在这些应用中,最典型和最基本的一类任务就是计算对象和对象之间的相似度。SimRank是一种非常流行的基于图拓扑结构信息来衡量任意两个对象之间相似程度的模型,其核心的思想为:一个对象应该与自身最相似,如果两个对象都被相似的对象所引用,那么这两个对象也相似。然而,由于SimRank定义的递归依赖性,导致了SimRank计算的时空复杂度很大,图数据规模的增大在另一方面也使得问题更加突出。在本文中,我们主要针对单源节点SimRank的计算,即给定一个查询顶点,返回该节点与所有其他节点间的相似度,提出并实现了一种称之为ProbeWalk的高度并行的算法。我...

【文章页数】：77 页

【学位级别】：硕士

【部分图文】：

图２－１：?ＳｉｍＲａｎｋ算法总结??

第二章相关工作??．１?ＳｉｍＲａｎｋ计算方法现状??ＳｉｍＲａｎｋ作为衡量对象间相似度的一种指标首次在２００２年由Ｊｅｌｌ和Ｗｉｄｏｍ??授在文献［８］提出来以后，随着其在网页排名、孤立点检测、协同过滤、近??查询处理、网络图聚类等领域的成功应用，ＳｉｍＲａｎｋ的计算速度便成为....

图３－１：?—个路径复用的例子??

较大的情况下的一个好方法。??图３－１：?—个路径复用的例子??图３－１是一个“路径复用”的例子，顶点ａ为一个待查询顶点，路径??＜?＞为算法随机的一条相遇长度为１的随机路径，路径＜?ａ，Ｚ？，ｅ，ｃ，／，／ｚ?＞??为相遇长度为２的随机路径，路径＜?＞为相遇长度为３的随机路??....

图３－２：从顶点ａ和ｊ出发的相遇长度为３的匹配路径??

高查询算法的可用性便成为了一个问题。“路径复用”策略便是解决查询集合??较大的情况下的一个好方法。??图３－１：?—个路径复用的例子??图３－１是一个“路径复用”的例子，顶点ａ为一个待查询顶点，路径??＜?＞为算法随机的一条相遇长度为１的随机路径，路径＜?ａ，Ｚ？，ｅ，ｃ，／，／....

图３－３：随机图的平均误差随／的变化?

?３３??以误差也就越大。同样的，在图３－３中有着跟人造图一样的规律，总体的平均??误差是随着／指数减小的，有所不同的是，这两个真实图的折线比较接近，这??是因为这两个数据集顶点数和边数都比较接近从而在相同条件下误差结果比较??接近。??１０“??????ｆｒ?■?Ｒａｎｄｏｍ?....

本文编号：4003694