Re: [igraph] Multilevel vs Label propagation

[Tamás Nepusz]

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