论文部分内容阅读
复杂网络的广泛研究源于其在建模真实数据结构时表现出的灵活性和普适性。一个复杂网络可以展示出刻画系统中个体的连接关系以及影响系统动态功能行使的结构特性。关于复杂网络结构特性度量方面的研究工作涉及到:将一个目标系统表示成网络结构;通过一系列富含系统结构信息的度量指标,分析网络拓扑结构属性;量化演化网络的结构属性值的变化,说明系统动态演化过程中网络的连接关系是如何变化的;使用拓扑结构度量指标来挖掘不同结构类型的子图模式;以及比较人们提出的模型网络和真实网络中特定度量值,来验证模型的正确性。可以看出,复杂网络的表示、分析、比较和建模都十分依赖于对网络拓扑结构的属性进行定量地刻画。近来,复杂网络的拓扑结构与动态结构可控性的关系成为了研究的热点。然而,与此动态控制过程关联的、重要的结构度量指标还没有受到研究者的广泛关注。事实上,只有通过获取对拓扑结构属性有意义的定量描述,才能刻画、分析并进一步揭示结构与动态控制过程之间的关系。因此,针对有向网络数据,提出结构属性量化指标来刻画动态控制过程、检测控制相关的子图模式,研究基于拓扑结构度量指标的复杂网络分析算法,应用于诸如全局网络比对这样的实际问题中,就成为了本文的主要研究内容。具体而言,本文开展了以下研究工作并做出了相应的贡献:1.拓扑结构中心性是复杂网络分析的核心内容之一。特别地,在考虑节点之间的方向性特异的连接与系统的动态控制功能行使的关系时,衡量一个节点从结构控制的角度来干预网络的能力大小就是非常具有实际应用价值的。本文基于能控子空间和能观子空间,在保持网络整体控制的输入代价最小的前提下,分别给出了节点的控制范围中心性以及支配能力中心性度量指标。它们的定义与边的方向性紧密相关,量化了通过一个节点能够控制干预有向网络的程度和范围。通过在真实网络数据以及随机网络数据上的统计分析,发现网络中节点的控制范围以及支配能力的分布是由节点的度分布来决定的。同时,度大的节点也并不一定就是干预网络动态过程时应该优先选择的驱动节点,这为干预网络提供了策略上的指导和帮助。2.虽然已经有大量的针对无向网络数据的模块检测技术,但是由于缺乏能被广泛认可的有向网络中节点的相似性度量指标,目前有向网络数据的聚类分析仍十分具有挑战性。从节点在控制、支配有向网络的能力出发,定义控制范围相似性以及支配能力相似性度量指标,来分析有向网络里节点在动态控制功能行使时行为的相似程度。由于这两个指标都具有与方向性紧密相关,同时又在计算上与网络中的边权重无关的特性,使得它们在精确刻画含有噪声的、稀疏、有向网络数据的结构特性时非常有效。在真实数据上的实验中,利用该指标在术语网络以及代谢网络中都检测出了具有显著功能特征的子图结构。3.在面对蓄意攻击时,无向网络的结构鲁棒性可以通过结构优化得到显著地提升。但是对于有向网络数据,人们还不知道在节点失效时应该如何保护网络的结构。动态控制功能是有向网络中与边的方向紧密相关的系统关键功能之一。因此,如何在蓄意攻击下提高网络控制功能的鲁棒性,对于优化有向网络的拓扑结构就具有重要意义。基于复杂网络的全局连通性以及可控性的研究,本文提出了一个控制鲁棒性结构度量指标。更进一步,通过分析拓扑结构属性与动态控制过程的关系,将优化网络的控制鲁棒性问题转化为提高控制路径的传递性问题。从而,给出了一个高效的复杂网络拓扑结构优化算法,能有效地保护复杂系统中的控制路径,减缓蓄意攻击对其的破坏速度。在真实数据和人工合成数据上的仿真实验表明,复杂网络的全局连通性和可控性可以通过少量的结构扰动同时得到提升,所给出的控制鲁棒性指标以及网络结构优化算法,在增强有向网络的控制鲁棒性方面都是非常有效的。4.网络比对是生物网络比较分析中的一项重要技术。比对不同物种的蛋白质网络,发现保守的相互作用关系,对于识别进化上的保守路径和蛋白质复合体具有重要意义。基于拓扑结构中心性度量指标,针对全局网络比对问题,采用网络中拓扑结构上的中心节点构建种子节点对,给出了一种新颖的比对初始种子选择策略。分别从每个种子节点对开始,用成员相似性指标来度量邻居节点与当前种子组成功能模块的可能性,这样以模块为单位来展开比对过程,保证了功能模块的完整性尽量不被启发式的搜索过程所破坏,有效地解决了大多传统全局网络比对算法存在的,初始种子选择在很大程度上影响比对结果的问题。该方法采用蛋白质的序列相似性、拓扑结构中心相似性、成员相似性指标来构建蛋白质之间的相似性度量,是一个基于多中心种子的全局网络比对算法。