Critical Node Identifcation for accessing network vulnerability, a necessary consideration

Timely identification of critical nodes is crucial for assessing network vulnerability and survivability. This thesis presents two new approaches for the identification of critical nodes in a network with the first being an intuition based approach and the second being build on a mathematical framework. The first approach which is referred to as the Combined Banzhaf & Diversity Index (CBDI) uses a newly devised diversity metric, that uses the variability of a node’s attributes relative to its neighbours and the Banzhaf power index which characterizes the degree of participation of a node in forming the shortest path route. The Banzhaf power index is inspired from the theory of voting games in game theory whereas, the diversity index is inspired from the analysis and understanding of the influence of the average path length of a network on its performance. This thesis also presents a new approach for evaluating this average path length metric of a network with reduced computational complexity and proposes a new mechanism for reducing the average path length of a network for relatively larger network structures. The proposed average path length reduction mechanism is tested for a wireless sensor network and the results compared for multiple existing approaches. It has been observed using simulations that, the proposed average path length reduction mechanism outperforms existing approaches by reducing the average path length to a greater extent and with a simpler hardware requirement. The second approach proposed in this thesis for the identification of critical nodes is build on a mathematical framework and it is based on suboptimal solutions of two optimization problems, namely the algebraic connectivity minimization problem and a min-max network utility problem. The former attempts to address the topological as- pect of node criticality whereas, the latter attempts to address its connection-oriented nature. The suboptimal solution of the algebraic connectivity minimization problem is obtained through spectral partitioning considerations. This approach leads to a distributed solution which is computationally less expensive than other approaches that exist in the literature and is near optimal, in the sense that it is shown through simulations to approximate a lower bound which is obtained analytically. Despite the generality of the proposed approaches, this thesis evaluates their performance on a wireless ad hoc network and demonstrates through extensive simulations that the proposed solutions are able to choose more critical nodes relative to other approaches, as it is observed that when these nodes are removed they lead to the highest degrada- tion in network performance in terms of the achieved network throughput, the average network delay, the average network jitter and the number of dropped packets