面向复杂网络可控性的若干关键问题研究

发布时间：2018-06-04 09:39

本文选题：复杂系统 + 复杂网络　；参考：《太原理工大学》2017年博士论文

【摘要】：进入21世纪后,复杂系统为人类的生产与生活带来了极大的提升与便利。与此同时,复杂系统的失效也会造成灾难性的后果,如大范围的停电事故、交通运输的瘫痪以及谣言或疾病的快速传播等。因此,我们需要对复杂系统进行有效地控制,从而尽可能地利用它的价值避免灾难发生。尽管现实中的复杂系统千差万别,但是大部分复杂系统均可抽象为复杂网络模型,从而把复杂系统的控制问题转化为复杂网络的控制问题。在进行复杂网络控制前,首先要明确被控对象是否可以被有效控制,即是否具备可控性。若确认被控对象具备可控性,再进行后续控制动作,否则需要重新调整被控对象,直至使之具备可控性。因此,判定复杂网络的可控性是开展控制的第一步。在前人工作的基础上,本文讨论了复杂网络可控性的若干关键问题,主要贡献如下:1.当复杂网络的整个拓扑结构未知时,我们往往采用局部控制的手段,重点控制那些相对其他节点在某些方面起着重要作用的关键节点。那么,控制关键节点的前提是要确定是哪些节点。因此,本文从不同的角度选取具有代表性几个指标,借鉴运筹学的多属性决策方法进行融合,提出了一个度量复杂网络中关键节点的综合指标。实验比较验证了本文所提方法的准确性与有效性,说明了该综合指标能更好地挖掘出一个网络的关键节点,为控制网络提供策略上的指导和帮助。2.当我们需要对一个复杂网络进行精准、完全控制时,首先要找到网络的最大匹配,并对非匹配节点进行控制实现对网络的精准控制。因此,如何挖掘复杂网络的最大匹配是一个必须解决的问题。本文研究了复杂网络最大匹配的挖掘方法,提出了利用矩阵初等变换识别网络中最大匹配的匹配节点,发现最大匹配中匹配节点的个数由网络矩阵特征值的最大几何重数决定。通过在真实网络数据以及随机网络数据上的统计分析,发现网络中最大匹配的匹配节点与节点的度分布密切相关。此外,本文也提出了挖掘最大匹配的一种启发式算法,保证所找到的最大匹配是最优的。大量真实网络和模型网络的计算结果表明了该方法的有效性与可行性。3.当复杂网络尺度较大时,用求解最大匹配算法来控制网络是很困难的。因此,本文从粒计算的角度入手模拟人类求解复杂问题的思维,提出了一种网络粗粒化的方法,将大规模网络降维为规模较小的网络,再求解其最大匹配。最后,通过实验数据分析了应用粗粒化算法的适应场景与优势,发现:当网络中含有大量的有向圈或有向路径时,网络粗粒化后它的驱动节点数会有所下降,而对于所含这两种结构相对较少的网络来说,粗粒化对其影响较小。本文提出的关于复杂网络可控性理论和研究方法具有一般性,研究结果有望为各种复杂系统的控制提供一定的借鉴价值,同时有助于我们更好地理解网络结构与其可控性之间的关系,为复杂系统的设计提供新的思路和理论依据。
[Abstract]:After twenty-first Century, complex systems have brought great improvements and conveniences to human production and life. At the same time, the failure of complex systems can also cause catastrophic consequences, such as a large scale of blackouts, traffic paralysis, and the rapid spread of rumors or diseases. Therefore, we need to effectively control complex systems. It can make use of its value as far as possible to avoid disaster. Although the complex systems in reality are different, most complex systems can be abstracted as complex network models, and the control problem of complex systems is transformed into a complex network control problem. Before the complex network control is carried out, the object is to be clearly defined. It can be effectively controlled, that is, whether it has controllability. If the controlled object is controllable, then follow the control action, otherwise the controlled object needs to be adjusted to make it controllable. Therefore, it is the first step to determine the controllability of the complex network. The main contributions of the network controllability are as follows: 1. when the whole topology of the complex network is unknown, we often use the local control method to control the key nodes which play an important role in some aspects. Then, the premise of controlling the key nodes is to determine which nodes are. In this paper, several representative indexes are selected from different angles, and the multi attribute decision-making method of operational research is used for reference. A comprehensive index of key nodes in a complex network is proposed. The experimental comparison shows the accuracy and effectiveness of the proposed method, which shows that the comprehensive index can better mine a network. Key nodes provide guidance and help to control network strategy and help.2. when we need accurate and complete control of a complex network, we must first find the maximum matching of the network and control the non matching nodes to realize the precise control of the network. In this paper, we study the mining method of the maximum matching of complex network, and propose a matching node identifying the maximum matching in the network by using matrix elementary transformation. It is found that the number of the matching nodes in the maximum match is determined by the maximum number of geometric weights of the eigenvalues of the network matrix. It is found that the maximum matching node in the network is closely related to the degree distribution of the nodes. In addition, a heuristic algorithm for mining maximum matching is proposed in this paper to ensure that the maximum matching is optimal. The results of a large number of real networks and model networks show that the effectiveness and feasibility of the method.3. is a complex network. When the scale is large, it is difficult to use the maximum matching algorithm to control the network. Therefore, this paper, starting with the point of grain computing, simulates the thinking of solving complex problems by human, and proposes a method of network coarse-graining, which reduces the dimension of large-scale network to a smaller network and then solves its maximum matching. Finally, the experimental data is analyzed. Using the adaptation scenarios and advantages of coarse graining algorithm, it is found that when the network contains a large number of directed loops or directed paths, the number of its driving nodes will decrease after the network coarse-grained, and coarse graining has little influence on the two networks with relatively few structures. The theory and research methods are general. The results of the study are expected to provide a certain reference value for the control of various complex systems, and help us to better understand the relationship between the network structure and its controllability, and provide new ideas and theoretical basis for the design of complex systems.
【学位授予单位】：太原理工大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：O157.5

【参考文献】