I want to get a sense of the similarity between weighted, undirected graphs.

My data are from an EEG experiment, where every vertex is an electrode, and every edge is the connectivity between two electrodes. As a result, every graph always has the same number of vertices and edges, and every vertex pair is connected (full connectivity). So between graphs, there is a straightforward one-to-one mapping between vertices and edges. What differs between graphs are the weights on the edges.

Moreover, there's a distinct topographical aspect to these graphs: electrodes that are closer together in physical space generally have higher connectivity.

The simplest approach to compare networks would be to essentially drop the graph approach and do a Pearson correlation (or related measures) over all weights. However, I suspect this is a pretty crude approach.

In researching, I've seen discussions where it is advised to interpret weights as distances and calculate the Euclidean distance, or more advanced procedures such as Gromov-Hausdorff distance (https://mathoverflow.net/questions/38305/similarity-of-weighted-graphs). However, methods based on matrix distance do not seem to care about electrode topography (weight pairs for closely spaced and widely separated electrodes contribute equally). It's unclear to me whether this is desirable.

Apart from a whole-network approach, I can imagine there are methods to compare networks on a vertex-by-vertex basis, which could have the benefit of seeing which parts of networks are similar and which are less so.

An final issue is that the weight distributions (mean, variance) could be different between the two networks, but if one network is just a scaled version of the other, I would still consider them highly similar. Normalizing weights is not trivial however, so methods that don't care about absolute weights would be optimal.

  • $\begingroup$ How about normalizing the weights within each network and then taking the difference or ratio of each single weight in network A and B? You again get a weighted adjacency matrix, which you can use to visualize the differences between A and B. $\endgroup$ – jmb May 6 '15 at 18:22

Since both networks contain comparable nodes (I suppose one electrod in the first network is equivalent to another one in the second), the simplest method that comes to my mind is to just process the Euclidean distance between both adjacency matrices. That is: linearize the matrices to obtain two vectors, then process the classic Euclidean distance.

See also this post on Mathematics.


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.