Implementation of Louvain Algorithm

[jamesdbaker]

The Louvain algorithm is commonly used to identify communities in graphs, and is present in other libraries/tools such as NetworkX and Neo4J.

It would be great if an implementation was available in RustworkX too.

[IvanIsCoding]

I think this is a good ask. Right not we have no community detection algorithms implemented, but this could be an effort like #315 to start implementing those.

Sometimes it is just a matter that no one asked for them before

[jamestwebber]

A general question: is the goal of rustworkx to include algorithms like this out-of-the-box, or would it be better to support third-party packages for things like this? I see that networkx includes Louvain now, but originally it was a separate package. Similarly leidenalg implements community-detection on igraph graphs.

One thing I don't know: how complicated is it to write a package that works with rustworkx graphs in a performant way (i.e. not going through python when possible)? One item on my ever-growing list of projects is to try to implement Leiden (or similar) in Rust in a way that's compatible with rustworkx, potentially using the underlying graph structures directly.

[IvanIsCoding]

Firstly, our goal is to expand the graph library. Most of the existing algorithms started like this, someone needed a specific algorithm and we eventually implemented it. There is a lot of upfront cost with implementation & testing for correctness, but once it is released generally our maintenance for algorithms has been pretty easy.

Secondly, using rustworkx from Python is easy, you can check some of the works citing our paper and Qiskit itself.
Also, using rustworkx-core from Rust is also easy, that is the approach some of Qiskit Rust modules use.

However, using rustworkx from other Rust code is currently blocked and you can see some discussion in #663. My general suggestion would be to call graph.edge_list() or graph.weighted_edge_list() from a Python object in PyO3 and then rebuild a rustworkx-core graph or just use that data directly in your algorithm.

[IvanIsCoding]

One last thought: for leiden specifically, I think if you build upon petgraph and rustworkx-core it would make life simpler to port your own version to be included in rustworkx. And we would gladly merge & distribute it if you made a PR submitting it!