论文部分内容阅读
现代对于社会网络及其关联的小世界模型的研究很多都是在模拟和数值试验中完成,其中两个重要的拓扑性质就是小世界性和强聚集性,一般指的就是平均距离或者直径远小于顶点数量而图中三角形的数量又接近于正则格。Watts和Strogatz提出了将正则格的一部分边随机以概率p移走到其他顶点的模型(WS模型)并通过数值模拟发现存在一个概率区间使得移边概率p在该区间内具有强聚集性和小世界性。Watts和Strogatz猜测存在一簇介于有序和无序(随机)的图使其聚集性能很强而平均距离或者直径接近于随机图,并称之为小世界网络。同时期Newman和Watts提出了用正则格和随机图的并去掉自环和重边后构成的模型(NW模型),这个模型的聚集系数相当容易估计。Newman、Moore和Watts利用连续型模型近似和中值场近似(以及独立的Barbour和Reinert利用连续模型)给出了平均距离的估计。我们提出了广义小世界模型并利用等周常数结合最大度得到该模型直径的上界,再利用组合计数估计三角形数量得到聚集系数的下界。从而证明了广义小世界模型为一簇满足强聚集性和小世界性的小世界网络。
社会网络及小世界模型上的代数性质是指的将图看作一个矩阵并通过研究矩阵的谱来研究网络的性质。这里网络的代数结构,尤其是Lapla-cian矩阵的第二小特征值(也称代数连通度)和最大特征值和网络上的动力系统有很强的关联,特别在多智能体系统的一致性问题和耦合系统的同步问题中有广泛的应用。Olfati-Saber利用计算机模拟发现WS模型的代数连通度与正则格比较有很大的提高,这个性质对于提高多智能体系统达成一致性的速度非常重要。我们给出了NW模型代数连通度的严格估计以及与正则格比较的代数连通度获取量的下界。代数连通度决定了小世界网络上多智能体系统达成一致性的速度,因此我们的结果可以用于设计成本低廉连接较少而一致性很快的多智能体系统。此外我们还分析了小世界网络上多智能体系统对时滞的鲁棒性能以及给出了一簇可同步的小世界网络。
社团性质指的是局部连接紧密而与外界连接稀疏的拓扑性质,它是社会网络的局部拓扑性质中很重要的一部分。对于社团性质的研究着重于找到现实网络中的这些社团,也就是社团划分,目前给定网络有许多社团划分的算法,但是仍然缺少一个通用有效并且确定划分数量的快速算法。在本篇论文中,我们提出了利用一个或者多个Laplacian矩阵特征向量的分量投影到一维或者多维欧式空间后,使用原点或者坐标轴进行切割,再考虑每个子块的连通分支的快速算法,在文章中称为弱Nodal域划分方法(WNDP),我们还提出了三个对不同特征向量划分后比较的标准从而决定网络具体划分块数。