# Comparing undirected weighted graphs

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.

• 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. – jmb May 6 '15 at 18:22