Achievement
In this paper, we put forth rigorous network-driven definitions of vulnerable, important, and critical nodes in a directed dependency graph motivated by real-world graph infrastructure. We then formulate these definitions in the language of Google's PageRank, and demonstrate that by identifying critical nodes in an infrastructure network (UrbanNet), we can determine which pieces of infrastructure to which we should provide redundancy. We finally show that our notion of critical nodes in a directed graph constitute a well-defined notion of graph centrality.
Significance and Impact
The significance of this paper is two-fold:
- Introduce a new graph centrality measure (that is, a measure of how 'central' a vertex is in a graph)
- Use our notion of centrality to determine pieces of infrastructure of note in a real world network.
The notion of centrality is motivated by the extant literature on critical infrastructure networks. A piece of infrastructure (water stations, power plants, hospitals e.g.,) is frequently referred to as vulnerable, important, or critical. These definitions are frequently described colloquially, but have the same general meanings:
- Vulnerable infrastructure: An infrastructure which is dependent on many infrastructures. That is, a cascading failure in the network is likely to cause failure in this infrastructure, or a random failure in the network is likely to affect this infrastructure.
- Important infrastructure: An infrastructure whose failure is likely to cascade to many other infrastructures, or an infrastructure on whom many further infrastructures depend.
- Critical infrastructure: An infrastructure which is both vulnerable and important. That is an infrastructure which is likely to fail given a failure in an infrastructure network and whose failure will propagate far in an infrastructure network.
An infrastructure network can be modeled as a directed graph, where each vertex is an infrastructure asset, and there is an edge from asset A to asset B if a failure in A is likely to induce a failure in B. The probability of failure can then be assigned as a weight to each edge. An infrastructure failure (which can cause further failures, who in turn can cause further failures) can be modeled by the experiment where when a node 'fails', the outgoing edges are viewed as IID bernoulli trials whose success probability is the probability of failure.
Given such an infrastructure network, we want to reframe the above intuitive notions of vulnerable, important, and critical in the language of Google's PageRank algorithm. Here, we provide an intuitive notion of what PageRank means, and how this translates to the above notions. Loosely speaking, the PageRank of a node in a (directed) graph is a measure of how likely you are to see that node if you choose an arbitrary node, and take random steps down outgoing edges for some number of steps. That is, the PageRank of a node v is a measure of how likely it is you see it in a random walk from an arbitrary starting node. Hence we have:
- A vulnerable node has a high PageRank, because a failure in an arbitrary node is likely to reach this node.
Importance is a dual notion to vulnerability, in the sense that arbitrary failures are likely to reach vulnerable nodes while a failure in an important node is likely to reach many (arbitrary) nodes. Hence, to compute the importance of a node we compute the PageRank in the graph where the directed edges are reversed (the Reverse PageRank).
- An important node has a high Reverse PageRank, because its failure is likely to reach many arbitrary nodes.
So a critical node is a node with a high PageRank and Reverse PageRank simultaneously. While studies of PageRank and Reverse PageRank are not novel, there are few (if any- our literature search yielded none) which combined both metrics into a single meaningful metric with a useful real-world application.
Research Details
After defining the infrastructure network and the measures of vulnerable, important, and critical nodes in terms of PageRank and Reverse PageRank, we tested our measure on a real world network (UrbanNet, a network consisting of tens of thousands of real world infrastructure assets and millions of edges determined by a nearest-neighbor type criteria). Using network X we pre-computed the PageRank and Reverse PageRank score of each infrastructure asset. We then computed the most critical nodes, and we 'protect' those nodes from failure. We then simulate failure in a small number of nodes and allow the failures to propagate through the network, and observe how much of the network fails. We repeat the experiment by protecting both arbitrary nodes and nodes only which have high out degree. We found that the 'arbitrary' node protection fails to protect most of the infrastructure network, while the high degree node protections perform comparably to protecting the high criticality score. We have further observed that in more highly connected graphs that protecting high criticality score nodes do better at protecting a larger proportion of the network from propagating through the network. Thus, we demonstrate that this so-called criticality score is among the useful centrality measures in a directed graph, and can be used in real world scenarios to decide which infrastructure assets one should provide redundancy to in order to prevent arbitrary failures to cascade throughout a network.
Last Updated: January 13, 2022 - 10:25 am