TY - GEN
T1 - Core-periphery Partitioning and Quantum Annealing
AU - Higham, Catherine F.
AU - Higham, Desmond J
AU - Tudisco, Francesco
N1 - Funding Information:
The work of CFH was supported by the Engineering and Physical Sciences Research Council UK Quantum Technology Programme under grant EP/M01326X/1. The work of DJH was supported by the Engineering and Physical Sciences Research Council under grants EP/P020720/1 and EP/V015605/1. The work of FT was supported by MUR-Pro3 grant “STANDS”. We would like to thank D-Wave for developer time on D-Wave Systems and Mason A. Porter for supplying the code implementing GenBE. For the purpose of open access, the authors have applied a creative commons attribution licence (CCBY) to any author accepted manuscript version arising.
Publisher Copyright:
© 2022 ACM.
PY - 2022/8/31
Y1 - 2022/8/31
N2 - We propose a new kernel that quantifies success for the task of computing a core-periphery partition for an undirected network. Finding the associated optimal partitioning may be expressed in the form of a quadratic unconstrained binary optimization (QUBO) problem, to which a state-of-the-art quantum annealer may be applied. We therefore make use of the new objective function to (a) judge the performance of a quantum annealer, and (b) compare this approach with existing heuristic core-periphery partitioning methods. The quantum annealing is performed on a commercially available D-Wave machine. The QUBO problem involves a full matrix even when the underlying network is sparse. Hence, we develop and test a sparsified version of the original QUBO which increases the available problem dimension for the quantum annealer. Results are provided on both synthetic and real data sets, and we conclude that the QUBO/quantum annealing approach offers benefits in terms of optimizing this new quantity of interest.
AB - We propose a new kernel that quantifies success for the task of computing a core-periphery partition for an undirected network. Finding the associated optimal partitioning may be expressed in the form of a quadratic unconstrained binary optimization (QUBO) problem, to which a state-of-the-art quantum annealer may be applied. We therefore make use of the new objective function to (a) judge the performance of a quantum annealer, and (b) compare this approach with existing heuristic core-periphery partitioning methods. The quantum annealing is performed on a commercially available D-Wave machine. The QUBO problem involves a full matrix even when the underlying network is sparse. Hence, we develop and test a sparsified version of the original QUBO which increases the available problem dimension for the quantum annealer. Results are provided on both synthetic and real data sets, and we conclude that the QUBO/quantum annealing approach offers benefits in terms of optimizing this new quantity of interest.
U2 - 10.1145/3534678.3539261
DO - 10.1145/3534678.3539261
M3 - Conference contribution
SP - 565
EP - 573
BT - KDD '22: Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
PB - Association for Computing Machinery (ACM)
T2 - KDD '22: Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
Y2 - 14 August 2022 through 18 August 2022
ER -