splines/fast-louvain

[Work in progress] A Rust implementation of the Louvain algorithm 🎈

Fast Louvain

Rust implementation of the Louvain algorithm for community detection in large networks.

Works on undirected, weighted graphs (weights are optional).

🔄	This project is currently in its initial construction phase. Once a first workable version is accomplished, I will publish a release.

Current status of this project (2023-08-01): the first version including CLI usage works, but of course all command line flags etc. might change. Until the first release, we need to add more tests, especially tests that automatically verify results by running the original Louvain implementation and this Rust implementation. We should also include a CLI command to compute modularity for arbitrary node-community assignments. As the project is called "fast-louvain", we should also add benchmarks and improve the speed, e.g. speeding up the increase_edge_weight() method with more appropriate data structures. In the long run, this project should also become available as ready-to-use cargo library (besides the CLI).

📜	The documentation book (work in progress) includes a detailed description of modularity (including derivations of formulas) and the Louvain algorithm. It explains and motivates the use of the Louvain method and illustrates key aspects with images, e.g. this one:

CLI usage

You can use the louvain binary (download here, TODO) or run the crate directly with cargo by using the just command runner (see below).

Run the Louvain algorithm and save the resulting communities as well as the complete hierarchy:

./louvain community ./my-graph.csv -s ./final-assignment.csv -h ./hierarchy.tmp

Having stored the ./hierarchy.tmp file, you can use it to extract the communities at a specific level (here level 2):

./louvain hierarchy ./hierarchy.tmp -s ./assignment.csv -l 2

For more information, run ./louvain --help.

Build & Run

Have Cargo installed. Then:

cargo install just (a great command runner written in Rust)
just run-release (or short: just rr)

e.g. your command could like this:

just rr community ./my-graph.csv -s ./final-assignment.csv -h ./hierarchy.tmp

• To list all available commands (not Louvain commands, rather project-related commands, e.g. to test the code, build it etc.), run just.
• To see the commands for a specific task, run just --show <task> or just (no pun) open the .justfile.
• To see the commands for how to use the Louvain CLI, run just rr -- -h or directly invoke the binary ./louvain -h.

Graph file format

The input graph must be stored in a simple CSV file that looks like this (header is mandatory):

source,target,weight
0,0,1.0
0,1,3.1415

or without weights (in this case, we assume weight 1.0 for all edges):

source,target
0,0
0,1

For the community command: with the -s option, the final community assignment is stored in a CSV file like this:

node,community
0,0
1,0

With the -h option, the hierarchy is stored in a temporary file:

[[0,0,0,3,0,0,3,3,1,1,1,2,1,2,1,1],[1,0,0,1]]
[-0.07142857142857144,0.3748558246828143,0.42524005486968447]

You can read in this file to get the node-to-community assignment as CSV file for one specific level (see CLI usage above).

References

• Original Louvain implementation (C++) and an overview page of Louvain
• Original paper by Blondel, Guillaume, Lambiotte and Lefebvre: Fast unfolding of communities in large networks
• See more references in the documentation book
• If you need a directed version of Louvain, see this repo by Dugué and Perez.

License

The source code of this program is licensed with the very permissive MIT license, see the LICENSE file for details. When you use this project (e.g. make a fork that becomes its own project), I do not require you to include the license header in every source file, however you must include it at the root of your project. According to the MIT license you must also include a copyright notice, that is, link back to this project, e.g. in this way:

Fast Louvain - Copyright (c) 2023 Splines

Any questions regarding the license? This FAQ might help.

Note that the documentation book is exempt from the MIT license. Redistribution of the documentation book is not permitted. Yet, you are welcome to reference it in your own work.

fast-louvain's Issues

Find best community to move into: don't check previous community

Checking the previous community and calculating the gain for it is completely unnecessary. If the node is inserted back into its previous community, we know that the total net gain is 0, so no need to calculate that again.

https://github.com/Splines/fast-louvain/blob/main/modules/application/src/louvain_level.rs#L129-L142

Support popular GraphML file format for graphs

not just CSV files as is currently

Add `visualizer`

We want to visualize the Louvain algorithm. This could be done by instrumenting the code, e.g. write specific log statements, that can later be parsed by the visualizer to create the animation programatically, e.g. using Manim.

Important Requirement: We should be able to disable the instrumentation for release builds to not affect runtime.

What about big graphs? Animate camera as well?

CLI: Hierarchy level 0

Consistent with the original implementation, hierarchy level 0 should not output the final level (we could output that for example with -1), but instead the trivial assignment where every node is in its own singleton community.

Random order of nodes not reset for next iteration

Still in development?

HI, I am long time lover of genlovauin since the old matlab wrapper. I am currently working with Polars dataframes and my data often have a graph representation via vectorization and neighborhood construction, I would be very interested in using this crate if it is still under development.

Add python bindings