{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T04:06:51Z","timestamp":1768536411811,"version":"3.49.0"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T00:00:00Z","timestamp":1630454400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,9,9]],"date-time":"2021-09-09T00:00:00Z","timestamp":1631145600000},"content-version":"vor","delay-in-days":8,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"CDL-MINT"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"published-print":{"date-parts":[[2021,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Emerging quantum technologies represent a promising alternative for solving hard combinatorial problems in the post-Moore\u2019s 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.<jats:bold>Reproducibility:<\/jats:bold>Our code and data are publicly available (Github in Quantum Modularization.<jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"https:\/\/github.com\/jku-win%20se\/quantum_modularization\">https:\/\/github.com\/jku-win se\/quantum_modularization<\/jats:ext-link>2021).<\/jats:p>","DOI":"10.1007\/s11128-021-03239-1","type":"journal-article","created":{"date-parts":[[2021,9,9]],"date-time":"2021-09-09T06:02:48Z","timestamp":1631167368000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Quantum k-community detection: algorithm proposals and cross-architectural evaluation"],"prefix":"10.1007","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7589-8263","authenticated-orcid":false,"given":"Felix G.","family":"Gemeinhardt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Wille","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manuel","family":"Wimmer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,9,9]]},"reference":[{"key":"3239_CR1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2020.10031","author":"S Akbar","year":"2020","unstructured":"Akbar, S., Saritha, S.K.: Towards quantum computing based community detection. Comput. Sci. Rev. (2020). https:\/\/doi.org\/10.1016\/j.cosrev.2020.10031","journal-title":"Comput. Sci. Rev."},{"key":"3239_CR2","doi-asserted-by":"publisher","unstructured":"Arcuri, A., Briand, L.: A practical guide for using statistical tests to assess randomized algorithms in software engineering. In: 33rd International Conference on Software Engineering (ICSE) (2011). https:\/\/doi.org\/10.1145\/1985793.1985795","DOI":"10.1145\/1985793.1985795"},{"key":"3239_CR3","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2008\/10\/P10008","author":"VD Blondel","year":"2008","unstructured":"Blondel, V.D., Guillaume, J., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. J. Stat. Mech. Theory Experiment. (2008). https:\/\/doi.org\/10.1088\/1742-5468\/2008\/10\/P10008","journal-title":"J. Stat. Mech. Theory Experiment."},{"key":"3239_CR4","unstructured":"Bork, D., Garmendia, A., Wimmer, M.: Towards a Multi-Objective Modularization Approach for Entity-Relationship Models. ER Forum, Demo and Posters 2020, co-located with 39th International Conference on Conceptual Modeling (ER) (2020)"},{"key":"3239_CR5","doi-asserted-by":"publisher","unstructured":"Brambilla, M., Cabot, J., Wimmer, M.: Model-Driven Software Engineering in Practice: Second Edition. Morgan & Claypool Publishers (2017). https:\/\/doi.org\/10.2200\/S00751ED2V01Y201701SWE004","DOI":"10.2200\/S00751ED2V01Y201701SWE004"},{"key":"3239_CR6","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.03.030","author":"S Cafieri","year":"2014","unstructured":"Cafieri, S., Hansen, P., Liberti, L.: Improving heuristics for network modularity maximization using an exact algorithm. Discrete Appl. Math. (2014). https:\/\/doi.org\/10.1016\/j.dam.2012.03.030","journal-title":"Discrete Appl. Math."},{"key":"3239_CR7","unstructured":"Chen, Y.Q., Chen, Y., Lee, C.K., Zhang, S., Hsieh, C.Y.: Optimizing Quantum Annealing Schedules: From Monte Carlo Tree Search to QuantumZero. arXiv:2004.02836. (2020)"},{"key":"3239_CR8","doi-asserted-by":"publisher","unstructured":"Clauset, A., Newman, M.E.J., Moore, C.: Finding community structure in very large networks. Phys. Rev. E Stat. Nonlinear Soft Matter Phys. (2004). https:\/\/doi.org\/10.1103\/PhysRevE.70.066111","DOI":"10.1103\/PhysRevE.70.066111"},{"key":"3239_CR9","doi-asserted-by":"publisher","unstructured":"Condon, A., Karp, R.M.: Algorithms for Graph Partitioning on the Planted Partition Model. In: Hochbaum D.S., Jansen K., Rolim J.D.P., Sinclair A. (eds) Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques. RANDOM 1999, APPROX 1999. Lecture Notes in Computer Science, vol 1671. Springer, Berlin, Heidelberg (1999). https:\/\/doi.org\/10.1007\/978-3-540-48413-4_23","DOI":"10.1007\/978-3-540-48413-4_23"},{"key":"3239_CR10","unstructured":"Farhi, E., Goldstone, J., Gutmann, S.: A Quantum Approximate Optimization Algorithm. arXiv:1411.4028. (2014)"},{"key":"3239_CR11","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2014.03.024","author":"E Ferrara","year":"2014","unstructured":"Ferrara, E., De Meo, P., Catanese, S., Fiumara, G.: Detecting criminal organizations in mobile phone networks. Expert Syst. Appl. (2014). https:\/\/doi.org\/10.1016\/j.eswa.2014.03.024","journal-title":"Expert Syst. Appl."},{"key":"3239_CR12","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002","author":"S Fortunato","year":"2010","unstructured":"Fortunato, S.: Community detection in graphs. Phys. Rep. (2010). https:\/\/doi.org\/10.1016\/j.physrep.2009.11.002","journal-title":"Phys. Rep."},{"key":"3239_CR13","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2016.09.002","author":"S Fortunato","year":"2016","unstructured":"Fortunato, S., Hric, D.: Community detection in networks: A user guide. Phys. Rep. (2016). https:\/\/doi.org\/10.1016\/j.physrep.2016.09.002","journal-title":"Phys. Rep."},{"key":"3239_CR14","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2020.04.124","author":"R George","year":"2020","unstructured":"George, R., Shujaee, K., Kerwat, M., Felfli, Z., Gelenbe, D., Ukuwu, K.: A comparative evaluation of community detection algorithms in social networks. Procedia Comput. Sci. (2020). https:\/\/doi.org\/10.1016\/j.procs.2020.04.124","journal-title":"Procedia Comput. Sci."},{"key":"3239_CR15","unstructured":"Gilliam, A., Woerner, S., Gonciulea, C.: Grover Adaptive Search for Constrained Polynomial Binary Optimization. arXiv:1912.04088v2. (2019)"},{"key":"3239_CR16","doi-asserted-by":"crossref","unstructured":"Girvan, M., Newman, M.: Community structure in social and biological networks. Proc Natl Acad Sci. 99(12) (2001). https:\/\/dx.doi.org\/10.1073%2Fpnas.122653799","DOI":"10.1073\/pnas.122653799"},{"key":"3239_CR17","unstructured":"Github. Quantum Modularization. https:\/\/github.com\/jku-win-se\/quantum_modularization (2021). Accessed June 2021"},{"key":"3239_CR18","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2017.07.035","author":"S Gupta","year":"2017","unstructured":"Gupta, S., Mittal, S., Gupta, T., Singhal, I., Khatri, B., Gupta, A.K., Kumar, N.: Parallel quantum-inspired evolutionary algorithms for community detection in social networks. Appl. Soft Comput. (2017). https:\/\/doi.org\/10.1016\/j.asoc.2017.07.035","journal-title":"Appl. Soft Comput."},{"key":"3239_CR19","doi-asserted-by":"publisher","unstructured":"Lancichinetti, A., Fortunato, S.: Community detection algorithms: a comparative analysis. Phys. Rev. E. Stat. Nonlinear Soft Matter Phys. (2009). https:\/\/doi.org\/10.1103\/PhysRevE.80.056117","DOI":"10.1103\/PhysRevE.80.056117"},{"key":"3239_CR20","doi-asserted-by":"publisher","unstructured":"Lancichinetti, A., Fortunato, S., Radicchi, F.: Benchmark graphs for testing community detection algorithms. Phys. Rev. E. Stat. Nonlinear Soft Matter Phys. (2008). https:\/\/doi.org\/10.1103\/PhysRevE.78.046110","DOI":"10.1103\/PhysRevE.78.046110"},{"key":"3239_CR21","doi-asserted-by":"crossref","unstructured":"Leymann, F., Barzen, J.: The bitter truth about gate-based quantum algorithms in the NISQ era. Quantum Science and Technology. 5(4) (2020)","DOI":"10.1088\/2058-9565\/abae7d"},{"key":"3239_CR22","doi-asserted-by":"crossref","unstructured":"Lotshaw, P.C., Humble, T.S., Herrman, R., Ostrowski, J., Siopsis, G.: Empirical performance bounds for quantum approximate optimization. arXiv:2102.06813. (2021)","DOI":"10.1007\/s11128-021-03342-3"},{"key":"3239_CR23","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177730491","author":"HB Mann","year":"1947","unstructured":"Mann, H.B., Whitney, D.R.: On a test of whether one of two random variables is stochastically larger than the other. Ann. Math. Stat. (1947). https:\/\/doi.org\/10.1214\/aoms\/1177730491","journal-title":"Ann. Math. Stat."},{"key":"3239_CR24","unstructured":"McGeoch, C., Pau, F.: Advantage Datasheet. https:\/\/dwavesys.com\/resources\/publications (2020). Accessed June 2021"},{"key":"3239_CR25","unstructured":"McGeoch, C., Pau, F.: D-Wave Hybrid Solver Service + Advantage: Technology Update. https:\/\/www.dwavesys.com\/hybrid-solver-service-advantage-technology-update-0 (2020). Accessed June 2021"},{"key":"3239_CR26","unstructured":"McGeoch, C., Pau, F.: Hybrid Solver for Discrete Quadratic Models. https:\/\/www.dwavesys.com\/hybrid-solver-discrete-quadratic-models-0 (2020). Accessed June 2021"},{"key":"3239_CR27","doi-asserted-by":"crossref","unstructured":"Mniszewski, S.M., Dub, P.A., Tretiak, S., Anisimov, P.M., Zhang, Y., Negre, C.F.A.: Downfolding the Molecular Hamiltonian Matrix using Quantum Community Detection. arXiv:2011.14268. (2020)","DOI":"10.1038\/s41598-021-83561-x"},{"key":"3239_CR28","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2009.67","author":"D Moody","year":"2009","unstructured":"Moody, D.: The Physics of Notations: toward a scientific basis for constructing visual notations in software engineering. IEEE Trans. Softw. Eng. (2009). https:\/\/doi.org\/10.1109\/TSE.2009.67","journal-title":"IEEE Trans. Softw. Eng."},{"key":"3239_CR29","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0227538","author":"CFA Negre","year":"2020","unstructured":"Negre, C.F.A., Ushijima-Mwesigwa, H., Mniszewski, S.M.: Detecting multiple communities using quantum annealing on the D-Wave system. PLoS ONE (2020). https:\/\/doi.org\/10.1371\/journal.pone.0227538","journal-title":"PLoS ONE"},{"key":"3239_CR30","doi-asserted-by":"crossref","unstructured":"Reittu, H., Kotovirta, V., Leskel\u00e4, L., Rummukainen, H., R\u00e4ty, T.: Towards analyzing large graphs with quantum annealing and quantum gate computers. arXiv:2006.16702. (2020)","DOI":"10.1109\/BigData47090.2019.9006174"},{"key":"3239_CR31","doi-asserted-by":"publisher","DOI":"10.1007\/s10664-008-9102-8","author":"P Runeson","year":"2009","unstructured":"Runeson, P., H\u00f6st, M.: Guidelines for conducting and reporting case study research in software engineering. Empirical Softw. Eng. (2009). https:\/\/doi.org\/10.1007\/s10664-008-9102-8","journal-title":"Empirical Softw. Eng."},{"key":"3239_CR32","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2014.10.023","author":"J Shang","year":"2015","unstructured":"Shang, J., Liu, L., Li, X., Xie, F., Wu, C.: Epidemic spreading on complex networks with overlapping and non-overlapping community structure. Phys. A Stat. Mech. Appl. (2015). https:\/\/doi.org\/10.1016\/j.physa.2014.10.023","journal-title":"Phys. A Stat. Mech. Appl."},{"key":"3239_CR33","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2019.2908942","author":"R Shaydulin","year":"2019","unstructured":"Shaydulin, R., Ushijima-Mwesigwa, H., Negre, C.F.A., Safro, I., Mniszewski, S.M., Alexeev, Y.: A hybrid approach for solving optimization problems on small quantum computers. Computer. (2019). https:\/\/doi.org\/10.1109\/MC.2019.2908942","journal-title":"Computer."},{"key":"3239_CR34","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/ab8c2b","author":"M Streif","year":"2020","unstructured":"Streif, M., Leib, M.: Training the quantum approximate optimization algorithm without access to a quantum processing unit. Quantum Sci Technol. (2020). https:\/\/doi.org\/10.1088\/2058-9565\/ab8c2b","journal-title":"Quantum Sci Technol."},{"key":"3239_CR35","unstructured":"Ushijima-Mwesigwa, H., Shaydulin, R., Negre, C.F.A., Mniszewski, S.M., Alexeev, Y., Safro, I.: Multilevel Combinatorial Optimization Across Quantum Architectures. arXiv:1910.09985. (2019)"},{"key":"3239_CR36","doi-asserted-by":"publisher","DOI":"10.1016\/j.physleta.2018.05.044","author":"M Yuanyuan","year":"2018","unstructured":"Yuanyuan, M., Xiyu, L.: Quantum inspired evolutionary algorithm for community detection in complex networks. Phys. Lett. A. (2018). https:\/\/doi.org\/10.1016\/j.physleta.2018.05.044","journal-title":"Phys. Lett. A."},{"key":"3239_CR37","doi-asserted-by":"publisher","DOI":"10.1086\/jar.33.4.3629752","author":"WW Zachary","year":"1977","unstructured":"Zachary, W.W.: An information flow model for conflict and fission in small groups. J. Anthropol. Res. (1977). https:\/\/doi.org\/10.1086\/jar.33.4.3629752","journal-title":"J. Anthropol. Res."},{"key":"3239_CR38","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevX.10.021067","author":"L Zhou","year":"2020","unstructured":"Zhou, L., Wang, S.T., Choi, S., Pichler, H., Lukin, M.D.: Quantum approximate optimization algorithm: performance, mechanism, and implementation on near-term devices. Phys. Rev. X. (2020). https:\/\/doi.org\/10.1103\/PhysRevX.10.021067","journal-title":"Phys. Rev. X."},{"key":"3239_CR39","unstructured":"Zhu, L., Tang, H.L., Barron, G.S., Calderon-Vargas, F.A., Mayhall, N.J., Barnes, E., Economou, S.E.: An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer. arXiv:2005.10258. (2020)"}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-021-03239-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11128-021-03239-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-021-03239-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,8]],"date-time":"2023-01-08T21:46:37Z","timestamp":1673214397000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11128-021-03239-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9]]},"references-count":39,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["3239"],"URL":"https:\/\/doi.org\/10.1007\/s11128-021-03239-1","relation":{},"ISSN":["1570-0755","1573-1332"],"issn-type":[{"value":"1570-0755","type":"print"},{"value":"1573-1332","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9]]},"assertion":[{"value":"20 February 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 August 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 September 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"This work was partially funded by the Austrian Federal Ministry for Digital and Economic Affairs and the National Foundation for Research, Technology and Development. Furthermore, this work has received funding from the European Research Council (ERC) under the European Union\u2019s Horizon 2020 research and innovation programme (grant agreement No. 101001318) and was partially been supported by the LIT Secure and Correct Systems Lab funded by the State of Upper Austria as well as by the BMK, BMDW, and the State of Upper Austria in the frame of the COMET program (managed by the FFG).","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Funding"}}],"article-number":"302"}}