Recent advancements in network neuroscience are pointing in the direction of considering the brain as a small-world system with an efficient integration-segregation balance that facilitates different cognitive tasks and functions. In this context, community detection is a pivotal issue in computational neuroscience. In this paper we explored community detection within brain connectomes using the power of quantum annealers, and in particular the Leap's Hybrid Solver in D-Wave. By reframing the modularity optimization problem into a Discrete Quadratic Model, we show that quantum annealers achieved higher modularity indices compared to the Louvain Community Detection Algorithm without the need to overcomplicate the mathematical formulation. We also found that the number of communities detected in brain connectomes slightly differed while still being biologically interpretable. These promising preliminary results, together with recent findings, strengthen the claim that quantum optimization methods might be a suitable alternative against classical approaches when dealing with community assignment in networks.
Recent advancements in network neuroscience are pointing in the direction of considering the brain as a small-world system with an efficient integration-segregation balance that facilitates different cognitive tasks and functions. In this context, community detection is a pivotal issue in computational neuroscience. In this paper we explored community detection within brain connectomes using the power of quantum annealers, and in particular the Leap's Hybrid Solver in D-Wave. By reframing the modularity optimization problem into a Discrete Quadratic Model, we show that quantum annealers achieved higher modularity indices compared to the Louvain Community Detection Algorithm without the need to overcomplicate the mathematical formulation. We also found that the number of communities detected in brain connectomes slightly differed while still being biologically interpretable. These promising preliminary results, together with recent findings, strengthen the claim that quantum optimization methods might be a suitable alternative against classical approaches when dealing with community assignment in networks.
Quantum adiabatic optimization has long been expected to outperform classical methods in solving NP -type problems. While this has been proven in certain experiments, its main applications still reside in academic problems where the size of the system to be solved would not represent an obstacle to any modern desktop computer. Here, we develop a systematic procedure to find the global optima of the modularity function to discover community structure in complex networks solely relying on pure annealers rather than hybrid solutions. We bypass the one-hot encoding constraints by hierarchically and recursively encoding binary instances of the problem that can be solved without the need to guess the exact penalties for the Lagrange multipliers. We study the variability and robustness of the annealing process as a function of network size, directness of connections, topology, and the resolution of the communities. We show how our approach produces meaningful and at least equally optimal solutions to state-of-the-art community detection algorithms while maintaining tractable and potentially scalable computing times. Lastly, due to its recursive nature, the annealing process returns intermediate subdivisions, thus offering interpretable rather than black-box solutions. Thesedendrogramscan be used to unveil normal and pathological hidden hierarchies in brain networks, hence opening the door to clinical workflows. Overall, this represents a first step towards an applicable practice-oriented usage of pure quantum annealing, potentially bridging two segregated communities in modern science and engineering: that of network science and quantum computing.
Abstract Emerging quantum technologies represent a promising alternative for solving hard combinatorial problems in the post-Moore’s law era. For practical purposes, however, the current number of qubits limits the direct applicability to larger real-world instances in the near-term future. Therefore, a promising strategy to overcome this issue is represented by hybrid quantum classical algorithms which leverage classical as well as quantum devices. One prominent example of a hard computational problem is the community detection problem: a partition of a graph into distinct communities such that the ratio between intra-community and inter-community connectivity is maximized. In this paper, we explore the current potential of quantum annealing and gate-based quantum technologies to solve the community detection problem for an arbitrary number of communities. For this purpose, existing algorithms are (re-)implemented and new hybrid algorithms, that can be run on gate-model devices, are proposed. Their performance on standardized benchmark graphs has been evaluated and compared to the one of a state-of-the-art classical heuristic algorithm. Although no quantum speed-up has been achieved, the existing quantum annealing-based methods as well as the novel hybrid algorithms for gate-based quantum computers yield modularity values, which are similar to those of the classical heuristic. However, the modular architecture of the used algorithms allows for fast utilization of more powerful quantum technologies once they become available.Reproducibility:Our code and data are publicly available (Github in Quantum Modularization. https://github.com/jku-win se/quantum_modularization 2021).
A very important problem in combinatorial optimization is the partitioning of a network into communities of densely connected nodes; where the connectivity between nodes inside a particular community is large compared to the connectivity between nodes belonging to different ones. This problem is known as community detection, and has become very important in various fields of science including chemistry, biology and social sciences. The problem of community detection is a twofold problem that consists of determining the number of communities and, at the same time, finding those communities. This drastically increases the solution space for heuristics to work on, compared to traditional graph partitioning problems. In many of the scientific domains in which graphs are used, there is the need to have the ability to partition a graph into communities with the "highest quality" possible since the presence of even small isolated communities can become crucial to explain a particular phenomenon. We have explored community detection using the power of quantum annealers, and in particular the D-Wave 2X and 2000Q machines. It turns out that the problem of detecting at most two communities naturally fits into the architecture of a quantum annealer with almost no need of reformulation. This paper addresses a systematic study of detecting two or more communities in a network using a quantum annealer.
After decades of being mainly confined to theoretical research, Quantum Computing is now becoming a useful tool for solving realistic problems. This work aims to experimentally explore the feasibility of using currently available quantum computers, based on the Quantum Annealing paradigm, to build a recommender system exploiting community detection. Community detection, by partitioning users and items into densely connected clusters, can boost the accuracy of non-personalized recommendation by assuming that users within each community share similar tastes. However, community detection is a computationally expensive process. The recent availability of Quantum Annealers as cloud-based devices, constitutes a new and promising direction to explore community detection, although effectively leveraging this new technology is a long-term path that still requires advancements in both hardware and algorithms. This work aims to begin this path by assessing the quality of community detection formulated as a Quadratic Unconstrained Binary Optimization problem on a real recommendation scenario. Results on several datasets show that the quantum solver is able to detect communities of comparable quality with respect to classical solvers, but with better speedup, and the non-personalized recommendation models built on top of these communities exhibit improved recommendation quality. The takeaway is that quantum computing, although in its early stages of maturity and applicability, shows promise in its ability to support new recommendation models and to bring improved scalability as technology evolves.
Community detection, also known as graph partitioning, is a well-known NP-hard combinatorial optimization problem with applications in diverse fields such as complex network theory, transportation, and smart power grids. The problem's solution space grows drastically with the number of vertices and subgroups, making efficient algorithms crucial. In recent years, quantum computing has emerged as a promising approach to tackling NP-hard problems. This study explores the use of a quantum-inspired algorithm, Simulated Bifurcation (SB), for community detection. Modularity is employed as both the objective function and a metric to evaluate the solutions. The community detection problem is formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem, enabling seamless integration with the SB algorithm. Experimental results demonstrate that SB effectively identifies community structures in benchmark networks such as Zachary's Karate Club and the IEEE 33-bus system. Remarkably, SB achieved the highest modularity, matching the performance of Fujitsu's Digital Annealer, while surpassing results obtained from two quantum machines, D-Wave and IBM. These findings highlight the potential of Simulated Bifurcation as a powerful tool for solving community detection problems.
We present a quantum-inspired algorithm that utilizes Quantum Hamiltonian Descent (QHD) for efficient community detection. Our approach reformulates the community detection task as a Quadratic Unconstrained Binary Optimization (QUBO) problem, and QHD is deployed to identify optimal community structures. We implement a multi-level algorithm that iteratively refines community assignments by alternating between QUBO problem setup and QHD-based optimization. Benchmarking shows our method achieves up to 5.49% better modularity scores while requiring less computational time compared to classical optimization approaches. This work demonstrates the potential of hybrid quantum-inspired solutions for advancing community detection in largescale graph data.