Spectral aspects of mining complex networks: geometry, topology, and dynamics
Dissertation Defense
Past Talk
Leonardo Torres
Network Science PhD Candidate
Wednesday
Jul 21, 2021
Watch video
3:00 pm
177 Huntington Ave
Online
11th floor
Join Talk (Zoom)

Traditionally, the study of complex networks has employed mathematical tools from graph theory and statistical physics. More recently, topological data analysis has introduced the application of algebraic topology to network science, opening up new possibilities. This dissertation takes a similar direction by drawing on topological and geometrical aspects of graph theory to develop data mining algorithms that provide new scientific insights into complex networks.

I consider the geometric structure of networks at many levels. First, I study the intrinsic metric structure of a graph using the theory of \emph{length spectrum} and its relation to the eigenvalues of the \emph{non-backtracking matrix} of the graph. I use this relationship to develop a principled algorithm for measuring graph distance. Second, I study the geometric structure of graph embeddings. Graph embedding techniques place a graph in a surrounding metric space. I use the geometry of this space to develop two embedding algorithms that enable the performance of such tasks such as link prediction and anomaly detection in an efficient and interpretable manner. Third, because considering distances between graphs depends on the assumption that graphs with similar structure exhibit similar behavior, I study how certain dynamical properties of graphs change under small perturbations of their structure. In particular, I focus on how small perturbations to the structure of the graph affect the epidemic threshold of certain dynamics. I introduce two algorithms that effectively manipulate the epidemic threshold by exploiting the relationship between the graph structure and its spectral properties.

I conclude with a reflection on the current trend in network science to rethink the study of complex systems in terms of polyadic relations. My collaborators and I find that a necessary step in this direction is to focus on the properties of real-world systems that determine which relationships affect the existence of other relationships. I discuss this property, which I call \textit{dependency}, in the context of graphs, simplicial complexes, and hypergraphs.

Dissertation Committee:
Tina Eliassi-Rad, Khoury College (Chair)
Cristopher Moore, Santa Fe Institute
Dima Krioukov, College of Science
Hongyang Zhang, Khoury College

About the speaker
About the speaker

Leo is a fifth year PhD student working with Tina Eliassi-Rad. He is broadly interested in the intersection of Network Science, Computer Science, and Mathematics. He studies complex networks by applying different fields of mathematics, such as differential and metric geometry, and algebraic topology; and different computational approaches such as graph mining and machine learning. Currently, his main research focus is to introduce novel mathematical tools to the network science toolbox, and design efficient algorithms around them to uncover previously unknown features of networks. Leo has a B.S. in Mathematics from Pontificia Universidad Católica del Perú, and has held positions as mathematics instructor at the undergraduate level, Spanish teacher, and research programmer at Wolfram Research South America.

No upcoming events

View all