Re: [igraph] Inexact graph matching

[Narayanan, Manikandan (NIH/NIAID) [C]]

I will assume that by distance in G1, you mean the shortest path distance from 
every vertex to every other vertex. If I understand you correctly, it seems 
like you can get this shortest path distance matrix for G2 too. You do have all 
neighboring vertices of any given vertex, using which you can obtain the list 
of edges and the distance matrix using an all-pairs shortest path algorithm. 
Can't you assume if an edge is not present in G2, then its edge weight is 
infinity? 

Graph-matching problems are in general computationally hard. For some 
definitions of graph similarity, there are tractable algorithms. The alignment 
needs to be well-defined too (eg. are G1,G2 defined over the same node set?). 

Best,
Mani

________________________________________
From: Khris address@hidden
Sent: Tuesday, July 03, 2012 10:12 AM
To: address@hidden
Subject: [igraph] Inexact graph matching

Hi,

I have specific Graph matching problem and I am not sure what's the best way to 
deal with it. The following is the def:-

We have 2 weighted undirected graphs. In one graph I know the distance of every 
vertex from every other vertex whereas in another graph I know only which 
vertices are close to a given vertex. So I know the neighboring vertices given 
a vertex. So the distance matrix of other Graph is incompletely known. So the 
question is what's the best way to find the correct alignment between the 2 
graphs. Are there any functions in iGraph library which implements those 
Algorithms?

Ex:- G1 is know the complete distance matrix. For G2, if there are four 
vertices let's say (v1, v2, v3 v4) the I know edge weight (v1,v2) and (v1,v3)  
but have no information of edge weight(v1,v4). Similarly I know about (v2,v3) 
but no information about edge weights (v2,v4) or (v3,v4). So G2 is incompletely 
known.

Appreciate any useful feedback and pointers.

Rest fine
Khris.