基于傅里叶相似变换的图距离矩阵分解研究

Research on Graph Distance Matrix Decomposition Based on Fourier Similarity Transformation

摘要: 本文考虑图距离矩阵的分解问题。给定一个图，根据其顶点集的划分，我们定义了图距离矩阵的傅里叶相似变换。该变换由用于执行离散傅里叶变换的矩阵乘以图距离矩阵实现。我们证明了图距离矩阵在傅里叶相似变换下能够分解成多个较小矩阵的直和，当且仅当该图的顶点划分是距离公平划分。

Abstract: This paper considers the problem of decomposition of graph distance matrix. Given a graph, we define a Fourier similarity transform of its graph distance matrix based on the vertex partition, which is implemented by multiplying the matrices used to perform the Discrete Fourier transformation. We show that graph distance matrices can be decomposed into many smaller matrices under Fourier similarity transformation, if and only if the vertex partition of the graph is a distance equitable partition.