MEASURING GRAPH SIMILARITY USING NODE INDEXING AND MESSAGE PASSING

摘要：

In this paper, we present a generative model to measure graph similarity.The parameters of that random process generating the observed graph from a template are determined by the node indices, reflecting the structure compatibility between nodes. We propose to use the steady state of the dynamic system represented by a directed graph to index the nodes.A message passing algorithm using the loopy belief propagation is adopted to approximate the maximum a posteriori assignment (MAP) for the nodes. The resulted believes of self matching form a similarity measure of the nodes in a graph.Examples and experiments demonstrated that the proposed method worked well for large graphs.

关键词： Graph similarity Graph matching Node indexing Loopy belief propagation

作者: GANG SHEN WEI LI

作者单位: Huazhong University of Science and Technology,Wuhan,China

会议类型: 国际会议

会议名称: 2011 3rd International Conference on Computer Technology and Development(2011第三届计算机技术与发展国际会议 ICCTD2011)

会议地点: 成都

会议语种:英文

页码: 1602-1607

在线出版日期: 2011-11-25（万方平台首次上网日期，不代表论文的发表时间）