Re: [igraph] multilevel community in weighted networks

[Tamás Nepusz]

Hi Stefano,

Sorry for the late reply. I'm not sure what happens here, but here's what I 
think. The modularity function has a so-called "resolution limit" (see 
http://www.ncbi.nlm.nih.gov/pmc/articles/PMC1765466/ ) which basically prevents 
one from detecting communities that are smaller than a given threshold. There 
are multiple ways to overcome the resolution limit, and one of the proposed 
methods involved adding loop edges of a given constant weight to all the nodes 
to increase the aversion of nodes to form communities. The bottom line is that 
the weights of the loop edges in a graph determine the "resolution" of the 
obtained community structure.

Of course you may say at this point that your graph does not have loop edges at 
all, and it is true. However, the multilevel method will *introduce* loop edges 
because first it detects communities at a fine-grained level, then *collapses* 
each community into a single node and then proceeds with the algorithm on the 
collapsed graph. When a community is collapsed into a node, the new meta-node 
(that represents the community) will gain a loop edge whose weight is equal to 
the sum of edge weights within the original community. This may influence the 
course of the algorithm in later steps and that's why you see different 
community structures for the multilevel method.

Note that this is pure speculation -- another option is that simply we screwed 
up something in the code of the multilevel algorithm and it is indeed sensitive 
on the magnitude of the weights. The third option is that there are numerical 
inaccuracies in the calculation of the modularity gains and these numerical 
errors accumulate over time, depending on the magnitude of the weights.

If you can construct a smaller graph (with, say, 5-10-15 nodes) that is 
sensitive on the magnitude of the weights, let me know and I'll try to confirm 
or refute my proposal by hand.

All the best,
Tamas

On 23 Feb 2013, at 13:31, Stefano Breschi <address@hidden> wrote:

> I am applying community detection algorithms to a weighted network. The 
> weight is just a number comprised between 0 and 1. What is puzzling me is 
> that the partition returned by the multilevel.community method seems to 
> depend on the scaling of the weights, i.e. if one multiplies the weight by 10 
> etc., whereas the fastgreedy.community method is not affected by this scaling 
> issue, i.e. the partitions are always the same irrespective of the scale.
> 
> Here is the link to the data I am using
> 
> https://www.dropbox.com/s/yxw7pjrsgqbfjsj/example.csv
> 
> The code applied is the following:
> 
> library(igraph)
> 
> a <- read.csv("example.csv",header=TRUE)
> h <- graph.data.frame(a, directed=FALSE)
> h <- simplify(h, remove.multiple=TRUE, remove.loops=TRUE)
> 
> memberships <- list()
> 
> fg <- fastgreedy.community(h,weights=E(h)$weight)
> memberships$`fg` <- fg$membership
> 
> fg10 <- fastgreedy.community(h,weights=E(h)$weight*10)
> memberships$`fg10` <- fg10$membership
> 
> fg100 <- fastgreedy.community(h,weights=E(h)$weight*100)
> memberships$`fg100` <- fg100$membership
> 
> lm <- multilevel.community(h,weights=E(h)$weight) 
> memberships$`lm` <- lm$membership
> 
> lm10 <- multilevel.community(h,weights=E(h)$weight*10) 
> memberships$`lm10` <- lm10$membership
> 
> lm100 <- multilevel.community(h,weights=E(h)$weight*100) 
> memberships$`lm100` <- lm100$membership
> 
> names=V(h)$name
> out <- as.data.frame(memberships)
> commun <- cbind(names,out)
> 
> Any help would be appreciated. Thanks a lot for the wonderful package you 
> maintain.
> 
> Stefano 
> 
> 
> 
> 
> -- 
> Department of Management & Technology and KITes
> 
> Università L. Bocconi
> Via Roentgen 3
> 20136 Milan (Italy)
> Grafton Building 5th floor
> Office B1-02
> tel. +39-02-5836 3365
> fax  +39-02-5836 3399
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help