[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [igraph] Bridges between clusters

From: Stephan Schlögl
Subject: Re: [igraph] Bridges between clusters
Date: Tue, 24 Jun 2014 15:30:10 +0200
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.5.0

thank you very much for your fast answers. Based on the abstract of Tamas paper this is exactly what i was looking for. Hopefully I can use this for smaller networks in the future. Is it implemented in igraph for R?

For now I'm going to use one or both of the approaches Tamas suggested. Thank you for going in detail with the second one so I can actually try to implement this now. Probably I'm coming back to you guys with a code snippet to have a look at it and make sure I'm actually doing what you said ;)


On 24.06.2014 15:14, Tamás Nepusz wrote:
How about using this paper by our own Dr Nepusz? :)
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.


igraph-help mailing list

Mag. Stephan Schlögl
Projektmitarbeiter (Prae-Doc)

Institut für Publizistik- und
Währinger Straße 29, 1090 Wien

T: +43-1-4277-493 87
eFax: +43-1-4277 849387

reply via email to

[Prev in Thread] Current Thread [Next in Thread]