The IPB colloquium will be held on Wednesday, 29 August 2018 at 12:00 in the “Zvonko Marić” lecture hall of the Institute of Physics Belgrade. The talk entitled

"Graph distance from the topological view of non-backtracking cycles"

will be given by Prof. Dr. Tina Eliassi-Rad (College of Computer and Information Science, Northeastern University, Boston, USA).

Abstract of the talk:

Whether comparing networks to each other or to random expectation, measuring dissimilarity is essential to understanding the complex phenomenon under study. However, determining the structural dissimilarity between networks is an ill-defined problem, as there is no canonical way to compare two networks. Indeed, many of the existing approaches for network comparison differ in their heuristics, efficiency, interpretability, and theoretical soundness. Thus, having a notion of distance that is built on theoretically robust first principles and that is interpretable with respect to features ubiquitous in complex networks would allow for a meaningful comparison between different networks. In this talk, we will introduce a theoretically sound and efficient new measure of graph distance, based on the length spectrum function from algebraic topology, which compares the structure of two undirected, unweighted graphs by considering their non-backtracking cycles. We will show how this distance relates to structural features such as presence of hubs and triangles through the behavior of the eigenvalues of the non-backtracking matrix, and showcase its ability to discriminate between networks in both real and synthetic data sets. By taking a topological interpretation of non-backtracking cycles, this work presents a novel application of topological data analysis to the study of complex networks.

• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
•