On Compact Graphs

Let G be a finite simple graph with adjacency matrix A, and let P（A） be the convex closure of the set of all permutation matrices commuting with A. G is said to be compact if every doubly stochastic matrix which commutes with A is in P（A）. In this paper, we characterize 3-regular compact graphs and prove that if G is a connected regular compact graph, G - v is also compact, and give a family of almost regular compact connected graphs.

图与复杂网络的拉普拉斯谱(英文)

总结了图与复杂网络(包括随机图与小世界网络)的拉普拉斯谱的最新的结果和研究进展.主要内容包括给定度序列的拉普拉斯谱半径、拉普拉斯系数、代数连通度、双随机矩阵和随机图与小世界网络的谱的性质.并且提出了可能进一步研究的一些相关的问题.

矩阵论中的图论匹配法

G.Birkhoff用代数的方法证明了如果一个矩阵是双随机矩阵,则它能表示成置换矩阵的凸线性组合.设G是具有两分类(X,Y)的二部图,则G中含有饱和X中的所有顶点的匹配M的充分必要条件为:对S■X,有dG(S)≥|S|.文章借助上述二部图的匹配思想,给出这一结论的图论证明.

关于紧图和超紧图的几个结果(英文)

给出了一些 新的紧图，并对 不是超紧的紧图

Swarte的引理5.4的证明及推广

D. Crystal, H. Greenberg, A. Kolem, W. Morris, A. Raian, R. Rardin和 M. Trick指出:从我们对Swart的文章的研究,确信变量公式是正确的,但Swart对关键性引理5.4的证明是错误的。在这里,我们给出引理5.4的一个严格证明,证明引理是完全正确的,并进一步推广引理5.4的结果。 Swart引理5.4;给定了一个n×n双随机矩阵D,它的所有元素是非负整数,并且每一行和与列和都是正整数K,则D能分解成置换矩阵的线性组合。推论:给定一个n×n双随机矩阵D,它的所有元素是非负整数,并且每一行和与列和都正实数K,则D能分解成置换矩阵的线性组合。

图优化的低秩双随机分解聚类

低秩双随机矩阵分解聚类(low-rank doubly stochastic matrix decomposition for cluster analysis,DCD)通过最小化KL(Kullback-Leibler)散度准则:KL(A,S),从图关联矩阵S中获得一个非负低秩双随机矩阵分解:A=UUT(U≥0),并以U作为类标签矩阵进行聚类。在DCD方法中,因矩阵S是固定不可变的,故S初始取值选取的好坏对聚类结果有极大影响,这导致了它缺乏稳定性。针对这一问题,提出了一种基于图优化的DCD方法,将图关联矩阵S和DCD的优化集成在统一框架中,这改进和拓展了原始的DCD方法。实验结果表明,与DCD方法相比,图优化的DCD方法具有更好的聚类精确度和稳定性。