Hi, OK. Thank you!
On Wed, Feb 20, 2013 at 1:19 PM, Tamás Nepusz <[email protected]> wrote: > 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 >
_______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
