CODEWITHSUNDEEP
algorithmgraph-theorygraph-algorithm
Saikat
Saikat

Reputation: 1219

Graph similarity measure with unknown node correspondence

How to measure the similarity between two graphs G1 and G2 with equal or unequal number of nodes where, the correspondence between the nodes of the graphs are unknown. For example, node A of G1 has moved to the middle of G2. Is there any similarity measure algorithm that returns

sim(G1,G1)=1 sim(G1,G2)=1 sim(G1,G3)=some number between 0 and 1

where, 1 denotes highest similarity and 0 denotes lowest similarity.

enter image description here

Upvotes: 1

Views: 432

Answers (2)

Nick
Nick

Reputation: 1106

In paper (Tantardini et al., 2019), authours proposed the classification of comparing methods for comparing networks: а) known node-correspondence, b) unknown node-correspondence.

Upvotes: 1

cobarzan
cobarzan

Reputation: 682

Since you don't know the nodes correspondence, one simple approach is to define the signature of a graph as a sorted array containing the degrees of all nodes. Then find the longest common sub-sequence of the two signatures, where "common" doesn't necessary mean all "elements are equal", but that they are close enough. Since the signatures are sorted arrays, the problem is even simpler. And then somehow compute the distance between the two versions of the longest "common" sub-sequence. Additionally, you can factor in some score concerning the nodes that are not part of it.

Upvotes: 1

Related Questions