复杂网络能控性研究

发布时间：2019-02-09 15:35

【摘要】：复杂网络能控性问题是复杂网络研究的一个核心问题。在过去的十年中复杂网络能控性研究蓬勃发展并且涌现了大批出色的成果。但是却很少有人关注任意拓扑结构的有向网络能控的最小被控点集合和最优输入配置问题。针对复杂网络结构能控中的最小被控点集合和最优输入配置、复杂网络精确能控中的最小驱动点集合和被控点集合、复杂网络结构能控性恢复等问题做了相关研究。主要研究内容如下:针对最少的驱动节点被不同的输入控制不一定能保证网络能控这一问题研究了网络能控的最小被控点集合和最优输入配置问题。首先,证明了最少驱动节点被不同的输入控制能否保证网络的能控性与网络是否包含具有完美匹配的不可达强连通分量有关。其次结合网络结构能控的输入可达和完美匹配条件,指出了求解网络能控的最小被控点集合和最优输入配置的关键是找到具有最大交集的最小不被匹配节点集合和最小不可达状态节点集合。考虑到复杂网络一般具有大规模的特性,给出了带有约束的组合优化算法和基于最大权完美匹配的多项式算法来求解具有最大交集的最小不被匹配节点集合和最小不可达状态节点集合。在一些模型和实证网络上的仿真结果表明网络的结构能控性与网络是否含有具有完美匹配的不可达强连通分量有关,这一结果有助于更好地理解网络能控性与网络拓扑结构之间的关系。针对复杂网络结构能控的研究框架不适用于有向加权或者无向网络的能控性这一问题,在Yuan等人的复杂网络精确能控的基础之上,研究了复杂网络精确能控中的最小驱动点集合和被控点集合问题。首先,通过实例说明了不同的最小驱动点集合对网络的控制力是不同的并引入了节点控制力的概念来衡量节点在网络能控中的作用。其次根据节点的控制力,给出了求解最小驱动点集合的算法。在一些模型和实证网络上的实验结果表明利用该算法求解的最小驱动点集合在很多模型和实际网络中可以保证网络的精确能控性。最后针对最小驱动点集合在某些网络中不能保证网络能控的情况和求解网络精确能控的最小被控点集合问题已被证明是NP-hard的现状,给出了一种求解被控点集合的启发式算法。针对一个完全能控的网络,恶意的攻击或者随机的节点、连边失效都可能破坏网络的能控性,引入能控缺乏度的概念衡量网络能控缺乏的程度。对于能控缺乏度大于零的网络围绕最小输入和最少需控制的节点提出了一种网络修复算法。在真实网络和ER随机网络、BA无标度网络上的仿真结果表明修复复杂网络的代价与网络拓扑结构之间有密切的关系。
[Abstract]:The controllability of complex networks is a core problem in the study of complex networks. In the past decade, the research on controllability of complex networks has flourished and a large number of outstanding achievements have emerged. However, few people pay attention to the problem of the minimum controlled point set and the optimal input configuration of the directed network with arbitrary topology. This paper studies the minimum controlled point set and optimal input configuration in complex network structure, the minimum driving point set and controlled point set in complex network, and the controllability recovery of complex network structure. The main contents of this paper are as follows: aiming at the problem that the least number of driving nodes under different input control does not guarantee the network controllability, the problem of the minimum set of controlled points and the optimal input configuration of the network is studied. Firstly, it is proved that whether the least drive nodes can be controlled by different inputs can guarantee the controllability of the network and whether the network contains unreachable and strongly connected components with perfect matching. Secondly, considering the input reachability and perfect matching condition of network structure, It is pointed out that the key to solve the minimum controlled point set and the optimal input configuration of the network is to find the minimum unmatched node set with the largest intersection and the minimum unreachable state node set. Considering that complex networks generally have large-scale characteristics, A combinatorial optimization algorithm with constraints and a polynomial algorithm based on maximum weight perfect matching are proposed to solve the minimum unmatched node set and the minimum unreachable state node set with maximum intersection. Simulation results on some models and empirical networks show that the structural controllability of the network is related to whether the network contains unreachable strongly connected components with perfect matching. This result is helpful to better understand the relationship between network controllability and network topology. The research framework of complex network structure controllability is not suitable for the controllability of directed weighted or undirected networks, and is based on the precise controllability of complex networks proposed by Yuan et al. The minimum set of driving points and the set of controlled points in complex networks are studied. Firstly, it is shown that the control forces of different sets of minimum driving points are different to the network, and the concept of node control force is introduced to measure the role of nodes in network controllability. Secondly, according to the control force of nodes, an algorithm for solving the minimum set of driving points is given. Experimental results on some models and empirical networks show that the minimum set of driving points solved by this algorithm can ensure the precise controllability of the networks in many models and practical networks. Finally, for the case that the minimum set of driving points can not guarantee the controllability of the network in some networks, and the problem of solving the minimum controlled set of precisely controllable points of the network has been proved to be the status quo of NP-hard. A heuristic algorithm for solving the set of controlled points is presented. For a completely controllable network, malicious attacks or random nodes, even the edge failure may destroy the controllability of the network. The concept of controllability deficiency is introduced to measure the degree of network controllability. A network repair algorithm is proposed for networks with controllable deficiency greater than zero around the minimum input and the least number of nodes that need to be controlled. In real networks and ER stochastic networks, the simulation results on BA scale-free networks show that the cost of repairing complex networks is closely related to the network topology.
【学位授予单位】：青岛大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：O157.5

【相似文献】