Theory and Applications of Latent Network Geometry
Dissertation Defense
Past Event
Ivan Voitalov
PhD Candidate
Friday
Oct 16, 2020
Watch video
10:00 am
177 Huntington Ave
Online
Join Talk (Zoom)
11th floor

During the past two decades, a multitude of statistical network models were developed to capture and explain the ubiquitous large-scale structural features observed in many real networks -- heterogeneous distribution of nodes' degrees, sparseness, strong clustering, and small-world effect. Despite the existence of many models that capture some of these features, to the best of our knowledge, only the non-Euclidean latent-geometric network models are capable to accurately model all the large-scale structural features simultaneously. However, several important theoretical and application-oriented research questions related to these models are still unanswered. In this dissertation, we address some of them.

First, we focus on a long-lasting question of identification of scale-free distributions in real networks that helps us to understand what scale-free networks are, and how omnipresent they are in real systems. Second, we review the current state-of-the-art latent-space network models with underlying hyperbolic geometry suited for modeling both static and growing networks, and outline their relation to the unbiased statistical models of graphs based on the principle of maximum entropy. Third, we make the first step towards extending maximum-entropy latent-geometric models to weighted networks by building a maximum-entropy weighted network model with given distributional constraints on the joint degree-strength distribution, the Weighted Hypersoft Configuration Model.

Next, we introduce the currently most accurate algorithm for finding hyperbolic embedding of real networks --- HyperLink. Using this algorithm, we turn to the applications of latent network geometry. We first consider link prediction using hyperbolic geometry. We analyze the interplay between the embedding accuracy and link prediction performance, and find that hyperbolic geometry may be extremely useful in identification of hard-to-predict links.

We then show how latent hyperbolic geometry may be used to design maximally scalable and efficient routing and addressing schemes for communication networks. Finally, we demonstrate how hyperbolic geometry may help to better understand information communication mechanisms in neural networks using as an example the Drosophila melanogaster brain network map at a single-neuron resolution.

The work presented in this dissertation addresses both core theoretical questions in network science, as well as very practical aspects of latent network geometry. The results presented here open new latent-geometric perspectives in network science with immediate applications to many other related fields including machine learning, bioinformatics, communication networks, and neuroscience.

About the speaker
Ivan is a Ph.D. Candidate in Physics working with Professor Dmitri Krioukov at the DK Lab. Combining the tools from hyperbolic geometry, graph theory, statistical physics and data analysis, he is trying to understand how to better predict and control behavior and structure of real-world complex networks. Particularly, he is interested in geometry-based navigation and link prediction on networks as well as possible generalizations of latent hyperbolic geometry framework to weighted graphs. Ivan received his Bachelor's degree in Physics from the V.N. Karazin Kharkiv National University.