Hi,
thanks for the link I'm going to have a look at it soon. Here is what i
came up with based on the instructions you sent me. The function takes
g igraph object
att the name of the vertex attribute containing the community membership
mode the neigbhorhood mode c("in","out","all"), which is directly
passed to igraphs neighboorhood function
calc the type of calculation to be done c("membscore","expent"),
where membscore (for membership score) is supposed to be the first
option you suggested and expent (for expontiated entropy of the
memebership score vector) which hopefully implements your second suggestion
it returns a vector of the length length(V(g)) with the respective
bridgeness score for each vertex.
bridgeness <- function(g,att,mode="all",calc="membscore"){
require(igraph)
membscore <- function(input){
nbc <- get.vertex.attribute(g, att, index=V(g)[input])
result <-
subset(count(nbc[1]==nbc[2:length(nbc)]),x==TRUE)$freq/(length(nbc)-1)
return(-(result-1))
}
expent <- function(input){
nbc <- get.vertex.attribute(g, att, index=V(g)[input])
if(length(nbc)>1){
membv <- count(nbc[2:length(nbc)])$freq/(length(nbc)-1)
result <- exp(-(sum(log(membv)*membv)))}
else{result <- 0}
return(result)
}
nbs <- neighborhood(g,1,mode=mode)
result <- unlist(lapply(nbs,calc))
return(result)
}
It would be great if you find the time to have a look at it and tell me
if it does what you recommended me to do.
Thanks a lot for your help!
Best,
stephan
On 24.06.2014 15:14, Tamás Nepusz wrote:
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
[email protected]
https://lists.nongnu.org/mailman/listinfo/igraph-help
On 25.06.2014 12:10, Tamás Nepusz wrote:
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?
It is implemented using igraph, but it does not use R - it uses the C
core directly. The source code is available here:
https://github.com/ntamas/fuzzyclust
I haven't used it in a while so if it doesn't work with the current
version of igraph, let me know and I'll try to fix it.
Best,
T.
_______________________________________________
igraph-help mailing list
[email protected]
https://lists.nongnu.org/mailman/listinfo/igraph-help
