Synchronizability and controllability of complex networks : an optimization perspective

從優化角度研究複雜網路之同步性及可控性

Student thesis: Doctoral Thesis

View graph of relations

Author(s)

  • Cuili YANG

Related Research Unit(s)

Detail(s)

Awarding Institution
Supervisors/Advisors
Award date3 Oct 2014

Abstract

Synchronization is always a major topic in the study of complex networks. Its significance is not only for the theoretical development but also for a wide range of real-world applications, including robotics, wireless sensor networks, opinion and information spreading, etc. When synchronization happens, all nodes in a network behave similarly. Since it may not be achievable with only internal interactions of nodes, some design of external control is required. Due to the concern of effectiveness and cost, it is natural to control only a small fraction of nodes to achieve synchronization, and this kind of control schemes is commonly referred to as pinning control. To reflect how easily a network can be controlled, the term controllability or pinning controllability is coined. The focus of this thesis is to explore the enhancement of synchronizability and controllability of complex networks under some specified system constraints, and to study the relationship between structural characteristics and these two ability measures. Inspired by previous research on complex networks, it is noted that network features are strongly determined by the interaction pattern among nodes. This in turn inspires the design of several edge rewiring schemes, forming a key element in this thesis study. Since optimal features are desirable, these schemes are further corporated with some global optimization algorithms, result in a more effective search for the global solutions. Our first rewiring scheme is designed for improving the synchronizability of a network. It involves an edge-addition process based on the information of end nodes' degree sum while the edge-removal procedure relies on the eigenvectors corresponding to the second smallest eigenvalue of the Laplacian matrix of the network. Although the proposed scheme is effective, it is also recognized that it is a greedy approach and thus is only local. To address our first problem, which is to identify the optimal topology with highest synchronizability, the rewiring scheme is combined with Tabu search for a global search capability. As shown in our simulations, this approach outperforms other existing methods in terms of both convergence speed and solution quality. The similar rewiring scheme can be embedded into a multi-objective genetic algorithm to solve a practical problem. We have demonstrated its effectiveness by solving a multi-criteria wireless sensor network problem, targeting application for distributed estimation. As illustrated with our simulation results, the obtained network presents the best estimation performance with longest network life-time. Our work also provides an excellent platform for the study of the relationship between structure and network synchronizability. As a result, the importance of specific network characteristics to distributed estimation is revealed. To study the controllability of a complex network, it is required to specify the pinned nodes and the control gains. Here, by treating the eigenratio of the Laplacian matrix associated to an extended network as controllability measure, a multi-constrained optimization strategy based on genetic algorithm is obtained. The design provides the feasibility to determine the topological structure, the pinned nodes and the corresponding control gains simultaneously. This novel approach suggests a different way in the study of the possible best controllable network design. A detailed investigation has been performed and different criteria are established. Finally, a more complex problem related to the controllability of directed network is presented, in which the constraints on the node degree sequence are specified. In order to perform the analysis, we have investigated the general synchronization criteria of a pinned network, and derived the bounds for the optimal controllability of a network which is indicated by the eigenvalue of a specific matrix. A degree-based rewiring scheme is then designed. In the edge-adding phase, it enhances the linkage between pinned and unpinned nodes, while in the edge-removal phase, it tries to improve the homogeneity of the in-degree distribution of the unpinned nodes. As shown in our simulations, the obtained networks reach the optimal or almost optimal controllability.

    Research areas

  • Synchronous data transmission systems, Network Time Protocol (Computer network protocol), Computer networks, Management, Synchronization