Spectral Partitioning for Node Criticality

Asif, W., Lestas, M., Qureshi, H. K. & Rajarajan, M. (2015). Spectral Partitioning for Node Criticality. 2015 IEEE Symposium on Computers and Communication (ISCC), pp. 877-882. doi: 10.1109/ISCC.2015.7405624

[img]
Preview
Text - Accepted Version
Download (306kB) | Preview

Abstract

Finding critical nodes in a network is a significant task, highly relevant to network vulnerability and security. We consider the node criticality problem as an algebraic connectivity minimization problem where the objective is to choose nodes which minimize the algebraic connectivity of the resulting network. Previous suboptimal solutions of the problem suffer from the computational complexity associated with the implementation of a maximization consensus algorithm. In this work, we use spectral partitioning concepts introduced by Fiedler, to propose a new suboptimal solution which significantly reduces the implementation complexity. Our approach, combined with recently proposed distributed Fiedler vector calculation algorithms enable each node to decide by itself whether it is a critical node. If a single node is required then the maximization algorithm is applied on a restricted set of nodes within the network. We derive a lower bound for the achievable algebraic connectivity when nodes are removed from the network and we show through simulations that our approach leads to algebraic connectivity values close to this lower bound. Similar behaviour is exhibited by other approaches at the expense, however, of a higher implementation complexity.

Item Type: Article
Additional Information: © 2015 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions: School of Engineering & Mathematical Sciences > Engineering
URI: http://openaccess.city.ac.uk/id/eprint/15499

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics