Higham, Desmond

Zygalakis, Kostas

Gong, Xue

Engineering and Physical Sciences Research Council (EPSRC)

2023-12-12T11:44:11Z

2023-12-12T11:44:11Z

2023-12-12

The spectral properties of Laplacian matrices offer valuable insights into the structure of graphs. One significant application is the embedding of nodes into a low-dimensional Euclidean space using the eigenvectors of a suitable Laplacian matrix, enabling the recovery of the underlying connection pattern. Such embedding proves relevant for various subsequent learning tasks, including node reordering, clustering, and visualization. Despite extensive research on undirected graph Laplacians, there remains a gap in analyzing more complex graph structures. This includes situations where relationships are asymmetrical and represented by directed edges, as well as scenarios involving interactions among more than two agents, effectively captured using hypergraphs or simplicial complexes. To address this research gap, we investigate mathematical frameworks utilizing graph Laplacians for directed networks, hypergraphs, and directed simplicial complexes. For directed graphs, we examine two existing Laplacian matrices associated with periodic and linear structures and developed corresponding generative models. Specifically, we establish and exploit connections between node reordering techniques, achieved through minimizing an objective function, and maximizing the likelihood of a random graph model. Leveraging this random graph framework, we compare the likelihood of each structure. Numerical experiments are conducted using synthetic graphs and graphs from social sciences, biology, and ecology. Furthermore, we extend this framework to hypergraphs and demonstrate its efficacy in quantifying structure strength, performing clustering, and predicting hyperedges on synthetic hypergraphs and social networks. Additionally, we define and analyze a new first-order Magnetic Hodge Laplacian for directed simplicial complexes, capturing directional flows on triangles. Through the analysis of triangle and torus examples, we showcase its ability to discover direction-related patterns.

https://hdl.handle.net/1842/41276

http://dx.doi.org/10.7488/era/4012

en

The University of Edinburgh

Xue Gong, Desmond J. Higham, and Konstantinos Zygalakis. Directed network laplacians and random graph models. Royal Society Open Science, 8(10):211144, 2021.

Xue Gong, Desmond J. Higham, and Konstantinos Zygalakis. Generative hypergraph models and spectral embedding. Scientific Reports, 13(1):540, 2023

spectral methods

graph Laplacian

graph algorithms

graph computation

Hodge Laplacian

graph model

Laplacians for structure recovery on directed and higher-order graphs

Thesis or Dissertation

Doctoral

PhD Doctor of Philosophy