论文标题
基于库普曼的指示图和随时间变化图的光谱聚类
Koopman-based spectral clustering of directed and time-evolving graphs
论文作者
论文摘要
虽然已建立了无向图的光谱聚类算法，并且已成功地应用于无监督的机器学习问题，从图像分割和基因组测序到信号处理和社交网络分析，但众所周知，有针对性的图仍然困难。主要挑战的两个是，与有向图相关的图形拉普拉斯人的特征值和特征向量是一般的复杂值，并且在有向图中没有普遍接受的群集的定义。我们首先利用图形拉普拉斯和转移操作员之间的关系，尤其是在无方向图中的群集和随机动力学系统中的可稳定集中的群集之间的关系，然后使用亚稳定性的概念的概括来推导群集算法，以进行定向和时间变化图。所得的簇可以解释为连贯的集合，在流体流中的运输和混合过程中起重要作用。
While spectral clustering algorithms for undirected graphs are well established and have been successfully applied to unsupervised machine learning problems ranging from image segmentation and genome sequencing to signal processing and social network analysis, clustering directed graphs remains notoriously difficult. Two of the main challenges are that the eigenvalues and eigenvectors of graph Laplacians associated with directed graphs are in general complex-valued and that there is no universally accepted definition of clusters in directed graphs. We first exploit relationships between the graph Laplacian and transfer operators and in particular between clusters in undirected graphs and metastable sets in stochastic dynamical systems and then use a generalization of the notion of metastability to derive clustering algorithms for directed and time-evolving graphs. The resulting clusters can be interpreted as coherent sets, which play an important role in the analysis of transport and mixing processes in fluid flows.
