I am looking for a clustering algorithm that is scalable up to large sparse undirected, unweighted networks (10-40M nodes, 10-80M edges). The most important aspects I care about are scaling efficiency to this size network and maybe consistency/stability. I'm mostly interested in this as a way to try and understand the network in more detail. I'm open to many types of clustering (including overlapping clusters, etc.).
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ Have you checked out networkit? $\endgroup$– Pål GDDec 2, 2021 at 20:49
-
1$\begingroup$ There they use Staudt, C. L., & Meyerhenke, H. (2015). Engineering parallel algorithms for community detection in massive networks. IEEE Transactions on Parallel and Distributed Systems, 27(1), 171-184. for their community detection algorithm. $\endgroup$– Pål GDDec 2, 2021 at 20:50
-
1$\begingroup$ Check also out the results from the very recent PACE Challenge on Cluster Editing. $\endgroup$– Pål GDDec 2, 2021 at 20:52
-
1$\begingroup$ Another reference from Networkit is Raghavan, U. N., Albert, R., & Kumara, S. (2007). Near linear time algorithm to detect community structures in large-scale networks. Physical review E, 76(3), 036106. $\endgroup$– Pål GDDec 2, 2021 at 20:53
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
The Louvain algorithm does just this, and it easily handles graphs of this size. It is implemented in most, if not all, graph libraries. In particular, Networkit provides a fast parallel implementation. If you are interested in clusters only, you may use a dedicated implementation like the generalized version documented in this paper.
-
$\begingroup$ Thank you, this is perfect. And thanks to you and Pål for the reference to NetworKit which is such an improvement over NetworkX for memory use and performance! $\endgroup$– sligockiDec 4, 2021 at 14:45