1
$\begingroup$

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.).

$\endgroup$
4
  • 1
    $\begingroup$ Have you checked out networkit? $\endgroup$
    – Pål GD
    Dec 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 GD
    Dec 2, 2021 at 20:50
  • 1
    $\begingroup$ Check also out the results from the very recent PACE Challenge on Cluster Editing. $\endgroup$
    – Pål GD
    Dec 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 GD
    Dec 2, 2021 at 20:53

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\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$
    – sligocki
    Dec 4, 2021 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.