Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1310.6638 · Physical Review X

Community Detection in Quantum Complex Networks

Mauro Faccin, Piotr Migdał, Tomi H. Johnson, Ville Bergholm, Jacob Biamonte

Published Oct 21, 2014• 50 citations
arXivHTMLPDF

Abstract

Determining community structure is a central topic in the study of complex networks, be it technological, social, biological or chemical, static or in interacting systems.In this paper, we extend the concept of community detection from classical to quantum systems-a crucial missing component of a theory of complex networks based on quantum mechanics.We demonstrate that certain quantum mechanical effects cannot be captured using current classical complex network tools and provide new methods that overcome these problems.Our approaches are based on defining closeness measures between nodes, and then maximizing modularity with hierarchical clustering.Our closeness functions are based on quantum transport probability and state fidelity, two important quantities in quantum information theory.To illustrate the effectiveness of our approach in detecting community structure in quantum systems, we provide several examples, including a naturally occurring light-harvesting complex, LHCII.The prediction of our simplest algorithm, semiclassical in nature, mostly agrees with a proposed partitioning for the LHCII found in quantum chemistry literature, whereas our fully quantum treatment of the problem uncovers a new, consistent, and appropriately quantum community structure.

DOI
10.1103/physrevx.4.041012

Related papers

Community Detection in Complex Networks with Quantum Random Walks

Dimitris I. Tsomokos

Complex networks are structurally disordered systems that often display clustering behavior. The emergent clusters, also known as communities, consist of nodes that are more connected among themselves than they are connected with the rest of the network. Analyzing community structure is an important problem in network theory, with numerous applications in different fields. In this work I investigate the evolution of a continuoustime quantum random walk on a social network with benchmark community structure and show that it can be used to perform community detection.

•Dec 14, 2010•2 citations

Community detection in network using Szegedy quantum walk

Md Samsur Rahaman, Supriyo Dutta

In a network, the vertices with similar characteristics construct communities. The vertices in a community are well-connected. Detecting the communities in a network is a challenging and important problem in the theory of complex networks. One approach to solving this problem uses the classical random walks on graphs. In quantum computing, quantum walks are the quantum mechanical counterparts of classical random walks. In this article, we employ a variant of Szegedy's quantum walk to develop a procedure for discovering the communities in networks. The limiting probability distribution of quantum walks assists us in determining the inclusion of a vertex in a community. We apply our community detection procedure to a variety of graphs and social networks, including the relaxed caveman graph, $l$-partition graph, Karate club graph, and the dolphin's social network, among others.

quant-pharXiv:2601.21152•Jan 30, 2026•1 citation

Discrete-time quantum walk on complex networks for community detection

Kanae Mukai, Naomichi Hatano

Many systems such as social networks and biological networks take the form of complex networks, which have a community structure.Community detection in complex networks is of great interest to many researchers in statistical physics and mathematical physics.There have been studies on community detection that use the classical random walk.The present study utilizes the discrete-time quantum walk instead.The quantum walk plays an important role in various fields, especially in research on quantum computers, and attracts much attention from mathematical physics too.The discrete-time quantum walk has two properties: it linearly spreads on a flat space, and it localizes in some cases because of quantum coherence.We demonstrate that these properties of the quantum walk are useful for community detection on complex networks.We define the discrete-time quantum walk on complex networks and utilize it for community detection.We numerically show that the quantum walk with a Fourier coin is localized in a community to which the initial node belongs.Meanwhile, the quantum walk with a Grover coin tends to be localized around the initial node, not over a community.The probability of a classical random walk on the same network converges to a uniform distribution with a relaxation time generally unknown a priori.We thus claim that the time average of the probability of a Fourier-coin quantum walk on complex networks reveals the community structure more explicitly than that of a Grover-coin quantum walk and a snapshot of the classical random walk.We first demonstrate our method of community detection for a prototypical three-community network, producing the correct grouping.We then apply our method to two real-world networks, namely, Zachary's karate club and the U.S. Airport network.We successfully reveal the community structure, the two communities of the instructor and the administrator in the former and major airline companies in the latter.

arXiv:2005.13104•Physical Review Research•Jun 22, 2020•42 citations

Quantum-Powered Deep Learning for Advanced Community Detection in Complex Networks: A Systematic Literature Review

khawla khalfi, Wala Rebhi, Nesrine Ben Yahia

Community detection in complex networks remains a fundamental challenge in network science, with applications across social and biological systems. Various approaches, ranging from optimization techniques to deep learning, have been explored to address this issue. More recently, the emergence of quantum methods has further enhanced computational efficiency, offering new possibilities for improving these existing techniques. In this context, numerous reviews have explored various community detection approaches. However, while some studies have focused individually on deep learning-based methods and quantum-powered techniques, their combined potential remains unexplored. This paper conducts a systematic literature review (SLR) on Quantum-Powered Deep Learning for advanced community detection in complex networks. Adopting a structured methodology, it defines key research questions, selects relevant studies from academic databases, and applies rigorous inclusion/exclusion criteria. The review provides a comprehensive analysis of deep learning-based community detection and quantum computing techniques, evaluating their effectiveness in optimizing community assignments. Selected studies are compared in terms of performance, computational efficiency, and scalability, revealing key advancements and research gaps. Finally, the paper discusses emerging challenges and opportunities, guiding researchers in leveraging the synergy between deep learning and quantum computing for more effective community detection within complex networks.

