B3:图间节点相似度分块计算方法

摘要：

传统的基于链接的对象相似度计算方法仅考虑单个图中的节点.Blondel等人将该问题扩展到图间节点,提出Blondel算法,但该算法的时间和空间复杂度过高,不适用于大规模图之间的节点相似度计算.如何高效地计算两个图之间的相似度的方法仍有待研究.提出了B3(block based Blondel)算法,先对图进行分块,然后将分块作为一个独立整体,应用原Blondel算法计算块内的节点相似度和块间的相似度,最后再计算任意节点间的全局相似度.该算法是收敛的,并且大大降低了时空复杂度.实验也很好地证明了算法的有效性.

关键词：相似度计算、链接分析、块结构、图的划分

所属期刊栏目：4

分类号：TP311(计算技术、计算机技术)

资助基金：The National Natural Science Foundation of China under Grant No.60873017

在线出版日期：2010-11-17（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：780-790