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

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

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

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.