Procedia Computer Science•Jan 1, 2025•0 citations

Quantum-Social Network Analysis for Community Detection: A Comprehensive Review

Samya Muhuri, Shashank Sheshar Singh

The dynamics and underlying structure of complex social networks (SNs) can be discovered using community detection. Considering how quantum computing might improve community detection techniques is becoming more and more popular in light of recent developments in computing technology. In this article, the rapidly developing topic of quantum-SN analysis for community discovery is thoroughly reviewed. Community detection is studied in the context of several quantum-inspired techniques, including quantum annealing and quantum-inspired optimization. To make use of the strengths of both conventional SN research methods and quantum computing techniques, hybrid quantum-classical approaches are being investigated. Case studies and applications that have made use of quantum-SN analysis methodologies are reviewed to highlight the practical consequences and potential advantages over conventional methods. The article also highlights the challenges and limitations of using quantum computing for SN analysis, including technical constraints and ethical issues. Finally, prospects and future research objectives in the area of quantum-SN analysis are highlighted. This covers possible developments in quantum algorithms for community detection, the incorporation of quantum computing with other SN research tasks, and the significance of multidisciplinary collaborations.

IEEE Transactions on Computational Social Systems•May 30, 2024•16 citations

The foundations of superposition and its use in quantum walks on complex networks

Peter G. Lewis

In classical physics, it is possible in principle to predict with certainty the outcome of any measurement that we might perform on a system. Where we are not able to predict outcome with certainty, we can attribute the uncertainty to incompleteness in our knowledge about the history of the system (its pre-measurement state), or the behaviour of the apparatus we use to measure it. Quantum theory, on the other hand, describes systems where what we can find out about the pre-measurement state is significantly restricted: we are not generally able to predict with certainty the outcome of an arbitrary measurement, even with full knowledge of that system’s history. Superposition states are at the heart of this phenomenon, and do not have an analogue in classical physics. In this thesis we examine superposition states from two points of view. Firstly, following long-running arguments about whether quantum theory can be considered complete, we examine the possibility of an underlying ‘ontological’ model of quantum theory that explains the quantum measurement statistics. We derive the first such model that has the property that a single state in the underlying model is compatible with distinct quantum states, and recovers the measurement statistics for systems of dimension greater than two. Secondly, we examine the dynamics of continuous time quantum walks in complex networks. Discovering community structure in these networks is a useful task to be able to perform, and there are several algorithms using the classical dynamics of random walks to return that structure. We introduce a new ‘centrality measure’ based on the observable dynamics of a quantum walker, and provide an algorithm using our new measure for community detection.

