Physics-Inspired Graph Clustering Algorithms

点击翻译按钮获取中文摘要

I will be doing research in the field of graph/network theory, in particular, graph clustering. Clustering involves grouping a set of objects into groups called 'clusters' where the objects within the clusters are more similar to each other than to those in other clusters. Often, data is described as a graph. In this case, the goal of clustering is to group together vertices of the graph that share similar connectivity properties. This definition can be extended to directed graphs, where the relation between pairs of vertices has a direction (i.e., is non-symmetric), or to dynamic graphs, where the weights of the edges change over time. While graph clustering on undirected graphs is very well-studied, graph clustering for directed graphs is much less understood, likely due to the asymmetry induced by directed graphs resulting in less interpretable properties in matrices that can be used to describe and encode information about the graph's structure.The goal of my research will be to design new algorithms to cluster graphs beyond the undirected static case. My approach will use intuition arising from physical processes (such as heat diffusion) together with spectral graph theory, which studies graphs with linear-algebraic means.For at least the early stages of my research, I will be focusing on the problem of clustering directed graphs. In particular, I will be attempting to design an algorithm which is based on two main components: (1) a heat kernel operator, which traditionally describes the evolution of the temperature in time when some heat energy is placed on a point of a certain domain; (2) Hermitian representations of directed graphs that have been recently studied for clustering by Cucuringu et al.I have already performed preliminary experimental studies that show that an algorithm based on these two key components is able to recover the correct clustering in certain digraphs with a ground-truth clustering. I have also discussed my findings with Mihai Cucuringu (Oxford), Yves van Gennip (Delft), and Andrea Pizzoferrato (nChain), who are expert on heat diffusion methods for graph clustering.In the next few months, I will be focusing on a thorough experimental investigation of such algorithm. I will also attempt to provide a theoretical analysis of the algorithm.In the future, I plan to generalise clustering techniques to other settings such as dynamic graphs (in which edges change over time) and hypergraphs (in which the interactions can involve more than two vertices). My plan is, again, to design algorithms inspired by physical processes (such as, for example, heat diffusion or the Allen-Cahn equation) together with recent generalisations of spectral graph theory to dynamic graphs and hypergraphs.