基于复杂网络结构异质性的信息传输路由函数优化设计及稳定性研究

Routing strategy plays a crucial role on information transferring efficiency. Current researches focus on routing strategies on the scale-free networks and small world networks. Few consider the other kinds of network. In fact, the heterogeneity of network structure has great impact on the routing strategy. Our previous findings suggest that an effective routing strategy is closely related to the statistical characteristics of the network. Thus, this project introduces routing function concept that is associated with network structure and then explores the routing path by minimizing the proposed routing function. On condition of the previous outcomes, a new set of routing criterion and several novel approaches are developed in this project. In more detail, first of all, degree distribution and degree correlation coefficient are used to describe the heterogeneity of network structure and restructured-based Markov chain is explored to calculate the degree distribution. Secondly, characteristics of routing function are investigated through theoretical deduction as well as computer simulation in order to discover the relations between routing strategy and degree distribution and degree correlation coefficient. Based on the above results, routing function is optimized and its stability is studies. Finally, some new routing criteria are established in which taking network structure as parameter the robustness and fragility of routing function are examined by simulation experiment as well as empirical study. The purpose of this project is to explore the relationship between routing strategy and network structure, which is important to the routing strategy construction on other types of network, rather than only on scale-free and small world networks.

如何针对不同复杂网络结构来构建高效的路由策略是一个极具现实意义但还未引起关注的重要问题。我们前期研究发现：高效的路由策略与网络的度分布和度相关系数之间存在密切关系。由此本项目提出构建与网络结构有关的路由函数，将求解路由函数最小值所得到的路径作为路由路径的思想，以此建立一套新的路由准则理论和方法。我们首先用度分布和度相关系数作为网络结构异质性的度量，运用基于随机过程的Markov Chain 方法求解度分布和度相关系数；其次运用理论分析和仿真模拟方法对路由函数特点进行深入研究，建立路由函数与度分布之间的量化关系，对路由函数模型及参数进行优化设计，建立以网络结构为基础的新的路由准则。并以网络容量为目标，以网络结构为参变量对路由函数的稳定性和脆弱性等系列问题进行深入的理论、仿真模拟和实证研究。本项目对揭示路由策略与网络结构之间的关系具有重要意义，为异质性网络的路由策略制定奠定理论基础。

项目背景.如何提高不同网络规模和拓扑结构的复杂网络上的信息（包括物质和非物质）传输能力，这是一个在许多领域所共同关注的问题。我们前期的研究表明：对于无标度网络，概率路由策略是一种优于最短路径策略和效率路由策略等的路由策略。然而对于其他均匀和非均匀网络，概率路由策略是否还具有这种优势？如何设置概率路由函数，概率路由函数与网络的统计特征之间存在何种关系？以及概率路由策略的稳定性及在网络拓扑结构发生变化后概率路由策略的稳定性等，这些需要我们对概率路由函数进行全面深入的研究。.主要研究内容.1..演化网络的度分布研究；.2..概率路由规则研究；.3..网络路由策略的稳定性研究。.重要结果.1..给出了求解演化网络度分布的SPR方法，验证了该方法不仅适用于节点增长的演化网络，而且可以用于求解节点减少的演化网络，目前，该方法是求解演化网络度分布最有效的方法；.2..全面验证了概率路由策略的优势，提出了信息传输的最大概率准则，用以替代传统的最短路径准则；.3..从理论方面全面、深入、系统的研究了网络动力学行为的稳定性；.4..至2016年底，共发表与项目相关论文50余篇，其中SCI文章46篇，JCR二区以上文章26篇。.科学意义.本质上，复杂网络的路由策略问题是一个自变量为离散型的优化问题，然而该优化问题由于无法确定所有路劲从而无法求解。因而运用一个好的规则来制定路由路径是研究路由策略问题的最佳选择。本项目研究结果的重要科学意义在于：.1..给出了复杂网络上的路由规则的‘最大概率准则’，由该准则确定的网络容量在均匀网络中与传统的‘最短路径准则’相当，而在非均匀网络中，远高于‘最短路径准则’。为今后在计算机网络和交通网络等方面的应用研究提供了理论基础；.2..丰富了复杂网络的数理基础研究；SPR方法是求解演化网络度分布最有效的方法，为进一步研究演化网络的统计特性及收敛性等提供了很好的工具和方法；.3..对概率路由策略的稳定性进行了较全面深入的研究，为复杂网络动力系统稳定性的研究提供了新的研究方向。