City Research Online

Optimization based spectral partitioning for node criticality assessment

Asif, W., Lestas, M., Khaliq Qureshi, H. & Rajarajan, M. (2016). Optimization based spectral partitioning for node criticality assessment. Journal of Network and Computer Applications, 75, pp. 279-292. doi: 10.1016/j.jnca.2016.09.003


Timely identification of critical nodes is crucial for assessing network vulnerability and survivability. In this work, we propose a new distributed algorithm for identifying critical nodes in a network. The proposed approach 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 aspect 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 approach, in this work we evaluate its performance on a wireless ad hoc network. We demonstrate through extensive simulations that the proposed solution is 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 degradation in network performance in terms of the achieved network throughput, the average network delay, the average network jitter and the number of dropped packets.

Publication Type: Article
Additional Information: © 2016, Elsevier. Licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
Publisher Keywords: Algebraic connectivity; Spectral partitioning; Network utility maximization; Node criticality; Fiedler vector
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments: School of Science & Technology > Engineering
SWORD Depositor:
[thumbnail of Optimization Based Spectral Partitioning for Node Criticality Assessment (2).pdf]
Text - Accepted Version
Available under License : See the attached licence file.

Download (988kB) | Preview
[thumbnail of Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International Licence]
Text (Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International Licence) - Other
Download (201kB) | Preview


Add to AnyAdd to TwitterAdd to FacebookAdd to LinkedinAdd to PinterestAdd to Email


Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login