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

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