[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] Bridges between clusters
From: |
Tamás Nepusz |
Subject: |
Re: [igraph] Bridges between clusters |
Date: |
Tue, 24 Jun 2014 15:14:03 +0200 |
> How about using this paper by our own Dr Nepusz? :)
> http://arxiv.org/abs/0707.1646
That's nice :) Actually, the clustering algorithm described in that paper
probably won't scale up to the size of the graph you are working with. However,
you can probably still make use of the "bridgeness" measure by "making up"
membership scores for each vertex and each cluster as follows. Let vertex i
belong to cluster j with a score that corresponds to the total weight of edges
connecting vertex i to members of cluster j, divided by the total weight of
edges incident on vertex i. You can then either calculate "bridgeness" scores
from these membership scores.
Alternatively, you can calculate the exponentiated entropy of the membership
score vector corresponding to a single vertex -- this gives you the "effective
number of clusters" that the vertex belongs to. For instance, if 60% of the
edges of a vertex connect the vertex to cluster 1, 30% of the edges connect it
to cluster 2 and 10% connect it to cluster 3, the membership vector is defined
as [0.6, 0.3, 0.1]. The exponentiated entropy of this vector is then
exp(-(0.6*log(0.6) + 0.3*log(0.3) + 0.1*log(0.1))), which tells us that the
vertex effectively belongs to 2.45 clusters. If the membership vector were
[0.9, 0, 0.1], the exponentiated entropy would have yielded
exp(-0.9*log(0.9)-0.1*log(0.1)) 1.38. You can then set an arbitrary threshold
and say that the bridges are those vertices for which the exponentiated entropy
is above 1.5.
T.