search

vtraag / leidenalg

Implementation of the Leiden algorithm for various quality functions to be used with igraph in Python.
GNU General Public License v3.0
606 stars 78 forks source link

How much is the space and time complexity of leiden algorithm? #94

Closed suzuki-shm closed 2 years ago

suzuki-shm commented 2 years ago

I have checked several sources but could not find any description. Let me ask a question regarding complexity. It is noted that the time complexity of Louvain clustering is O(n logn). As Leiden algorithm is faster than Louvain, I think it may have better time complexity. I would like to refer this to select a computational resource.

vtraag commented 2 years ago

As far as I know there is no theoretical result of the time complexity of Louvain or Leiden, only empirical analyses that suggest it roughly scales as O(n) or O(n log n), with n being the number of nodes. Experimental results shows that Leiden roughly scales similar to Louvain, see Fig. 5, but with a smaller constant.

Regarding the memory required, in addition to the memory for the graph itself, which is O(n + m), the memory required for the algorithm itself is O(n), with m being the number of edges.

suzuki-shm commented 2 years ago

@vtraag Thank you for providing a special insight! It helped me a lot.