Skip to content

[Work in progress] A Rust implementation of the Louvain algorithm ๐ŸŽˆ

License

Notifications You must be signed in to change notification settings

Splines/fast-louvain

Folders and files

NameName
Last commit message
Last commit date

Latest commit

ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 

Repository files navigation

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:

Resulting Louvain hierarchy for a sample graph in the documentation



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

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-social-preview