This repository contains an implementation of the Louvain algorithm in Kotlin.
Louvain algorithm is a greedy optimization method for community detection introduced by Blondel et al. in this paper.
The algorithm optimizes modularity, which is computed as follows:
Where
represents the edge weight between nodes i and j;
are the sum of the weights of the edges attached
to nodes i and j;
is the sum of all the edge weights in the graph;
are the communities of the nodes i and j;
is 1 if arguments are equal, 0 otherwise.
In the first step, each node gets assigned to its own community. At each step the algorithm tries to move each node to a community which fits the node best, based on modularity changes caused by this move. This process is repeated for all nodes until no further modularity increase can occur. In the second step, the algorithm builds a new graph with nodes being communities consisting of nodes of the previous graph, to which the first step can be applied again.
This repository provides two functions in the API file. Both expect a list of objects implementing Link interface as their first argument.
getPartition takes the desired depth of partition as an argument.
Depth is the number of iterations of the algorithm on the resulting communities after getting the first partition.
A map node id : community id is returned.
computeModularity expects a community split as its second argument.
Computes and returns modularity of the given split.
If you encounter any issues, please report them using the issue tracker.