MSc Thesis

mscthesis.herokuapp.com

Community Finding with Applications on Phylogenetic Networks

The aim of the thesis (extended abstract) was to implement three community finding algorithms – Louvain, Infomap and Layered Label Propagation; to benchmark them using two synthetic networks – Girvan-Newman and Lancichinetti-Fortunato-Radicchi; to test them in real networks, particularly, in one derived from a Staphylococcus aureus MLST dataset; to compare visualization frameworks – Cytoscape.js and D3.js (using SVG and Canvas elements), and, finally, to make it all available online.

Implemented Algorithms

• Louvain;
• Infomap;
• Layered Label Propagation (LLP);
• Girvan-Newman (GN) Benchmark Network Generator;
• Normalized Mutual Information (NMI);
• Hamming Distance.

Benchmark & Testing

Synthetic Networks

• Girvan-Newman;
• Lancichinetti-Fortunato-Radicchi (LFR).

Real Networks

• Amazon;
• Zachary's Karate Club;
• Staphylococcus aureus MLST Dataset.

Parameters

Accuracy

Congruence of each partition inferred by Louvain, Infomap and LLP was determined using NMI.

Speed

Time required to run Louvain, Infomap and LLP, in GN and LFR networks, was measured. As well as, the time needed to execute GN Benchmark Network Generator, considering different mixing and average node degree parameters.

Visualization Interface

• Cytoscape.js;
• D3.js (Version 4 & SVG);
• D3.js (Version 4 & Canvas).

Phyl

Web application which integrates all the previous components. Image available in Docker Hub. Description video below.

Supervision Team

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

Roadmap -> Wiki