Hi, So I've checked our implementation of community_label_propagation() and it is indeed quadratic, not linear. The reason is that we are using a dense vector to count the number of occurrences of labels in the neighborhood of a node, and clearing this vector takes O(n) time, while it would be O(1) with a proper sparse vector. I will come up with a better implementation soon(ish).
-- T. On 14 Feb 2013, at 00:44, Zhige Xin <[email protected]> wrote: > 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 > > _______________________________________________ > igraph-help mailing list > [email protected] > https://lists.nongnu.org/mailman/listinfo/igraph-help _______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
