A QUBO formulation for top-τ eigencentrality nodes

Prosper D Akrobotu; Tamsin E James; Christian F A Negre; Susan M Mniszewski

doi:10.1371/journal.pone.0271292

A QUBO formulation for top-τ eigencentrality nodes

PLoS One. 2022 Jul 14;17(7):e0271292. doi: 10.1371/journal.pone.0271292. eCollection 2022.

Authors

Prosper D Akrobotu^{1

2}, Tamsin E James², Christian F A Negre³, Susan M Mniszewski²

Affiliations

¹ Department of Mathematical Sciences, The University of Texas at Dallas, Richardson, TX, United States of America.
² Computer, Computational, and Statistical Sciences Division, Los Alamos National Laboratory, Los Alamos, NM, United States of America.
³ Theoretical Division, Los Alamos National Laboratory, Los Alamos, NM, United States of America.

Abstract

The efficient calculation of the centrality or "hierarchy" of nodes in a network has gained great relevance in recent years due to the generation of large amounts of data. The eigenvector centrality (aka eigencentrality) is quickly becoming a good metric for centrality due to both its simplicity and fidelity. In this work we lay the foundations for solving the eigencentrality problem of ranking the importance of the nodes of a network with scores from the eigenvector of the network, using quantum computational paradigms such as quantum annealing and gate-based quantum computing. The problem is reformulated as a quadratic unconstrained binary optimization (QUBO) that can be solved on both quantum architectures. The results focus on correctly identifying a given number of the most important nodes in numerous networks given by the sparse vector solution of our QUBO formulation of the problem of identifying the top-τ highest eigencentrality nodes in a network on both the D-Wave and IBM quantum computers.

Publication types

Research Support, Non-U.S. Gov't
Research Support, U.S. Gov't, Non-P.H.S.

MeSH terms

Algorithms
Computing Methodologies*
Quantum Theory*

Grants and funding

This research was supported by the U.S. Department of Energy (DOE) National Nuclear Security Administration (NNSA) Advanced Simulation and Computing (ASC) program at Los Alamos National Laboratory (LANL). This research has been funded by the LANL Laboratory Directed Research and Development (LDRD) under project number 20200056DR.and ASC program. SMM, CFAN, and PDA were funded by LANL LDRD. TEJ was funded by the U.S. Department of Energy (DOE) through a quantum computing program sponsored by the Los Alamos National Laboratory (LANL) Information Science & Technology Institute. Assigned: Los Alamos Unclassified Report LA-UR-21-24030. LANL is operated by Triad National Security, LLC, for the National Nuclear Security Administration of U.S. Department of Energy (Contract No. 89233218NCA000001). The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.