Community Finding with Applications on Phylogentic Networks

by Luís Artur Domingues Rita

MSc thesis presentation and discussion.

Date: 2019-Jun-25   Time: 14:00
Room: IST P3

Abstract: With the advent of high-throughput sequencing methods, new ways of
visualizing and analyzing increasingly amounts of data are needed. Although
some software already exist, they do not scale well or require advanced skills
to be useful in phylogenetics. The aim of this thesis was to implement three
community finding algorithms – Louvain, Infomap and Layered Label Propagation
(LLP); to benchmark them using two synthetic networks – Girvan-Newman (GN) and
Lancichinetti-Fortunato-Radicchi (LFR); 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, and, finally, to
make it all available online (mscthesis.herokuapp.com).  Louvain, Infomap and
LLP were implemented in JavaScript. Unless otherwise stated, next conclusions
are valid for GN and LFR. In terms of speed, Louvain outperformed all others.
Considering accuracy, in networks with well-defined communities, Louvain was
the most accurate. For higher mixing, LLP was the best. Contrarily to weakly
mixed, it is advantageous to increase the resolution parameter in highly mixed
GN. In LFR, higher resolution decreases the accuracy of detection,
independently of the mixing parameter. The increase of the average node degree
enhanced partitioning accuracy and suggested detection by chance was
minimized. It is computationally more intensive to generate GN with higher
mixing or average degree, using the algorithm developed in the thesis or the
LFR implementation. In S. aureus network, Louvain was the fastest and the most
accurate in detecting the clusters of seven groups of strains directly evolved
from the common ancestor.