基于相位匹配的复杂网络拓扑重构研究

摘要

现实世界中存在着各种各样的网络，这些网络性质不同、功能各异，但是都可以抽象成复杂网络。复杂网络作为一个交叉学科，近年吸引了来自统计物理学、生态学、计算机网络及经济学等多个领域的科学家的目光。研究网络的拓扑结构和网络的动力学行为之间的相互关系是复杂网络研究中的一个重要问题。一般情况下，网络各单元的动力学信息可以直接观测到，但单元间的耦合关系，即网络的拓扑结构却不容易直接观测到。网络重构是网络动力学的一个逆问题，主要研究利用网络的动力学行为推测网络的拓扑结构。网络中节点的相位信息的动态演化过程是网络动力学行为的一种，本文主要研究从观察到的网络相位动力学信息出发，挖掘有价值的信息，并最终推测出网络的拓扑结构。所取得的主要成果为： 1.相位匹配算法。我们从网络的相位动力学公式中发现了节点的邻居节点与节点相位值之间存在特殊的匹配关系，并利用该匹配关系重构出网络中度已知和度未知的节点，本文将该方法称为相位匹配算法。利用相位匹配算法重构节点的拓扑结构时仅需要在连续两个时刻点采集相位信息，即仅需要一步迭代相位数据，用如此少量的数据进行拓扑重构是现有的网络重构研究中一个非常具有挑战性的问题。本文提出的相位匹配算法应用了组合数思想，当网络中节点规模比较大、待重构节点的度比较大或两者同时比较大时，推测节点的拓扑结构时的计算量会特别大，甚至可能因此出现内存溢出问题。我们从数学角度分析出了内存溢出问题的原因为组合数激增，并对如何避免组合数激增问题进行了数学分析。 2．相位匹配网络重构算法。本文提出了逐步循环重构思想来避免组合数激增问题，使相位匹配算法可以用来重构整个网络的拓扑结构，具体方法是每次重构时仅重构网络中度最小的节点，每完成一次重构就将已重构的节点和连边从待重建网络中删除。相位匹配网络重构算法分单节点相位匹配网络重构算法和多节点相位匹配网络重构算法两种。每轮重构中，单节点相位匹配网络重构算法仅重构出当前待重构网络中度等于最小度的一个节点，多节点相位匹配网络重构算法则可以重构出当前待重建网络中度等于最小度的所有节点。我们分别在BA无标度网络、ER随机网络、LFR benchmark网络和基因调控网络上对该算法的性能进行了测试，结果表明我们提出的相位匹配算法既可以重构无向网络，也可以重构有向网络，在重构无向网络时效果更好；且该网络重构算法重构正确率较高，甚至可以完全无误地重构出节点数大于10000的网络；用该网络重构算法重构BA无标度网络时在正确率和运行时间方面性能明显优于重构其它网络时的性能。 3．相位模糊匹配网络重构算法。本文提出的相位匹配网络重构算法对含噪相位信号具有较高的敏感性，其使用的前提是假设采集到的相位信息是不含任何噪声的信号。然而事实上，测量的方式、工具、环境及测量者本身的分辨能力等因素都会对采集到的相位信号的质量有影响，致使我们几乎不能采集到不含噪声的信号，这就限制了其在现实世界应用。为了提高相位匹配算法的鲁棒性，使其在采集到的相位信息含噪声的情况下也同样适用，本文提出了相位模糊匹配重构算法。与相位匹配网络重构算法相比，相位模糊匹配网络重构算法虽然在重构正确率上稍微差点，但是更适用于现实环境。

目录

第一个书签之前