[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: |
Thu, 14 Feb 2013 12:08:17 +0100 |
> 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.