[igraph] Multilevel vs Label propagation

[Zhige Xin]

Hi dear all,

I have tested two community detection methods for some data sets. One is community_multilevel() and 

the other one is community_label_propagation(). The results surprised me because the LPA is very slower

than the multilevel algorithm but theoretically the LPA is superior since it is linear. I do not get it.

The following is my testing results:

data set:         Internet(nodes:22963,edges:48436)         collaboration(40421,175692)

Multilevel:       0.5454 seconds                                      2.3077 seconds

LPA:               29.4948 seconds                                    184.7579 seconds

BTW, all the data sets are gml file format and can be downloaded from Mark Newman's homepage.

And the following is my testing platform:

Cpu: intel core2    1.7 GHz

Memory: 2GB

Hard drive: 320GB 5400rpm

OS: Linux Mint 14

Language: python 2.7

Library: igraph

Thanks!

Isaiah