Whether comparing networks to each other or to random expectation, measuring similarity is essential to understanding the complex phenomena under study. However, there is no canonical way to compare two networks.
Having a notion of distance that is built on theoretically robust first principles and that is interpretable with respect to important features of complex networks would allow for a meaningful comparison between different networks. We introduced an efficient new measure of graph distance, based on the marked length spectrum. It compares the structure of two undirected, unweighted graphs by considering the lengths of non-backtracking cycles. We show how this distance relates to structural features such as the presence of hubs and triangles through the behaviour of the eigenvalues of the non-backtracking matrix, and we showcase its ability to discriminate between networks in both real and synthetic data sets.
In joint work with Leo Torres and Tina Eliassi-Rad we introduced a topological interpretation of non-backtracking cycles as a new homotopical application of topological data analysis to the study of complex networks. In this talk I will explain a manifold learning application developed with Sophie Achard and Luiba Orlov in which we can distinguish networks inferred from fMRI data of healthy and comatose patients.
Copyright. All Rights Reserved.