Modularity maximization and community detection in complex networks through recursive and hierarchical annealing in the D-Wave Advantage quantum processing units
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917233614127104 |
|---|---|
| author | Falcó-Roget, Joan Jurek, Kacper Wojtarowicz, Barbara Capała, Karol Rycerz, Katarzyna |
| author_facet | Falcó-Roget, Joan Jurek, Kacper Wojtarowicz, Barbara Capała, Karol Rycerz, Katarzyna |
| contents | 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 computing times. Lastly, due to its recursive nature, the annealing process returns intermediate subdivisions thus offering interpretable rather than black-box solutions. These \textit{dendrograms} can 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_07744 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Modularity maximization and community detection in complex networks through recursive and hierarchical annealing in the D-Wave Advantage quantum processing units Falcó-Roget, Joan Jurek, Kacper Wojtarowicz, Barbara Capała, Karol Rycerz, Katarzyna Physics and Society Social and Information Networks Combinatorics 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 computing times. Lastly, due to its recursive nature, the annealing process returns intermediate subdivisions thus offering interpretable rather than black-box solutions. These \textit{dendrograms} can 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. |
| title | Modularity maximization and community detection in complex networks through recursive and hierarchical annealing in the D-Wave Advantage quantum processing units |
| topic | Physics and Society Social and Information Networks Combinatorics |
| url | https://arxiv.org/abs/2410.07744 |