Physics-Inspired Graph Clustering Algorithms

我将在图/网络理论领域进行研究，特别是图聚类。聚类包括将一组对象分组到称为“集群”的组中，其中集群内的对象彼此之间比其他集群中的对象更相似。通常，数据被描述为图形。在这种情况下，聚类的目标是将共享相似连接属性的图的顶点分组在一起。这个定义可以扩展到有向图，其中顶点对之间的关系有一个方向（即，是非对称的），或动态图，其中边的权重随时间而变化。虽然无向图上的图聚类研究得很好，但有向图的图聚类却知之甚少，这可能是由于有向图引起的不对称导致矩阵中可用于描述和编码图结构信息的可解释性较差。我的研究目标将是设计新的算法来超越无向静态情况的聚类图。我的方法将使用从物理过程（如热扩散）中产生的直觉，以及用线性代数方法研究图的谱图理论。至少在我研究的早期阶段，我将关注有向图的聚类问题。特别地，我将尝试设计一种基于两个主要组成部分的算法：(1)热核算子，它传统上描述了当一些热能放在某一区域的一点上时温度的演变；(2) Cucuringu等人最近研究的用于聚类的有向图的厄米表示，我已经进行了初步的实验研究，表明基于这两个关键组成部分的算法能够在某些有向图中使用基真聚类恢复正确的聚类。我还与Mihai Cucuringu（牛津）、Yves van Gennip（代尔夫特）和Andrea Pizzoferrato （nChain）讨论了我的发现，他们是图聚类的热扩散方法专家。在接下来的几个月里，我将专注于对这种算法进行彻底的实验研究。我还将尝试对该算法进行理论分析。在未来，我计划将聚类技术推广到其他设置，如动态图（其中边缘随时间变化）和超图（其中交互可能涉及两个以上的顶点）。同样，我的计划是设计受物理过程（例如，热扩散或Allen-Cahn方程）以及最近将谱图理论推广到动态图和超图的算法。

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.