Multi-leader Selection in Complex Networks

In this paper, we study the multi-leader selection problem 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 order 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, a clustering based two-step approach is proposed in this paper. 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.