> 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. _______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
