# Similarity measure for clusterings in graphs evolving over time (temporal network)

From what I understand about clusters, they can be obtained from an existing graph at 1 instance of time. But consider the situation of a temporal network, such as a social network, where the graph keeps evolving and the clusters keep on changing.

So I'm looking for a method which will be able to give me a similarity measure between two set of clusters formed at different timestamps.

I have looked at a few research papers but haven't come across a proper implementation/algo related to the idea.

The idea mentioned here: https://math.stackexchange.com/questions/52184/measure-similarity-of-graphs is that of degree sequence and euclidean distance but works only on two graphs with matching number of nodes.

In a temporal-evolving network, a graph with constant nodes isn't really possible.

So, I'm looking for algorithm/suggestions to improve the existing methods which is easy to compute (and has some sort of implementation available, hopefully) that can find a similarity measure between two sets of clusters.

Is it possible to first look at the nodes presenting in both graphs? then find a way to quantify the relative "importance" of intersection regarding to two original graphs. For instance, if the non-intersect part is large or complex enough to overwhelm the intersection part.

This make sense only if you agree that the non-intersect part don't have any similarity with each other, since the nodes are totally different

• When we are talking about the clusters, that too the ones evloving over time, I highly doubt that the intersecting part will be overwhelmed by the non-intersecting part. This is because the clusters tend to remain constant with an exception of a few areas in the graph. The similarity measure I'm looking for is kind of required to find out those anomalous/infrequent nodes in the time-evolving graph. – codeninja Jun 29 '16 at 13:39

See the section 3.2.4. Definitions based on vertex similarity in the paper (Fortunato, 2010). But sets of nodes should be equal.

Ref: Fortunato, S.: Community detection in graphs. Physics Reports 486, 75–174 (2010)

The similar question is here.

• Working link please? Nothing attached right now. Blank hyperlink. – codeninja Jun 30 '16 at 19:11