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

• 作者: 何军 杜小勇 邹李
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 相似度计算 链接分析 块结构 图的划分
• 年，卷（期）: 2010,（9）
• 页码范围: 780-790
• 分类号: TP311
• 字数: 8060字
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.2010.09.002

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	何军	中国人民大学数据工程与知识工程教育部重点实验室	24	215	6.0	14.0
5	杜小勇	中国人民大学数据工程与知识工程教育部重点实验室	79	2516	24.0	49.0
9	邹李	中国人民大学数据工程与知识工程教育部重点实验室	1	1	1.0	1.0