Spectrum-based methods for multi-leader selection and fragility analysis in complex networks

Abstract

During recent decades we have witnessed rapid development in network analysis, in which the spectrum plays a salient role. The spectrum reflects not only algebraic, but also structural properties of the network. In this thesis, we study two problems in networks using spectrum-based approaches. The first problem is the multi-leader selection in complex networks. While selecting a single leader can be done via various centrality measures, selecting multiple leaders is much more involved than a simple ordering of the nodes in terms of centrality measures. In many situations, it is often desirable to see that the multiple leaders selected are as representative as possible. Motivated by this, we propose a clustering based two-step approach in this thesis. Specifically, in order to select k leaders in a complex network, we first partition the network into k clusters and then find a leader within each cluster. For network partitioning, we propose a hierarchical algorithm by exploiting the properties of the Fiedler vector. For the single leader selection in each cluster, we resort to the eigenvector centrality, the closeness centrality and the effective resistance as useful tools. Examples on several real-world networks are worked out to illustrate the effectiveness of our method. The second problem we study is the fragility analysis of a network under negative-weight perturbations, which can be characterized by the positive semidefiniteness of the Laplacian matrix of such a signed network. It is noted that a symmetric Laplacian defines a unique resistive electrical network, wherein the negative weights correspond to negative resistances. As such, the positive semidefiniteness of the signed Laplacians is equivalent to the passivity of the associated resistive networks. By utilizing the n-port circuit theory, we obtain several equivalent conditions for the signed Laplacians to be positive semidefinite with a simple zero eigenvalue. The result is used to analyze the consensus of multi-agent systems as an interesting application.

Date of Award	2016
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology