Optimal k-centres of a graph: a system-theoretic approach

Abstract

In a network consisting of n nodes, this paper's goal is to identify the ‘most central’ k nodes with respect to the definitions of centrality proposed in this paper. This concept finds applications in various scenarios, ranging from multi-agent problems where external communication (or leader nodes) must be identified, to more classical use cases like ambulance or facility location problems. Depending on the specific application, there exist several notions of quantifying k-centrality, and the set of best k nodes obviously varies based on the chosen definition. Closely related to graphs, we also explore notions of k-centrality within stochastic matrices. In this paper, we formulate two new metrics and establish connections to a well-studied metric from the literature (that was proposed and more studied for stochastic matrices, and then extended to graph-Laplacians). We prove that these three notions match for path-graphs and formulate an explicit expression for the metric both in general and at optimality. Some of the results extend to graphs more general than path-graphs, and the agreement among the three metrics is later analysed for randomly generated general graphs, where we also include a few other system-theoretic notions and consider these too in the comparison. The first metric proposed in this paper involves maximising the smallest eigenvalue of the graph Laplacian matrix after an appropriate diagonal entry perturbation. This maximisation can be interpreted as minimising the time constant of discharge when a corresponding RC circuit is provided a leakage across various combinations of k capacitors. The second metric focuses on minimising the Perron root of a substochastic matrix that is a principal submatrix of a stochastic matrix: an idea proposed and interpreted in the literature linking it to ‘manufacturing consent’. The third one explores minimising the Perron root of a perturbed (now super-stochastic) matrix, which can be seen as minimising the impact of added stubborn-ness. The first of these metrics is linked to time-constant of a dynamical system and dominance is formalised through k-centrality; later in this paper, we compare these metrics with other system-theoretic notions, namely, observability Gramian and port-centrality in terms of maximum energy extraction from a uniformly charged circuit-system (using the Riccati theory). It is important to emphasise that we consider applications (for example, facility location) when the notions of central nodes are such that the set of the ‘best’ k nodes does not necessarily contain the set of the k−1 nodes: this distinguishes these notions from the well-studied ranking-based metrics. We apply the proposed k-centrality notions to various network structures.