Community finding algorithm.
npm install louvain-algorithmThis 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:
Install package using NPM.
``cmd`
npm i --save louvain-algorithm
Require it using Node.js.
`node`
const louvain = require('louvain-algorithm');
Start community finding.
`node
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.
``
#### 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)