概率意义下图模型的某些全系不变量的研究

Graph models provide an appropriate way of describing complex systems and have been investigated widely. Three models of those networks, E-R random graphs model, W-S small-world model and B-A scale-free model, have attracted more attention, since they significantly represent some of fundamental characters of the "complexity" from different perspectives. The majority of those researches on that issue, however, only focus on one invariant for a model, and only a few of invariants were considered so far about the relationships among them for a given model. Our project intends, however, to investigate, from a global point of view, invariants for a given model, and we try to find out a crucial invariant, called a complete invariant of a model, which can determine a graph in the model from the probabilistic perspective and thus can be used to characterize the typical properties of other invariants. We shall try to prove the adjacency spectrum or the Laplacian spectrum are two complete invariants of the E-R random graphs model, and then we shall try to establish complete invariants for the rest of two models above. Furthermore, we shall employ these invariants to characterize the typical properties of graphs in those models and other invariants, which are some of fundamental problems in the theory of random graphs.

图模型作为描述复杂系统的工具, 已经得到了广泛而系统的研究. 而E-R随机图模型, W-S小世界模型和B-A无标度模型更是受到了大家的格外关注, 这是因为它们分别从不同角度展现了"复杂"的基本特征. 不过, 大多数工作只限于孤立地研究一个不变量在模型中的典型特征. 而对于模型上不变量间关系的现有研究, 还只是对为数很少的几个不变量做数值或理论分析. 本项目旨在从整体角度, 研究图模型上的不变量, 力图找出高概率意义下, 模型最重要的不变量, 即模型的全系不变量. 这种不变量能够在高概率的意义下, 决定模型中图的结构, 因而也就决定了其他不变量在模型中的典型特征.本项目将尝试证明图的邻接谱或Laplace谱是E-R随机图模型的全系不变量, 并对后两个图模型, 尝试建立相应的全系不变量. 进而运用这些不变量, 刻画模型中图结构和其他不变量的典型特征. 而这些都是随机图论研究的基本内容.

大家知道，所谓两图同构是说两图顶点集之间存在着恰好保持所有邻接关系的双射。而图不变量是指图集合上的一个映射，其满足条件：只要两个图同构，则这两个图在该映射下的像相同。我们起初试图在概率意义下解决图同构问题。确切地说，是要找出一个能够快速求解的图不变量，并证明其在概率意义下是图的全系不变量，即对几乎所有的图，该不变量能区分互不同构的图。然而通过实际计算，我们发现置换群的几何表示可以有效地确定该群作用的轨道。借助这一工具，我们设计出了确定性的算法，它可以判别任意给定的两个有限图是否同构，并且其在最坏情形下的复杂性是n^[C*(log n)]，此处n代表图的顶点数，C是某个大常数。这是目前已知的处理图同构问题的最快算法。而且当图n不算太大时，log n并不大。所以我们的算法已经可以满足大部分的实际需求了。此外，我们还对若干重要的复杂网络模型进行了研究，分析了若干图不变量对于刻画网络各种性质的作用。