Skip to main content

Marina Herrera Sarrias: Comparing Networks using Shape-aware Graph Distances

Time: Wed 2021-06-09 14.15 - 15.00

Location: Zoom, meeting ID: 611 3329 7865

Lecturer: Marina Herrera Sarrias

Abstract

Complex networks, i.e., graphs with non-trivial topological features, have been studied intensively in past decades since they provide us with intuitive graphical representation to study a wide variety of natural systems, such as social, economical and biological systems. A fundamental question in network theory is how to compare and classify networks, which requires the formulation of appropriate distance measures that distinguish networks with different structures. Stemmed from graph theory, a major class of network distances is constructed from the spectrum of the graph Laplacian. Recently, Shimada et al. extended this class and proposed the spectral graph distance (SGD) in terms of the eigenvectors of the graph Laplacian. It has been argued the SGD can be more effective in comparing networks with different structures and sizes.

Nevertheless, we found that SGD suffers from several pitfalls, namely, incorrect weighting of eigenvector contributions, ignoring couplings between eigenmodes, etc., that can lead to artifacts in comparing networks. To overcome the above pitfalls, we recently formulated a novel network distance, termed shape-aware graph distance (SAGD). The SAGD not only weights the eigenmodes of the graph Laplacian accordingly without neglecting their couplings, but also incorporates with global network structural (or shape-aware) information. In this talk, I will give an intuitive introduction of SGD, SAGD and the related graph concepts. To demonstrate the significance of SAGD compared with other network distances, such as the Hamming distance, SGD, etc., I will demonstrate the performance of SAGD in terms of well-known graphs with structural properties commonly found in real systems. These include the small-world networks (Watts-Strogatz model), and the weighted community-rich networks proposed by Kumpula et al.

Page responsible:webmaster@math.kth.se
Belongs to: Department of Mathematics
Last changed: Jun 08, 2021