Politecnico di Torino (logo)

Graphlet Counting for Topological Data Analysis

Marco Guerra

Graphlet Counting for Topological Data Analysis.

Rel. Francesco Vaccarino. Politecnico di Torino, Corso di laurea magistrale in Ingegneria Matematica, 2018

PDF (Tesi_di_laurea) - Tesi
Licenza: Creative Commons Attribution Non-commercial No Derivatives.

Download (5MB) | Preview

GRAPHLET COUNTING FOR TOPOLOGICAL DATA ANALYSIS In the present work we focus on computing the shortest possible basis of the first homology group H_1 of a weighted simplicial complex. The task is proved to be an NP-hard problem for H_k with k > 1, but the k=1 case is subject of recent research. Taking the lead from the recent work of Dey, which borrows ideas from previous studies to improve computational complexity, we have implemented a polynomial-time algorithm for the shortest homology basis of a simplicial complex over Z_2 coefficients and extended it to compute persistence over a family of its refinements. The final objective is to experiment with existing datasets of neuroscientific measurements, in the light of the framework proposed in a recent paper, where a new topological object called homological scaffold is introduced to evaluate brain neuron activity correlations at a mesoscopic level, interpreting holes as inhomogeneities in the network structure. The algorithm has been tested on real-world examples concerning neural activity of a model organism, the nematode worm C. Elegans, and large aggregates of fMRi data of patients affected by autism provided through the Autism Brain Imaging Data Exchange initiative. The foreseeable developments include incorporating the method in the pipeline of the scaffold computation, as an effort to shed light on challenging questions in neuroscience.

Relators: Francesco Vaccarino
Academic year: 2017/18
Publication type: Electronic
Number of Pages: 100
Corso di laurea: Corso di laurea magistrale in Ingegneria Matematica
Classe di laurea: New organization > Master science > LM-44 - MATHEMATICAL MODELLING FOR ENGINEERING
Aziende collaboratrici: UNSPECIFIED
URI: http://webthesis.biblio.polito.it/id/eprint/7641
Modify record (reserved for operators) Modify record (reserved for operators)