有利于导航的最优与次优网络

章忠志，盛益彬，胡正一，陈关荣

摘要：对于一个网络上的随机游走，从某一节点i到另一根据马尔科夫过程的稳定分布选取的节点j的平均首达时间的期望叫作该网络的Kemeny常数。由于Kemeny常数跟网络的导航效率息息相关，因此，构造一个导航效率最优或次优的网络是一个有趣的科学问题。现有结果表明，在所有网络中，完全图的导航效率是最高的。本文采用另一种方法证明了完全图具有最小的Kemeny常数，并说明了当网络很大时，完全图Kemeny常数的高阶项以网络规模的线性形式增长。众所周知，现实网络大多数是稀疏的，且许多网络同时具有无标度与分形的性质，这两个性质均不能用完全图来描述。本文接着研究了一类稀疏的无标度分形网络的Kemeny常数，利用重正化群的方法导出了该类网络概率转移矩阵的所有特征值及其重数的精确结果，在此基础上求得了Kemeny常数的精确解，并发现对于这类网络的特殊情形，其Kemeny常数与网络规模亦呈线性关系。因此，相对于完全图上的导航而言，这类网络可称为次优的导航网络。最后，为了说明所得特征值及Kemeny常数的可靠性，文章还利用求得的谱计算了网络生成树的数目，得到了与之前研究完全相符的结果。研究结果表明，所研究网络的结构有利于网络上的有效导航，这对现实世界中设计高导航效率的网络具有参考价值。

相关结果已在Chaos上正式发表。

文章发表的PDF版本：

Optimal and suboptimal networks for efficient navigation measured by mean-first .pdf