Aggregating Centrality Rankings
Definition
Aggregating Centrality Rankings considers several numerical topological descriptors of the nodes’ importance (e.g., degree, betweenness, closeness, etc.) and convert such descriptors into ratio matrices; then, it extend the Analytic Hierarchy Process problem to the case of multiple ratio matrices and resort to a Logarithmic Least Squares formulation to identify an aggregated metric that represents a good tradeoff among the different topological descriptors.
The following description indicates the methodology adopted to calculate an aggregated ranking that is representative of several rankings over the same set of alternatives.
Considering a situation where we are given $m$ cardinal rankings $r^{(1)}, . . . , r^{(m)}$ over the set of $n$ nodes in a given graph. In particular, each ranking $r^{(i)}$ is an $n × 1$ vector having positive entries, and $r^{(i)}_j$ represents the numerical value or utility associated to the $j$-th node according to the $i$-th ranking. In order to obtain an aggregated ranking that is representative for the given $m$ rankings, our approach is composed of two logical steps: (1) converting the rankings into ratio matrices and (2) calculating the overall ranking. During the first step, we convert each ranking $r^{(i)}$ into an $n × n$ matrix $W^{(i)}$ such that the $(u, v)$-th entry $W^{(i)}_{uv}$ is in the form $W^{(i)}_{uv} = r^{(i)}_u / r^{(i)}_v$ . In other words, $W^{(i)}_{uv}$ models the relative utility or importance of the $u$-th alternative over the $j$-th one according to the $i$-th ranking. As a second step, we aim at finding the ranking vector $w^∗$ that solves the following problem.
Problem 1. Find $w^∗ \in {R}^n$ that solves
$${\underset{W\in R ^n}{arg min}}f(w)= {\underset{i=1}{\overset{m}{\sum}}} {\underset{u=1}{\overset{m}{\sum}}} {\underset{v=1}{\overset{m}{\sum}}} (Ln(W^i_{uv})-log (w_u)+log (w_v))$$
subject to
$$\{w_u >0, \forall_u \in {1,..., n}.$$
The above problem aims at finding the vector $w^∗$ such that the logarithm of the ratio of its components is the least squares compromise among the logarithms of the corresponding ratios $W^{(i)}_uv$ . In other words, Problem 1 aims at finding the weight $w_u$, to be assigned to each node, such that the ratios $w_u/w_v$ minimize the deviation from respect to the ratios $W^{(i)}_{uv}$ for the $m$ considered criteria. In order to solve this problem, which is in general non-convex and may have non unique solution, we aim at finding a vector $y^{\ast}$ such that $w^∗ = exp(y∗)$, where $exp(·)$ is the component-wise exponential; in other words, we aim at solving the following unconstrained problem.
Problem 2. Find $y^∗ \in R^n$ that solves
$${\underset{y\in R ^n}{arg min}}g(y)= {\underset{i=1}{\overset{m}{\sum}}} {\underset{u=1}{\overset{n}{\sum}}} {\underset{v=1}{\overset{n}{\sum}}} (Ln(W^i_{uv})- y_u+y_v)^2$$
The above problem is easily solved in a closed form. Specifically, being an unconstrained convex problem, the minimum is attained at $y^∗$ such that, for all $u\in {1, . . . , n}$, it holds ${\partial_{g(y)} \over \partial_{y_u}}|_{y=y^*}=0.$ By some algebra, it can be shown that the optimal $y^∗$ satisfies
$$m(n I_n - 1_n 1_n^T) y^* = {\underset{i=1}{\overset {m}{\sum}}} log(W^{(i)})1_n .$$
where $log(W^{(i)})$ is the $n \times n$ matrix collecting the logarithm of the corresponding entries of $W^{(i)}$ (note that we assumed the rankings have positive entries hence the logarithm is always finite). Note further that matrix $n I_n −1_n1_n^T$ is the Laplacian matrix of a complete graph and is singular; hence, in order to find $y^∗$, one may need to resort to a pseudoinverse, i.e., by setting
$$y^*= {1\over m} {(n I_n - 1_n 1_n^T)^†} {\underset{i=1}{\overset{m}{\sum}}} log(W^{(i)})1_n.$$
where ${(n I_n - 1_n 1_n^T)^†}$ denotes the left pseudoinverse of $n I_n - 1_n 1_n^T$. An alternative approach is to solve in an approximated way via the differential equation
$$\bar y(t)= m (1_n 1_n^T - nI_n) y(t) {\underset{i=1}{\overset{m}{\sum}}} log(W^{(i)})1_n.$$
which is known to asymptotically converges to a vector that satisfies the above singular system of equations.
Generally, different ranking criteria capture peculiar elements in terms of node criticality. Hence, any one of them provides a useful point of view to better understand the role and the relevance of each node. Consequently, selecting one ranking criterion while discarding another, may lead to misleading prioritizations in the protection strategies. To overcome such a limit we propose to aggregate the different ranking criteria into a single “super-ranking”,
The following description indicates the methodology adopted to calculate an aggregated ranking that is representative of several rankings over the same set of alternatives.
Considering a situation where we are given $m$ cardinal rankings $r^{(1)}, . . . , r^{(m)}$ over the set of $n$ nodes in a given graph. In particular, each ranking $r^{(i)}$ is an $n × 1$ vector having positive entries, and $r^{(i)}_j$ represents the numerical value or utility associated to the $j$-th node according to the $i$-th ranking. In order to obtain an aggregated ranking that is representative for the given $m$ rankings, our approach is composed of two logical steps: (1) converting the rankings into ratio matrices and (2) calculating the overall ranking. During the first step, we convert each ranking $r^{(i)}$ into an $n × n$ matrix $W^{(i)}$ such that the $(u, v)$-th entry $W^{(i)}_{uv}$ is in the form $W^{(i)}_{uv} = r^{(i)}_u / r^{(i)}_v$ . In other words, $W^{(i)}_{uv}$ models the relative utility or importance of the $u$-th alternative over the $j$-th one according to the $i$-th ranking. As a second step, we aim at finding the ranking vector $w^∗$ that solves the following problem.
Problem 1. Find $w^∗ \in {R}^n$ that solves
$${\underset{W\in R ^n}{arg min}}f(w)= {\underset{i=1}{\overset{m}{\sum}}} {\underset{u=1}{\overset{m}{\sum}}} {\underset{v=1}{\overset{m}{\sum}}} (Ln(W^i_{uv})-log (w_u)+log (w_v))$$
subject to
$$\{w_u >0, \forall_u \in {1,..., n}.$$
The above problem aims at finding the vector $w^∗$ such that the logarithm of the ratio of its components is the least squares compromise among the logarithms of the corresponding ratios $W^{(i)}_uv$ . In other words, Problem 1 aims at finding the weight $w_u$, to be assigned to each node, such that the ratios $w_u/w_v$ minimize the deviation from respect to the ratios $W^{(i)}_{uv}$ for the $m$ considered criteria. In order to solve this problem, which is in general non-convex and may have non unique solution, we aim at finding a vector $y^{\ast}$ such that $w^∗ = exp(y∗)$, where $exp(·)$ is the component-wise exponential; in other words, we aim at solving the following unconstrained problem.
Problem 2. Find $y^∗ \in R^n$ that solves
$${\underset{y\in R ^n}{arg min}}g(y)= {\underset{i=1}{\overset{m}{\sum}}} {\underset{u=1}{\overset{n}{\sum}}} {\underset{v=1}{\overset{n}{\sum}}} (Ln(W^i_{uv})- y_u+y_v)^2$$
The above problem is easily solved in a closed form. Specifically, being an unconstrained convex problem, the minimum is attained at $y^∗$ such that, for all $u\in {1, . . . , n}$, it holds ${\partial_{g(y)} \over \partial_{y_u}}|_{y=y^*}=0.$ By some algebra, it can be shown that the optimal $y^∗$ satisfies
$$m(n I_n - 1_n 1_n^T) y^* = {\underset{i=1}{\overset {m}{\sum}}} log(W^{(i)})1_n .$$
where $log(W^{(i)})$ is the $n \times n$ matrix collecting the logarithm of the corresponding entries of $W^{(i)}$ (note that we assumed the rankings have positive entries hence the logarithm is always finite). Note further that matrix $n I_n −1_n1_n^T$ is the Laplacian matrix of a complete graph and is singular; hence, in order to find $y^∗$, one may need to resort to a pseudoinverse, i.e., by setting
$$y^*= {1\over m} {(n I_n - 1_n 1_n^T)^†} {\underset{i=1}{\overset{m}{\sum}}} log(W^{(i)})1_n.$$
where ${(n I_n - 1_n 1_n^T)^†}$ denotes the left pseudoinverse of $n I_n - 1_n 1_n^T$. An alternative approach is to solve in an approximated way via the differential equation
$$\bar y(t)= m (1_n 1_n^T - nI_n) y(t) {\underset{i=1}{\overset{m}{\sum}}} log(W^{(i)})1_n.$$
which is known to asymptotically converges to a vector that satisfies the above singular system of equations.
Generally, different ranking criteria capture peculiar elements in terms of node criticality. Hence, any one of them provides a useful point of view to better understand the role and the relevance of each node. Consequently, selecting one ranking criterion while discarding another, may lead to misleading prioritizations in the protection strategies. To overcome such a limit we propose to aggregate the different ranking criteria into a single “super-ranking”,
References
- Oliva G., Esposito Amideo A., Starita S., Setola R., Scaparra M.P., 2020. Aggregating centrality rankings: A novel approach to detect critical infrastructure vulnerabilities. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 11777 LNCS, pp.57-68.
DOI: 10.1007/978-3-030-37670-3_5
