igraph-help
[Top][All Lists]

## Re: [igraph] Inexact graph matching

 From: Tamás Nepusz Subject: Re: [igraph] Inexact graph matching Date: Wed, 4 Jul 2012 10:34:17 +0200

```Hello Khris,

This seems to be a very complicated graph matching problem and I'm very
confident that you cannot find the exact solution in polynomial time -- if you
could, you could also solve the graph isomorphism problem in polynomial time by
finding the best match between the two graphs and checking whether the distance
between the two matched matrices is zero or not. If the graph is small, you can
try a branch-and-bound strategy -- basically an exhaustive search where you
keep track of the best match found so far (and its "cost") and skip the
branches of the search tree where you can infer that the cost of any leaf in
that branch is higher than the best match found so far. (You can do this
because the cost function is monotonously increasing as you match more and more
nodes along a branch of a search tree). This will be exponential, but with some
clever heuristics it may be tractable. The heuristic part comes into play at
two places:

1. You have to decide in which order you are going to consider the nodes of one
graph to be matched to the other as you build up the complete matching.
2. You have to decide in which order you try to assign the unmatched nodes of
G2 to the currently considered node in G1.

--
T.

On Tuesday, 3 July 2012 at 16:12, Khris wrote:

> 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.
>
>
>
> _______________________________________________
> igraph-help mailing list