The problem of multiway partitioning of an undirected graph is considered. A spectral method is used, where the k > 2 largest eigenvalues of the normalized adjacency matrix (equivalently, the k smallest eigenvalues of the normalized graph Laplacian) are computed. It is shown that the information necessary for partitioning is contained in the subspace spanned by the k eigenvectors. The partitioning is encoded in a matrix $\Psi$ in indicator form, which is computed by approximating the eigenvector matrix by a product of $\Psi$ and an orthogonal matrix. A measure of the distance of a graph to being k-partitionable is defined, as well as two cut (cost) functions, for which Cheeger inequalities are proved; thus the relation between the eigenvalue and partitioning problems is established. Numerical examples are given that demonstrate that the partitioning algorithm is efficient and robust.
翻译:考虑未定向图形的多路分割问题。 使用光谱方法, 使用正态对称矩阵的 k > 2 最大 egen值( 等同, 普通图形 Laplacian 的 k最小 egen值) 计算。 显示分隔所需的信息包含在 k 源源的子空间中。 分割以指标形式在矩阵中编码, 以美元=Psi$为单位计算, 由 $\Psi$ 和 正方形矩阵的产物对等计算。 定义了可分割图形的距离, 以及两个切割功能( 成本), Cheeger 的不平等得到了证明; 因此, 确定了断层值和分隔问题之间的关系。 给出的数值示例表明, 分配算法是有效和稳健的。