Graphlet Counting for Topological Data Analysis

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.