Scalable Similarity Search for SimRank相似性评价度量

1、Scalable Similarity Search for SimRankScalable Similarity Search for SimRank论文方向：相似度评价算法论文级别：SIGMOD会议，CCF推荐A类基于SimRank模型的可扩展相似性搜索目 录论文背景简介SimRank论文主要工作总结123SimRank什么是SimRank1SimRank 是一种基于图的拓扑结构信息来衡量任意两个对象间相似程度两个对象间相似程度的模型，该模型由 MIT 实验室的 Glen Jeh 和 Jennifer Widom教授在2002年首先提出。SimRank相似度的核心思想为：如果两个对象和被其

2、相似的对象所引用（即它们有相似的入邻边结构），那么这两个对象也相似。SimRank模型定义SimRank2SimRank 模型定义两个页面的相似度是基于如下递归的公式：网页排名协同过滤近似查询网络图聚类SimRankSimRank的应用3论文主要工作论文摘要1由Jeh和Widom教授提出的SimRank模型提供了一个很好的相似性指数，并且已经成功应用于许多提到的应用之中。迄今为止，尽管已经提出了很多算法来计算SimRank，但是没一个算法能够扩展到一个具有十亿数量级的图之中来。由此项事实激励我们考虑以下的SimRank相似性搜索问题：给定一个查询节点u，查找对于u来说拥有最高SimRank指数

3、的前k个节点v，该指数可表述为s(u,v)。我们提出了一个高效且可扩展的计算SimRank搜索问题的算法。在十亿级别边的图中，该算法可以在 几秒之内计算出给定节点u的的top-20相似性节点。论文主要工作四大要素2 线性递归表达式s(u, v) = euDev +c(Peu)DPev +c2(P2eu)DP2ev + 两个上界值xy max xew xy |x| |y| SimRank指数的距离衰减特性 蒙特卡罗模拟论文主要工作SimRank线性递归公式变换3论文主要工作top-k相似性搜索算法4预处理构建原图的二分图，由蒙特卡罗模拟确定二分图的边。第一次筛选出候选节点。计算两个相似度界限。查

4、询由两个相似度界限剪除冗余节点。运用适应性选样加速筛选节点，一次设置随机游走的次数较少，第二次筛选出候选点后进行二次精确计算SimRank值，选出前K个点。总结论文的创新点 提出SimRank的线性递归表达式，结合蒙特卡罗模拟方法、距离的衰减特性、适应性选样技术使得搜索的时间复杂度独立于图的规模，空间复杂度控制在可接受范围。 根据实际需要，进一步简化算法为top-k相似性搜索，为实际运用提供指导。 由于算法独立于图的规模的特性，方便进行并行计算。使得计算超大规模的图的SimRank值成为可能。首次扩展到十亿级别的超大规模网络结构中来。总结论文不足之处与其他可行工作 未能建立蒙特卡罗步数、衰减系数与精度的关系的数学分析模型 算法的预处理步骤是建立二分图，能否找到空间复杂度更优的替代数据结构完成筛选点的步骤，这样就可以扩展到更大的图 算法的核心是基于线性递归表达式的，而论文的实验数据都是大规模的稀疏图，若是稠密图，精度会有较大影响 节点间的相似度不仅与它们之间的链接有关还与其中的内容有关，当把节点间的内容也放进相似度评价后，如何把本文的线性递归表达式与内容评价融合起来是一个值得研究的问题总结体会 SimR