Physics-Inspired Graph Clustering Algorithms

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

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.