[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] Multilevel vs Label propagation
From: |
Tamás Nepusz |
Subject: |
Re: [igraph] Multilevel vs Label propagation |
Date: |
Wed, 20 Feb 2013 22:19:52 +0100 |
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