search

jacquesfize / ged4py

Implementation of a graph edit distance in python
MIT License
34 stars 10 forks source link

The normalized distance is 1+ #4

Open woaiwodib107 opened 6 years ago

woaiwodib107 commented 6 years ago

I think normalized distance should be from 0 to 1

jacquesfize commented 6 years ago

Hi @woaiwodib107, first, remember that the graph edit distance is ... a distance. Which means the lower the value, the closer are the two compared graphs. If you wish to work in terms of similarity, you can reverse the distance value by doing this: 1-distance (if the distance is normalized)

woaiwodib107 commented 6 years ago

thanks for your answer. I used two Graph() g1 =1-2, 2-3 g2 =1-2 the distance is 0.666 g1 =1-2, 2-3 g3 =1-2, 3 the distance is 0.555

So is g3 more simlar then g2?

g1 = 1-2, 2-3 g4 = nx.Graph() the distance is 2!!!

g1 =1-2, 2-3 g5 = 1 the distance is 1.5

g1 = 1-2, 2-3 g6 = 1,2 without any edge the distance is 1.6

g1 =1-2, 2-3 g7 = 1,2,3 without any edge the distance is 1.333

so g7<g5<g6?

and I found the id of node influces the distant, is that right?

jacquesfize commented 6 years ago

Hi @woaiwodib107, sorry about the delay.

I checked the GED algorithm and yes, it seems the normalization was not working :s I modify the GED algorithm, but the new version is part of python module of my design : GMatch4py

This new module comes with GEDs and other graph matching algorithms. And compared to this version, it used Cython for better performances !