复杂网络上的路由策略及结构性质对其的影响

• 作 者: 许睿捷
• 机 构: 中国科学技术大学
• 出 处: 中国科学技术大学
• 发表日期: 2015年期
• 关键词: 复杂网络 双随机路由 局域信息 数据包传递

当前环境下，复杂性科学是一个研究的重点。基于理想条件或是单个粒子的理论已经无法满足现代科学技术的研究和应用。所以，复杂网络的研究是一个重要的方向。复杂网络是一种具有极大规模节点数和边数的图，是现实中复杂系统的异质性的一种抽象描述。复杂网络的研究，就是研究网络的各种性质，如度分布、聚类系数、介数等对网络上的动力学，如传播，路由，扩散等的影响。　　本文选择对网络上的传输过程以及路由策略进行研究。研究网络上的数据包传递的路由策略与网络结构性质的关系。本文首先给网络上的数据包传递建立了一个数学模型并进行解析，得到了描述传输过程的参数，如节点的平均队列长度L，包的平均传输时间T，以及传输能力Rc的关系。我们证明了网络传输能力的上界被Rc＜C＜k＞，其中C是每个节点每时间步处理的包数，＜k＞是平均度。我们的结果同样可以用最短路径路由的介数来描述。　　接下来，我们提出了一种双随机路由策略，这个策略只需要局域信息以及一些简单通信就可以实现。通过模拟，我们发现相比较一般的局域信息静态路由，双随机路由可以提升传输能力Rc，但是并不是对所有网络都成立。　　最后，我们就双随机路由策略的数学本质，构造双随机矩阵的迭代过程展开讨论。从网络中图形结构的角度，我们发现当图形h个互不相连的节点只和另外g个节点相连(h＞g)不存在时，这个迭代过程收敛。当这种图形存在时，迭代不收敛。这种图形的存在性和两个因素有关，1.网络度分布的高阶矩的收敛性。2.网络中度为1的节点存在概率。模拟结果支持这个理论，并且，我们从理论上证明了，对BA网络当平均度为8时有一个相变。