most recent 30 from http://mathoverflow.net 2013-05-22T15:45:15Z http://mathoverflow.net/feeds/question/92806 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/92806/how-to-use-node-similarity-to-measure-subgraph-similarity dvdgrs 2012-04-01T11:57:00Z 2012-09-03T20:22:00Z

<p>For a semantic annotation task I am trying to calculate the semantic similarity between two sets of annotations: S1 and S2. Both sets consist out of multiple nodes from within one graph (in my case an ontology). The sets do not necessarily contain the same amount of nodes.</p> <p>I measure the similarity between two nodes using a path-based similarity metric (Leacock &amp; Chodorow's). By measuring the similarity between each node in both subgraphs, I can generate a semantic similarity graph, see example here: <a href="http://graus.nu/thesis/measure-and-visualize-semantic-similarity-between-subgraphs/" rel="nofollow">http://graus.nu/thesis/measure-and-visualize-semantic-similarity-between-subgraphs/</a> (in this case, the red and blue nodes are nodes from S1 and S2, the edges represent similarity between nodes).</p> <p>But now I want to know how to calculate the average, mean and standard deviation of the similarity between the two subgraphs as a whole. How would I go about that? I thought about taking the shortest path for each node in S1 to each node in S2, and using these to get my avg/mean/std deviation, however different sized sets means I miss information in some cases (for example in the case where S1 has 3 nodes and S2 has 8 nodes; I'd get 3 paths). Couldn't I just use all possible edges between all nodes from S1 to all nodes from S2 to get these numbers?</p> <p>Researching so far has brought me distance matrices, graph bijection, but I'm a bit lost here, any help in pointing me in the right direction will be greatly appreciated!</p>

http://mathoverflow.net/questions/92806/how-to-use-node-similarity-to-measure-subgraph-similarity/92881#92881 dvdgrs 2012-04-02T09:34:31Z 2012-04-02T09:34:31Z

<p>I'm approaching it now by taking each shortest path from S1 to a node in S2, and then the other way around (shortest path from node in S2 to node in S1), omitting duplicate paths. I imagine that as long as I'm consistent with this approach over different annotation sets, it can suffice to use as measure, right?</p>