Louvain Algorithm

Description

This algorithm is divided in 2 phases: Modularity Optimization and Community Aggregation. Just after the first is completed, the second takes place. Louvain will iteratively go through both until we get an optimized partition of the network. Modularity Optimization - At the beginning of this phase, the algorithm will randomly order all the nodes in the network such that, one by one, it will remove and insert it in a different community. This will continue until no significant variation in modularity is achieved (given by a constant defined below - __MIN). Community Aggregation - After finalizing the first pass, every node belonging to the same community is merged into a single giant one and the links connecting these will be formed by the sum of the ones previously connecting nodes from the same different communities. From now on, there will also exist self-loops that represent the sum of all links in a given community (strictly connecting nodes inside of it) before being collapsed into a single one.

Optimizing equation:

Usage

Install package using NPM.

npm i --save louvain-algorithm

Require it using Node.js.

const louvain = require('louvain-algorithm');

Start community finding.

let node2com = louvain.jLouvain(nodes, links, min);

// node2com = {nodeID1: commmunityID1, nodeID2: commmunityID2...}
// nodes = [nodeID1, nodeID2...]
// links = [{source: nodeID1, target: nodeID2, value: weight ...}]
// Whenever the MDL between 2 partitions is lower than a value "min", the iteration stops.

More

Community Finding with Applications on Phylogenetic Networks (Master Thesis)

Louvain, Infomap, Layered Label Propagation, Label Propagation, Hamming Distance, Girvan-Newman Benchmark and Normalized Mutual Information algorithms were developed in JavaScript. To visualize the results, an interface using D3.js (SVG and Canvas) and Cytoscape was implemented. Every community finding algorithm was tested in terms of accuracy, speed and memory against 2 synthetic networks (Girvan-Newman and Lacichinetti-Fortunato-Radicchi networks with varying parameters). Final goal was to cluster microbiological data.

Check out more in the thesis website. You may also download an image of the application in Docker Hub. A description video is below.

Supervision Team

Alexandre Francisco (INESC-ID & IST) | João Carriço (iMM) | Vítor Borges (INSA)