TY - GEN
T1 - A Quantum Algorithm for Assessing Node Importance in the st-Connectivity Attack
AU - Burge, Iain
AU - Barbeau, Michel
AU - Garcia-Alfaro, Joaquin
N1 - Publisher Copyright:
© IFIP International Federation for Information Processing 2025.
PY - 2025/1/1
Y1 - 2025/1/1
N2 - Problems in distributed security often naturally map to graphs. The centrality of nodes assesses the importance of nodes in a graph. It is used in various applications. Cooperative game theory has been used to create nuanced and flexible notions of node centrality. However, the approach is often computationally complex to implement classically. This work describes a quantum approach to approximating the importance of nodes that maintain a target connection. In addition, we detail a method for quickly identifying high-importance nodes. The approximation method relies on quantum subroutines for st-connectivity and approximating Shapley values. The search for important nodes relies on a quantum algorithm to find the maximum. We consider st-connectivity attack scenarios in which a. malicious actor disrupts a subset of nodes to perturb the system functionality. Our methods identify the nodes that are most important in minimizing the impact of the attack. The node centrality metric identifies where more redundancy is required and can be used to enhance network resiliency. Finally, we explore the potential complexity benefits of our quantum approach in contrast to classical random sampling.
AB - Problems in distributed security often naturally map to graphs. The centrality of nodes assesses the importance of nodes in a graph. It is used in various applications. Cooperative game theory has been used to create nuanced and flexible notions of node centrality. However, the approach is often computationally complex to implement classically. This work describes a quantum approach to approximating the importance of nodes that maintain a target connection. In addition, we detail a method for quickly identifying high-importance nodes. The approximation method relies on quantum subroutines for st-connectivity and approximating Shapley values. The search for important nodes relies on a quantum algorithm to find the maximum. We consider st-connectivity attack scenarios in which a. malicious actor disrupts a subset of nodes to perturb the system functionality. Our methods identify the nodes that are most important in minimizing the impact of the attack. The node centrality metric identifies where more redundancy is required and can be used to enhance network resiliency. Finally, we explore the potential complexity benefits of our quantum approach in contrast to classical random sampling.
KW - Distributed system
KW - Game theoretic node centrality
KW - Graph analytics
KW - Quantum computing
KW - st-Connectivity
UR - https://www.scopus.com/pages/publications/105006642472
U2 - 10.1007/978-3-031-92886-4_16
DO - 10.1007/978-3-031-92886-4_16
M3 - Conference contribution
AN - SCOPUS:105006642472
SN - 9783031928857
T3 - IFIP Advances in Information and Communication Technology
SP - 234
EP - 248
BT - ICT Systems Security and Privacy Protection - 40th IFIP International Conference, SEC 2025, Proceedings
A2 - Nemec Zlatolas, Lili
A2 - Rannenberg, Kai
A2 - Welzer, Tatjana
A2 - Garcia-Alfaro, Joaquin
PB - Springer Science and Business Media Deutschland GmbH
T2 - 40th IFIP International Conference on ICT Systems Security and Privacy Protection, SEC 2025
Y2 - 20 May 2025 through 23 May 2025
ER -