Louvain
Java implementation of the Louvain method for community detection.
Input: weighted, undirected graph, defined in a CSV file as a list of edges. See the graphs at src/test/resources for examples. Nodes may be named or indexed, and the indexes do not have to start at zero or be continuous.
Features
- Read graphs from files, build manually, or generate random Erdős–Rényi graphs.
- Detect communities using the Louvain method and calculate the modularity of the resulting clustering.
- Read infomap output files.
- Compare different clusterings of a graph using Normalised Mutual Information (NMI).
- Assign nodes to random communities (for baseline comparisons of a clustering).
- Read and write community structures to disk.
Examples
Load a graph file and detect communities using the Louvain method, and print the modularity of the detected communities:
final Graph g = new GraphBuilder().fromFile("src/test/resources/graphs/arxiv.txt", true);
final LouvainDetector ld = new LouvainDetector(g);
final LayeredCommunityStructure cs = ld.cluster();
System.out.println(ld.modularity());Load a graph file and detect communities using the Louvain method, then compare each layer with each layer from a loaded infomap file:
final Graph g = new GraphBuilder().fromFile("src/test/resources/graphs/arxiv.txt", true);
final LouvainDetector ld = new LouvainDetector(g);
final LayeredCommunityStructure cs = ld.cluster();
final InfomapResultsReader irr = new InfomapResultsReader("graphs/infomap.tree");
final LayeredCommunityStructure cs2 = irr.cluster();
for (int i = 0; i < cs.layers(); i++) {
for (int j = 0; j < cs2.layers(); j++) {
System.out.printf("%.03f ", NMI.NMI(cs.layer(i), cs2.layer(j)));
}
System.out.println();
}Generate an Erdős–Rényi graph, detect communities using the Louvain method, and compare the NMI of those communities to randomly-assigned communities of the same size:
final Graph g = new GraphBuilder().erdosRenyi(1000, 0.1);
final LouvainDetector ld = new LouvainDetector(g);
final LayeredCommunityStructure cs = ld.cluster();
RandomCommunityAssigner rca = new RandomCommunityAssigner(cs);
final LayeredCommunityStructure cs2 = rca.cluster();
for (int i = 0; i < cs.layers(); i++) {
for (int j = 0; j < cs2.layers(); j++) {
System.out.printf("%.03f ", NMI.NMI(cs.layer(i), cs2.layer(j)));
}
System.out.println();
}Run the Louvain community detection 10 times, and write the clustering with the best modularity to a file:
final Graph g = new GraphBuilder().erdosRenyi(1000, 0.1);
final LouvainSelector ls = new LouvainSelector("src/test/resources/graphs/arxiv.txt", "out.csv");
final LayeredCommunityStructure cs = ls.cluster(10);Licensing
License: MIT
| Dependency | License |
|---|---|
| log4j2 | Apache 2.0 |
| trove4j | LGPL |
| junit | Eclipse 1.0 |