复杂网络中的动态过程问题研究

摘要

近年来兴起的复杂网络为研究复杂系统提供了一种新的视角。它关注系统中个体相互作用的拓扑结构，是理解复杂系统性质和功能的基础。复杂网络要研究的是各种看上去互不相干但其实密切关联的形形色色网络之间的共同属性和处理它们的普适性方法。自从1998年Watts和Strogatz提出的小世界网络模型、1999年Barabási和Albert提出的无标度网络模型后，复杂网络研究进入高速发展时期，它甚至被称为“网络的新科学”。目前，它已经与数学、物理科学、计算机与信息科学、生物科学、系统科学、社会科学等众多学科广泛交叉，引起了国内外不同学科的研究人员对网络科学的高度重视和普遍参与，对复杂网络的定性与定量特征的认识和理解已成为网络时代科学研究中一个共同而又极其重要的挑战性课题。复杂网络的研究成果对探索其他学科具有前瞻性、启发性、指导性、应用性和推动作用，将有着广阔的应用前景。复杂网络的主要研究内容包括发现网络结构的统计性质并建立合适的模型以揭示网络演化的原因，分析和研究网络上的动态过程以帮助人们改善已有网络的性能和提出设计高效网络的方法。
　　 本文主要对复杂网络动态过程中的几个关键问题进行了研究，主要内容和结论可以归纳如下：首先，级联失效在网络尤其是Internet和电力网上的产生会造成严重的影响，设计合理的负载容量模型以防御级联失效来获得较高的网络鲁棒性能和较低的成本则成为研究的关键。本文提出了一种更符合实际网络的负载容量非线性模型。通过在无标度网络、随机图网络、Internet AS级网络和美国西部电力网络上进行仿真，验证了该模型的可行性，并且发现该模型中的两个参数在一定条件下具有负指数关系。本文进一步考察了网络成本和鲁棒性关系，与ML模型进行对比发现该模型能够更好的抵御级联失效，并且在获得较高鲁棒性能的情况下有较小的投资成本。其次，本质上拥塞是由于网络当中的负载超出了网络资源的存储和处理能力造成的。对于控制拥塞和提高网络传输效率而言，目前的研究主要集中在修改基础网络结构和开发路由策略两方面，而后者则更为人们所关注。本文建立了具有不同处理能力和容量的节点模型，提出了一种具有流量意识的路由策略。
　　 本文讨论了网络拥塞的产生与节点模型的关系，认为不同的节点处理能力决定了相变临界值的大小；研究了路由策略中的控制参数对拥塞相变点的影响，得到了与理论估计相一致的结果；对比不同的路由策略在本文框架下的有效性，验证了本文方法能够更好的提高网络传输的效率。第三，影响扩散是复杂网络中动态过程研究的关键问题之一，而且基于动态网络的影响扩散问题的相关成果很少。本文讨论了动态独立级联模型和动态线性阈值模型以及基于这两个模型的动态影响最大化问题，提出了一种改进的贪婪算法，该算法消除了随机模型的不确定性并采用连通图方法来提高算法性能，并在不同规模的四个数据集AS、EMAIL、DELICIOUS和DBLP上进行了验证。实验结果表明，与HT算法相比本章所提出的算法在影响扩散范围方面有着明显的优势，且在时间效率方面要好于HT算法。最后，本文利用复杂网络理论研究网络结构演化问题。首先采取角色连接轮廓方法从结构上对网络进行划分，发现社会网络属于外围串类型；其次，验证了网络的无标度分布、直径缩减和稠化性质，发现网络中社区大小服从幂律分布，规模中等的社区主要呈现星型结构；发现网络中存在紧密连接且直径较小的核心结构；最后，基于事件框架研究了网络中社区结构的演化，发现社区间的融合很大程度上取决于社区间直接连接的节点所构成网络的聚簇系数，而社区的分裂则与该社区的聚簇系数相关。