B3:A Block-based Method for Estimating Similarity for Inter-Graph Vertice
Jun He · Jisuanji kexue yu tansuo · 2010
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.