search

netsiphd / netrd

A library for network {reconstruction, distances, dynamics}
https://netrd.readthedocs.io/en/latest/
MIT License
166 stars 43 forks source link

Common Subgraph Based Distances #35

Open tlarock opened 5 years ago

tlarock commented 5 years ago

There is a class of graph distances, largely published about in the late 90s/early 2000s, based on maximum/minimum common subgraphs. Should we implement these?

The following papers claim that the computation of the maximum common subgraph is a special case of the computation of edit distance:

  1. On a relation between graph edit distance and maximum common subgraph
  2. A graph distance metric based on the maximal common subgraph

These define some variants of common subgraph based distances:

  1. A graph distance metric combining maximum common subgraph and minimum common supergraph
  2. Graph distances using graph union

These papers are written by people more math-y than me. @leotrs (or anyone else!), could you take a look, specifically at 1 and 2, and comment on whether you think we should implement these?

leotrs commented 5 years ago

I confess I haven't read the cited papers, but I have Things To Say.

  1. We should leave open the possibility for implementing any distance method, so let's keep this open
  2. I don't think we need to worry about this for the time being (let's revisit after NetSci'19)
  3. One thing we could think about for the time being - do these distances fit the two-step model outlined in #174 ? If not, what changes would we need to make to the library to include these?