8
$\begingroup$

Suppose you have networks A and B, each with a set of nodes and edges. You want to measure how similar the networks are to each-other. None of the nodes or edges are labelled. What are the metric(s) typically used that get the distance between two networks? There are plenty of summary statistics such as connectivity distributions, etc. However, is there any "fine-grained" metric that only vanishes for identical networks, is symmetric, and satisfies the triangle inequality?

Clarifications: this question asks about the distance between two networks, not the classical graph-distance between two nodes in a network. Networks are considered "identical" if the adjacency matrices of A and B can be made identical.

Edit: This is a generalization of the Graph Isomorphism Problem, which is not known in P. So the question becomes: are there any estimators sensitive to the "fine-grained" details?

Improve this question
$\endgroup$
4
  • $\begingroup$ See en.wikipedia.org/wiki/Graph_isomorphism_problem. If there were an easy metric to compute it would solve this well-known open problem. $\endgroup$
    – Douglas Zare
    Commented Apr 21, 2014 at 18:06
  • $\begingroup$ As a step toward your goal, consider all maps f: between A and B. Devise a measure on this space that determines how far a map is from an isomorphism, say count of tuples abar such that R(abar) and not R(f(abar)) for a relation R the network has (number of nodes of degree d as an example, but you may want several differing R.) If you are looking for a distance, now see if your measure will give you the additional properties between different spaces. Gerhard "Ask Me About System Design" Paseman, 2014.04.21 $\endgroup$
    – Gerhard Paseman
    Commented Apr 21, 2014 at 18:07
  • 1
    $\begingroup$ Have you looked at the graph edit distance (GED)? E.g.: Xinbo Gao, Bing Xiao, Dacheng Tao, Xuelong Li, "A survey of graph edit distance," Pattern Analysis and Applications 13.1 (2010): 113-129. $\endgroup$
    – Joseph O'Rourke
    Commented Apr 21, 2014 at 20:42
  • $\begingroup$ Of possible interest: maximizing the number of matched edges over choice of maps $A \to B$ (an approximate version of graph isomorphism) can be approximated to within some constant factor in $n^{O(\log n)}$ time, but approximating it to within a factor better than 0.94 is NP-hard: link.springer.com/chapter/10.1007%2F978-3-642-32589-2_12 and eccc.hpi-web.de/report/2012/078/download. $\endgroup$
    – Joshua Grochow
    Commented Jun 14, 2014 at 2:33

3 Answers 3

Reset to default
4
$\begingroup$

I suggest to look at the Gromov-Wasserstein distances (defined between two metric measure spaces). A great start is the paper "Gromov-Wasserstein distances and the metric approach to object matching" ( https://link.springer.com/content/pdf/10.1007/s10208-011-9093-5.pdf) that also deals with some computational issues. As introduced in the paper, the approach does not incorporate weights on the edges yet (as far as I remember)...

Improve this answer
$\endgroup$
3
$\begingroup$

See

http://mpba.fbk.eu/sites/mpba.fbk.eu/files/PhD-Thesis.pdf

for a brief review and

http://arxiv.org/abs/1201.2931

for a novel solution.

Improve this answer
$\endgroup$
2
$\begingroup$

You can also use persistent homology combined with the Wasserstein distance (or the bottleneck distance) to define a distance between networks.

See here

https://ieeexplore.ieee.org/abstract/document/8365984/

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .