I am working with Community Detection in graphs. I have been through the different community detection algorithms implemented in igraph and plotting the community structures. Now after getting the communities object for different algorithms, I want to compare the algorithms based on different measures like density,cut ratio, coverage. (I know that modularity is already implemented). I can obtain a subgraph and then calculate the intra-cluster density but to find the inter-cluster density, I dont not know how to proceed. This is the code I have been using to find intra-cluster density:
karate <- graph.famous("Zachary")
wckarate <- walktrap.community(karate) #any algorithm
subg1<-induced.subgraph(karate, which(membership(wckarate)==1)) #membership id differs for each cluster
intradensity1 <- ecount(subg1)/ecount(karate) #for each cluster
Similarly I could proceed for each cluster and add all the densities or take the average of the all. My question is that if the number of communities is very large, then how to proceed?
And if I want to extract the number of edges between different communities, is there a nice way to extract the number of edges?
Please pardon me if this question is already asked. I am novice to igraph and R.
Community detection, also called graph partition, helps us to reveal the hidden relations among the nodes in the network. Many algorithms have been developed to detect communities (Clauset et al., 2004; Girvan and Newman, 2002; Lancichinetti and Fortunato, 2009).
Community detection is very applicable in understanding and evaluating the structure of large and complex networks. This approach uses the properties of edges in graphs or networks and hence more suitable for network analysis rather than a clustering approach.
Well, we can just adapt your code to loop over the different subgroups
karate <- graph.famous("Zachary")
wckarate <- walktrap.community(karate) #any algorithm
sapply(unique(membership(wckarate)), function(g) {
subg1<-induced.subgraph(karate, which(membership(wckarate)==g)) #membership id differs for each cluster
ecount(subg1)/ecount(karate)
})
and as far as getting the edges between the communities, you could do
#get all combinations of communities
cs <- data.frame(combn(unique(membership(wckarate)),2))
cx <- sapply(cs, function(x) {
es<-E(karate)[V(karate)[membership(wckarate)==x[1]] %--%
V(karate)[membership(wckarate)==x[2]]]
length(es)
})
cbind(t(cs),cx)
Also you can plot the communities to make sure that looks reasonable
plot.communities(wckarate, karate)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With