Examination Committee

Prof Ling SHI, ECE/HKUST (Chairperson)
Prof Li QIU, ECE/HKUST (Thesis Supervisor)
Prof Weichuan YU, ECE/HKUST

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 select multiple leaders as representative as possible. Motivated by this, we propose a clustering based two-step approach. Specifically, 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 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 a multi-agent system as an application.