NISQ-Ready Community Detection Based on Separation-Node Identification

Jonas Stein (), Dominik Ott, Jonas Nüßlein, David Bucher, Mirco Schönfeld and Sebastian Feld
Additional contact information
Jonas Stein: Mobile and Distributed Systems Group, LMU Munich, 80538 Munich, Germany
Dominik Ott: Mobile and Distributed Systems Group, LMU Munich, 80538 Munich, Germany
Jonas Nüßlein: Mobile and Distributed Systems Group, LMU Munich, 80538 Munich, Germany
David Bucher: Aqarios GmbH, 80538 Munich, Germany
Mirco Schönfeld: Data Modelling & Interdisciplinary Knowledge Generation, University of Bayreuth, 95445 Bayreuth, Germany
Sebastian Feld: Quantum Machine Learning, Delft University of Technology, 2628 CD Delft, The Netherlands

Mathematics, 2023, vol. 11, issue 15, 1-19

Abstract: The analysis of network structure is essential to many scientific areas ranging from biology to sociology. As the computational task of clustering these networks into partitions, i.e., solving the community detection problem, is generally NP-hard, heuristic solutions are indispensable. The exploration of expedient heuristics has led to the development of particularly promising approaches in the emerging technology of quantum computing. Motivated by the substantial hardware demands for all established quantum community detection approaches, we introduce a novel QUBO-based approach that only needs number-of-nodes qubits and is represented by a QUBO matrix as sparse as the input graph’s adjacency matrix. The substantial improvement in the sparsity of the QUBO matrix, which is typically very dense in related work, is achieved through the novel concept of separation nodes. Instead of assigning every node to a community directly, this approach relies on the identification of a separation-node set , which, upon its removal from the graph, yields a set of connected components, representing the core components of the communities. Employing a greedy heuristic to assign the nodes from the separation-node sets to the identified community cores, subsequent experimental results yield a proof of concept by achieving an up to 95% optimal solution quality on three established real-world benchmark datasets. This work hence displays a promising approach to NISQ-ready quantum community detection, catalyzing the application of quantum computers for the network structure analysis of large-scale, real-world problem instances.

Keywords: quantum computing; community detection; QUBO; NISQ (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/15/3323/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/15/3323/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:15:p:3323-:d:1205398

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().