NDLI: Spectral partitioning for node criticality

Content Provider	IEEE Xplore Digital Library
Author	Asif, Waqar Lestas, Marios Qureshi, Hassaan Khaliq Rajarajan, Muttukrishnan
Copyright Year	2015
Description	Author affiliation: Department of Electrical Engineering, Frederick University, Nicosia, Cyprus (Lestas, Marios) \|\| School of Engineering and Mathematical Sciences, City University, London, UK (Rajarajan, Muttukrishnan) \|\| National University of Sciences & Technology (NUST), Islamabad, Pakistan (Asif, Waqar; Qureshi, Hassaan Khaliq)
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.
Starting Page	877
Ending Page	882
File Size	283336
Page Count	6
File Format	PDF
e-ISBN	9781467371940
DOI	10.1109/ISCC.2015.7405624
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-07-06
Publisher Place	Cyprus
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Partitioning algorithms Laplace equations Eigenvalues and eigenfunctions Complexity theory Measurement Computers Electronic mail
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in