2
$\begingroup$

I am not able to find out the computational complexity of the Louvain Algorithm. Can anyone here help me? link of the paper given below:

DOI: 10.1088/1742-5468/2008/10/P10008

https://doi.org/10.1038/s41598-019-41695-z.

enter image description here

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Apparently, it runs in time $O(n \log(n))$: en.wikipedia.org/wiki/Louvain_method. $\endgroup$
    – Luc Guyot
    Commented Dec 16, 2020 at 17:46
  • 2
    $\begingroup$ This $O(n\log(n))$ complexity is empirically observed on practical instance, but there is no proof, and I doubt non-trivial complexity is known. $\endgroup$
    – Matthieu Latapy
    Commented Dec 21, 2020 at 23:13
  • $\begingroup$ The paper cited in the Wikipedia article doesn't appear to actually state an $O(n\log(n))$ complexity for Louvain. They do claim without proof that it "is essentially linear in the number of links of the graph". Maybe I missed something? $\endgroup$
    – rlchqrd
    Commented Jun 29, 2021 at 18:13

0

Reset to default

You must log in to answer this question.