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?

$\endgroup$
  • $\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 Apr 21 '14 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 Apr 21 '14 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 Apr 21 '14 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 Jun 14 '14 at 2:33
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)...

| cite | 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.

| cite | 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/

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.