【作者】 党妮；

【导师】 吴建设；

【作者基本信息】 西安电子科技大学 ， 电路与系统， 2018， 硕士

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

【Abstract】 There are a variety of networks with different properties and distinctive function,such as personal relationships networks,power networks,gene regulatory networks and so on,in the real world,all of which can be abstracted as complex networks.Recent years witness a rapid development in the field of complex networks.As an interdisciplinary academic field,the complex network study has attracted intense interest from the field of Statistical Physics,Computer Technology,Ecology,Graph Theory and Economics and so on.The relation between the topology of the networks and the dynamics of the networks is a most significant research topic in the field of complex networks.The dynamics of the vertex in the networks is,usually,the priori information,while the topology of the networks is hard to be detected.Reconstructing networks,which is further digging out valuable information and inferring the topology of the networks from this information,is an inverse problem in the field of dynamics.The dynamical process of the phases of nodes in a network is one of dynamics behaviors.In this thesis,the algorithm of estimating the topology of a network from the phase information of nodes is studied.The main contribution of this thesis is organized as follows: 1.The algorithm of matching positions by phase information.There is a special matching phenomenon between the phase of a vertex and the phase of its neighbors in a network.Based on the matching,we infer the topology of the nodes whose degree is known or unknown.If the degree of the nodes is large,and the number of nodes in the network is pretty large,there will probably be computational burden or even run out of memory when utilizing the algorithm of matching positions by phase information to reconstruct a whole network.We analyze the problem of the computational burden and propose a method to solve this dilemma in terms of the mathematics.2.Reconstructing networks from matching positions by phase information.We propose the stepwise reconstruction strategy,which enable the algorithm of matching positions by phase information to be utilized to infer the topology of a whole network,to ease the computational burden.In the strategy,only the nodes whose degree is the minimum in the current network is reconstructed in every step,and the nodes whose topology have been known and all the edges connected to them will be removed from the current network,then we continue to infer the topology of the nodes whose degree is minimum in the new current network,and then update the current network by removing nodes and edges,repeating the cycle until there is no node in the current network.We propose two matching algorithm: Matching Positions with Single Vertex and Matching Positions with Multiple Vertex.The latter can infer the topology of more nodes than the former in every circle.The algorithm of Matching Positions with Multiple Vertex has been tested in BA Scale-free networks,ER random networks,LRR Benchmark networks and a gene regulatory network.The results show that the algorithm can be used to infer the topology of undirected networks and directed networks,and almost all these networks can be reconstructed accurately even when there are more than 10000 nodes in the networks.Moreover,the data of phase we need are pretty few and the algorithm performs much better when reconstructing BA Scale-free network.3.Fuzzy Matching Positions method.Estimating the topology of a network from short time series data is a challenging problem,while we have solved this problem by the algorithms mentioned above.In these algorithms,we assume that the phase information we get is pure,without any noise,but in reality,it is almost impossible to acquire pure information.To make these algorithms suitable for this case,a new method called Fuzzy Matching Positions method to reconstruct network is proposed in this thesis.The Fuzzy Matching Positions method can be used to infer the topology of networks regardless the purity of the priori phase information.更多还原