Re: [igraph] Multilevel vs Label propagation

[Tamás Nepusz]

> than the multilevel algorithm but theoretically the LPA is superior since it 
> is linear.
There are at least three catches here:

1) The multilevel algorithm is also claimed to be "near linear" on sparse 
graphs. We haven't benchmarked it, this is what is written in the publication 
of the multilevel algorithm. If it is indeed "near linear", similarly to the 
label propagation algorithm, then this could be a possible explanation.

2) Although the label propagation algorithm is in theory linear, there is no 
estimate about how many iterations the algorithm will take until it reaches 
convergence. It could be the case that lots of iterations are needed until 
convergence for the LPA but not for the multilevel algorithm.

3) It could be the case that we screwed up something and our LPA implementation 
is not linear after all ;) I will check the LPA code once we're done with the 
release of the next minor version to see if there is room for improvement.

-- 
T.