0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – codeninja Jun 29 '16 at 13:39
0
$\begingroup$

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.

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

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.