•Oct 1, 2014•1 citation
Determining community structure is a central topic in the study of complex networks, be it technological, social, biological or chemical, static or in interacting systems.In this paper, we extend the concept of community detection from classical to quantum systems-a crucial missing component of a theory of complex networks based on quantum mechanics.We demonstrate that certain quantum mechanical effects cannot be captured using current classical complex network tools and provide new methods that overcome these problems.Our approaches are based on defining closeness measures between nodes, and then maximizing modularity with hierarchical clustering.Our closeness functions are based on quantum transport probability and state fidelity, two important quantities in quantum information theory.To illustrate the effectiveness of our approach in detecting community structure in quantum systems, we provide several examples, including a naturally occurring light-harvesting complex, LHCII.The prediction of our simplest algorithm, semiclassical in nature, mostly agrees with a proposed partitioning for the LHCII found in quantum chemistry literature, whereas our fully quantum treatment of the problem uncovers a new, consistent, and appropriately quantum community structure.
Complex networks are structurally disordered systems that often display clustering behavior. The emergent clusters, also known as communities, consist of nodes that are more connected among themselves than they are connected with the rest of the network. Analyzing community structure is an important problem in network theory, with numerous applications in different fields. In this work I investigate the evolution of a continuoustime quantum random walk on a social network with benchmark community structure and show that it can be used to perform community detection.
In a network, the vertices with similar characteristics construct communities. The vertices in a community are well-connected. Detecting the communities in a network is a challenging and important problem in the theory of complex networks. One approach to solving this problem uses the classical random walks on graphs. In quantum computing, quantum walks are the quantum mechanical counterparts of classical random walks. In this article, we employ a variant of Szegedy's quantum walk to develop a procedure for discovering the communities in networks. The limiting probability distribution of quantum walks assists us in determining the inclusion of a vertex in a community. We apply our community detection procedure to a variety of graphs and social networks, including the relaxed caveman graph, lll-partition graph, Karate club graph, and the dolphin's social network, among others.
Many systems such as social networks and biological networks take the form of complex networks, which have a community structure.Community detection in complex networks is of great interest to many researchers in statistical physics and mathematical physics.There have been studies on community detection that use the classical random walk.The present study utilizes the discrete-time quantum walk instead.The quantum walk plays an important role in various fields, especially in research on quantum computers, and attracts much attention from mathematical physics too.The discrete-time quantum walk has two properties: it linearly spreads on a flat space, and it localizes in some cases because of quantum coherence.We demonstrate that these properties of the quantum walk are useful for community detection on complex networks.We define the discrete-time quantum walk on complex networks and utilize it for community detection.We numerically show that the quantum walk with a Fourier coin is localized in a community to which the initial node belongs.Meanwhile, the quantum walk with a Grover coin tends to be localized around the initial node, not over a community.The probability of a classical random walk on the same network converges to a uniform distribution with a relaxation time generally unknown a priori.We thus claim that the time average of the probability of a Fourier-coin quantum walk on complex networks reveals the community structure more explicitly than that of a Grover-coin quantum walk and a snapshot of the classical random walk.We first demonstrate our method of community detection for a prototypical three-community network, producing the correct grouping.We then apply our method to two real-world networks, namely, Zachary's karate club and the U.S. Airport network.We successfully reveal the community structure, the two communities of the instructor and the administrator in the former and major airline companies in the latter.
Community detection in complex networks remains a fundamental challenge in network science, with applications across social and biological systems. Various approaches, ranging from optimization techniques to deep learning, have been explored to address this issue. More recently, the emergence of quantum methods has further enhanced computational efficiency, offering new possibilities for improving these existing techniques. In this context, numerous reviews have explored various community detection approaches. However, while some studies have focused individually on deep learning-based methods and quantum-powered techniques, their combined potential remains unexplored. This paper conducts a systematic literature review (SLR) on Quantum-Powered Deep Learning for advanced community detection in complex networks. Adopting a structured methodology, it defines key research questions, selects relevant studies from academic databases, and applies rigorous inclusion/exclusion criteria. The review provides a comprehensive analysis of deep learning-based community detection and quantum computing techniques, evaluating their effectiveness in optimizing community assignments. Selected studies are compared in terms of performance, computational efficiency, and scalability, revealing key advancements and research gaps. Finally, the paper discusses emerging challenges and opportunities, guiding researchers in leveraging the synergy between deep learning and quantum computing for more effective community detection within complex networks.
The dynamics and underlying structure of complex social networks (SNs) can be discovered using community detection. Considering how quantum computing might improve community detection techniques is becoming more and more popular in light of recent developments in computing technology. In this article, the rapidly developing topic of quantum-SN analysis for community discovery is thoroughly reviewed. Community detection is studied in the context of several quantum-inspired techniques, including quantum annealing and quantum-inspired optimization. To make use of the strengths of both conventional SN research methods and quantum computing techniques, hybrid quantum-classical approaches are being investigated. Case studies and applications that have made use of quantum-SN analysis methodologies are reviewed to highlight the practical consequences and potential advantages over conventional methods. The article also highlights the challenges and limitations of using quantum computing for SN analysis, including technical constraints and ethical issues. Finally, prospects and future research objectives in the area of quantum-SN analysis are highlighted. This covers possible developments in quantum algorithms for community detection, the incorporation of quantum computing with other SN research tasks, and the significance of multidisciplinary collaborations.
In classical physics, it is possible in principle to predict with certainty the outcome of any measurement that we might perform on a system. Where we are not able to predict outcome with certainty, we can attribute the uncertainty to incompleteness in our knowledge about the history of the system (its pre-measurement state), or the behaviour of the apparatus we use to measure it. Quantum theory, on the other hand, describes systems where what we can find out about the pre-measurement state is significantly restricted: we are not generally able to predict with certainty the outcome of an arbitrary measurement, even with full knowledge of that system’s history. Superposition states are at the heart of this phenomenon, and do not have an analogue in classical physics. In this thesis we examine superposition states from two points of view. Firstly, following long-running arguments about whether quantum theory can be considered complete, we examine the possibility of an underlying ‘ontological’ model of quantum theory that explains the quantum measurement statistics. We derive the first such model that has the property that a single state in the underlying model is compatible with distinct quantum states, and recovers the measurement statistics for systems of dimension greater than two. Secondly, we examine the dynamics of continuous time quantum walks in complex networks. Discovering community structure in these networks is a useful task to be able to perform, and there are several algorithms using the classical dynamics of random walks to return that structure. We introduce a new ‘centrality measure’ based on the observable dynamics of a quantum walker, and provide an algorithm using our new measure for community detection.