Graph similarity scoring and matching

被引：143

作者：

Zager, Laura A. ^{[1
]}

Verghese, George C. ^{[1
]}

机构：

[1] MIT, Dept Elect Engn & Comp Sci, Cambridge, MA 02139 USA

来源：

APPLIED MATHEMATICS LETTERS | 2008年 / 21卷 / 01期

基金：

美国国家科学基金会;

关键词：

graphs and networks; graph algorithms; similarity measures; graph matching; graph alignment;

D O I：

10.1016/j.aml.2007.01.006

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We outline a class of graph similarity measures that uses the structural similarity of local neighborhoods to derive pairwise similarity scores for the nodes of two different graphs, and present a related similarity measure that uses a linear update to generate both node and edge similarity scores. This measure is then applied to the task of graph matching. (c) 2007 Elsevier Ltd. All rights reserved.

引用

页码：86 / 94

页数：9

共 19 条

[1] A LINEAR-PROGRAMMING APPROACH FOR THE WEIGHTED GRAPH MATCHING PROBLEM [J].

ALMOHAMAD, HA ;

DUFFUAA, SO .

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1993, 15 (05) :522-525

[2] A measure of similarity between graph vertices: Applications to synonym extraction and web searching [J].

Blondel, VD ;

Gajardo, A ;

Heymans, M ;

Senellart, P ;

Van Dooren, P .

SIAM REVIEW, 2004, 46 (04) :647-666

[3]

BORLIN N, ASSIGNPROB ZIP

[4] Error correcting graph matching: On the influence of the underlying cost function [J].

Bunke, H .

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1999, 21 (09) :917-922

[5] A graph distance metric combining maximum common subgraph and minimum common supergraph [J].

Fernández, ML ;

Valiente, G .

PATTERN RECOGNITION LETTERS, 2001, 22 (6-7) :753-758

[6] Deriving phylogenetic trees from the similarity analysis of metabolic pathways [J].

Heymans, Maureen ;

Singh, Ambuj K. .

BIOINFORMATICS, 2003, 19 :i138-i146

[7] Role-similarity based functional prediction in networked systems: application to the yeast proteome [J].

Holme, P ;

Huss, M .

JOURNAL OF THE ROYAL SOCIETY INTERFACE, 2005, 2 (04) :327-333

[8]

JEH G, 2002, P 8 INT C KNOW DISC

[9] Authoritative sources in a hyperlinked environment [J].

Kleinberg, JM .

JOURNAL OF THE ACM, 1999, 46 (05) :604-632

[10]

Kuhn H. W. W., 1955, Nav.Res. logistics Quart., V2, P83, DOI DOI 10.1002/NAV.20053

← 1 2 →