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.
_______________________________________________
igraph-help mailing list
address@hidden
https://lists.nongnu.org/mailman/listinfo/igraph-help