全齐性网络

 

 

 

寻找使得动力学网络同步能力最强的网络，人们称为同步最优网络或者缠绕网络，就是一个有意义的课题，这就是我们为什么要研究全齐性网络。我们的研究证实同步最优网络是度数相同、路和相同并且最小、周长相同并且最大的几乎全齐性网络

 

 

第二类网络是全齐性网络。我们为什么会研究全齐性网络？网络科学能够超越数学中的图论，最为重要的是与动力学相结合，即流行的互联网+思想。

 

网络科学的第一波浪潮，互联网+大数据，是由外国学者掀起的。他们利用互联网获取了许多现实网络的数据，提出了与传统随机图论不同的网络模型。通过实证统计或模型分析，发现了大多数网络具有小世界或无标度特性。小世界特性由网络平均路径和群集系数刻画，而无标度特性由网络度分布描述。

 

网络科学的第二波浪潮，互联网+动力学，则是由中国学者发动的。主要思想是对每个节点加上动力学，研究网络拓扑和动力学之间的相互影响。开创性的工作由汪小帆和陈关荣，首先研究复杂网络同步问题开始，随后带出了多智能体的一致性研究和复杂网络可控性研究等等。

 

假定网络中的每个节点的行为用一个非线性动力学方程来描述，节点之间的动力学关联通过网络拓扑来耦合，假设耦合为常数，问什么条件下网络节点动力学的行为能够达到完全同步？这是一个很难的数学问题。考虑最简单的无向联通网络，这时网络的拉普拉斯矩阵的特征值，除了零以外，其余都是正实数。他们研究发现可用网络结构和节点动力学的有关常数来刻画同步区域。他们首先得到对于无界区域情况，无向连通网络完全同步的条件是网络拉普拉斯矩阵的谱隙。即最小非零特征值，越大越容易同步。而对于有界区域情况，外国人得到无向联通网络完全同步条件是网络拉布拉斯矩阵的特征比。即最小非零特征值和最大特征值之比，越大越容易同步。

 

一个实际应用当中感兴趣的问题是，给定了网络的规模（节点数和连线数）以及节点动力学，具有何种特性的网络结构同步能力最强？如，是不是小世界网络或是无标度网络呢？后来发现不一定，因此寻找使得动力学网络同步能力最强的网络，人们称为同步最优网络或者缠绕网络，就是一个有意义的课题，这就是我们为什么要研究全齐性网络。

 

缠绕网络没有告知同步最优网络到底是什么样子。因网络的特征比最大，可以证明其谱隙也最大，所以问题转换为如何安排网络的邻接矩阵里面的1的位置。也就是重新改变网络的节点之间的连线，设计一个新的网络，使得网络的拉普拉斯矩阵的特征比最大，但这是一个有NP难度的最优化问题。

 

我们的研究证实同步最优网络是度数相同、路和相同并且最小、周长相同并且最大的几乎全齐性网络。在这里，路和定义为网络中其余节点到该节点最短路径通过的连线数目之和，周长定义为从该点出发，再返回它的最短环路所含连线数目。不过，度数相同就限制了对某些网络是无能为力的。例如，5个节点不能度都为3。同样有些网络即使度数相同，也不一定能保证各个节点的周长和路和都相同！这就是前面要加上几乎二字的原因，但为了叙述简便，常常省掉它。

 

构造同步最优的全齐性网络不是一件非常容易的事情，涉及到代数图论和数论。我们2013年在IEEE上发表的长篇论文给出了某些例子。

 

无标度网络是周知的异质性网络，全齐性网络是典型的同质性网络。探索这两个极端网络类的结构对功能的影响具有重要意义。无标度网络是基于树结构，hub节点拥有大量的连线。全齐性网络关注着圈结构，周长最大的同步能力最强！于是在此基础上，我们引入了一类新的节点重要性指标。

 

关于网络节点重要性排序有许多重要的工作。例如，网页排序中最著名的Page Rank算法就是通过计算一个网络马氏链的平稳分布来实现的；而Leader Rank算法通过巧妙地构造了另外一个网络马氏链来实现。马志明院士提出的Browse Rank算法是利用用户浏览网页的大数据，通过得到Q矩阵来实现的。

 

基于树结构的节点重要性排序指标有度数、H指数、核数。吕琳媛等人，发现它们之间存在着美妙的数学关系，即度数通过逐次计算H指数，最终会收敛到核数。类似的，我们基于圈结构提出了新的节点重要性指标，圈数、圈和、圈比。圈数是节点处于可供周长候选的最短环路中的个数；圈和是节点处于候选周长中的边数总和；圈比是过该节点的周长个数占所有可能周长数的比。

 

对于多个实际网络的模拟评价显示，圈比指标在网络攻击上效果很好，圈数指标在信息传播上性能更佳。它们大多优于树结构的三个指标。

 

通过网络圈结构的研究，我们期望能够突破网络中树结构的一统天下！