Re: [igraph] Multilevel vs Label propagation

[Zhige Xin]

Hi,

OK. Thank you!

On Wed, Feb 20, 2013 at 1:19 PM, Tamás Nepusz <address@hidden> 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 <address@hidden> 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
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help


_______________________________________________
igraph-help mailing list
address@hidden
https://lists.nongnu.org/mailman/listinfo/igraph-help