Journal of Frontiers of Computer Science and Technology ›› 2010, Vol. 4 ›› Issue (9): 780-790.DOI: 10.3778/j.issn.1673-9418.2010.09.002

• 学术研究 • Previous Articles     Next Articles

B3: A Block-based Method for Estimating Similarity for Inter-Graph Vertice*

ZOU Li1,2, DU Xiaoyong1,2+, HE Jun1,2   

  1. 1. Key Lab of Data Engineering & Knowledge Engineering, MOE, Renmin University of China, Beijing 100872, China
    2. School of Information, Renmin University of China, Beijing 100872, China
  • Received:1900-01-01 Revised:1900-01-01 Online:2010-09-09 Published:2010-09-09
  • Contact: DU Xiaoyong

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

邹 李1,2, 杜小勇1,2+, 何 军1,2   

  1. 1. 中国人民大学 数据工程与知识工程教育部重点实验室, 北京 100872
    2. 中国人民大学 信息学院, 北京 100872
  • 通讯作者: 杜小勇

Abstract: Traditional linkage-based similarity computation just considers vertice in single graph. Blondel et al have extended the problem to similarity computation between two directed graphs. However their approach suffers from high time and space complexity, which makes it difficult to be used on large graphs. Therefore, effective and efficient methods for computing similarity between vertices across different graphs are still expected. This paper exploits the block structure of graphs, and proposes B3 (block based Blondel) algorithm, which partitions graphs into several blocks at first, and computes the intra-block similarities and inter-block similarities by original Blondel algorithm, then obtains the global similarities of vertices. The convergence of B3 is proved, and it has less time and space complexity. Experiments also show the effectiveness of this method.

Key words: similarity estimate, link analysis, block structure, graph partition

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

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

CLC Number: