A rewiring algorithm, depending on the parameters, makes different graphs from a base random graph. I want to cluster the rewired networks and see which parameters make more similar/dissimilar graphs, and ideally, find what "structural prototypes" my algorithm produces.
The graph is binary and has 300 nodes, first 50 of them labeled as minority (blue) and the remaining 250 nodes of majority (red). The edges within the minority are colored blue, within the majority red, and the edges between majority and minority are green. Note that the edges are labeled by color, they are binary.
I'm attaching four examples of what I have: Anna, Hannah, Stef, and Emilie (I don't have enough reputation to embed the images.) Each plot shows the adjacency matrix (top left), adjacency matrix ordered/seriated (using matrix Laplacian, to better visualize "communities"; top right), and the network.
I want a similarity measure that allows me to cluster the networks.
I a network similarity measure (or clustering algorithm) for two scenarios:
- Similarity of the whole network (without color labels of edges, as if the adjacency matrices are black and white)
- Similarity of the networks, while taking into account the edge labels.
My initial idea was to vectorize the serialized adjacency matrix and do (k-means/hierarchical/etc.) clustering on the vectors. It has two issues though:
- There could be a difference in the position of a "community" (i.e., the squares in the adjacency matrix) in two graphs, but since the elements of the vectors are compared one-to-one, they would not end up in one cluster (hard to explain in words).
- It might work for the first scenario, but it is unclear how it can apply to the second.
- (more importantly,) the serialized matrices can be sometimes "flipped"; it's possible that two networks are quite similar (like Alice and Camille, if you treat them as black and white) but the adjacency matrices are similar only if one of them is mirrored along the off-diagonal axis.
What can I do? Thanks in advance.