Physics-Inspired Graph Clustering Algorithms

受物理启发的图聚类算法

• 批准号: 2748617
• 金额: --
• 依托单位: University of Bath
• 依托单位国家: 英国
• 项目类别: Studentship
• 财政年份: 2022
• 资助国家: 英国
• 起止时间: 2022 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=studentship-2748617
• 关键词: 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.

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