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:2601.21152

Community detection in network using Szegedy quantum walk

Md Samsur Rahaman, Supriyo Dutta

quant-phcs.SImath.COphysics.soc-phSubmitted Jan 29, 2026• Announced Jan 30, 2026• 0 citations
v1 · Jan 29, 2026v2 · Feb 9, 2026
arXivHTMLPDF

Abstract

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 solve this problem uses the classical random walks on the 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 procedure of community detection on a number of graphs and social networks, such as the relaxed caveman graph, $l$-partition graph, Karate club graph, dolphin's social network, etc.

Comments
Comments are welcome!

Related papers

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•37 citations

Community Detection in Quantum Complex Networks

Mauro Faccin, Piotr Migdał, Tomi H. Johnson +2 more

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.

arXiv:1310.6638•Physical Review X•Oct 21, 2014•43 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•14 citations

Quantum Walk-Based Graph Algorithms for Scalable Network Analysis

Jincheng Zhang

This paper investigates the application of quantum walk algorithms to address the computational challenges inherent in analyzing large and complex networks. Traditional graph algorithms often suffer from exponential scaling, rendering them impractical for networks with a substantial number of nodes and edges. We propose a framework leveraging quantum walks to perform network exploration and analysis tasks, aiming to achieve significant speedups compared to their classical counterparts. The core of our approach lies in simulating a quantum walk on the graph, where the walker's movement is governed by quantum mechanical principles, promoting parallel exploration of the graph's connectivity. We detail the theoretical foundations of this approach, focusing on the mathematical formulation of quantum walk operators and their application to graph traversal and algorithm design. Furthermore, we explore specific network analysis problems, such as shortest path finding and community detection, demonstrating the potential of this methodology. The results presented suggest that quantum walk-based algorithms offer a promising avenue for scalable network analysis, particularly for large networks where classical algorithms face limitations.

•Sep 5, 2026•0 citations

Quadratic speedup for finding marked vertices by Quantum walks

Andris Ambainis, András Gilyén, Stacey Jeffery +1 more

A quantum walk algorithm can detect the presence of a marked vertex on a graph quadratically faster than the corresponding random walk algorithm (Szegedy, FOCS 2004). However, quantum algorithms that actually find a marked element quadratically faster than a classical random walk were only known for the special case when the marked set consists of just a single vertex, or in the case of some specific graphs. We present a new quantum algorithm for finding a marked vertex in any graph, with any set of marked vertices, that is (up to a log factor) quadratically faster than the corresponding classical random walk, resolving a question that had been open for 15 years.

arXiv:1903.07493•ACM Symposium on Theory of Computing (STOC)•Jun 7, 2020•45 citations

Quantum Random Walk-Enhanced Framework for Social Network Analysis

Weronika Iga Halikowa, Norbert Głębocki

In this research, the computational efficiency of large-scale social network analysis is enhanced by the use of quantum random walk algorithms. The goal of this project is to address the need for high-efficiency centralized analysis of large-scale, heterogeneous social networks, community discovery, and dynamic effect mapping. In a theoretically sound framework of quantum random walks, amplitude superposition and unitary evolution principles have been used to improve both the sensitivity to local and global aspects. The solution uses real social network data with up to 5,000 nodes and more than 60,000 edges, and the testing results demonstrate its excellent scalability and fast convergence. Quantum algorithms have discovered community divisions and cut the mixing time by roughly 2.3 times after multiple optimizations. The performance indicators demonstrate that the above method has greatly improved key node detection accuracy and computation time as compared to the conventional baseline model in noisy situations. According to the aforementioned research, quantum-inspired algorithms have been used to expedite the analysis of large-scale data and reveal hidden structures that are challenging to identify using conventional techniques, such as bridge nodes and core-periphery distributions. The research assist data-driven choices in digital social ecosystems and lay the groundwork for in-depth network analysis.

Journal of Applied Automation Technologies•Sep 26, 2025•0 citations
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 solve this problem uses the classical random walks on the 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 procedure of community detection on a number of graphs and social networks, such as the relaxed caveman graph, lll-partition graph, Karate club graph, dolphin's social network, etc.
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.
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.
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.
This paper investigates the application of quantum walk algorithms to address the computational challenges inherent in analyzing large and complex networks. Traditional graph algorithms often suffer from exponential scaling, rendering them impractical for networks with a substantial number of nodes and edges. We propose a framework leveraging quantum walks to perform network exploration and analysis tasks, aiming to achieve significant speedups compared to their classical counterparts. The core of our approach lies in simulating a quantum walk on the graph, where the walker's movement is governed by quantum mechanical principles, promoting parallel exploration of the graph's connectivity. We detail the theoretical foundations of this approach, focusing on the mathematical formulation of quantum walk operators and their application to graph traversal and algorithm design. Furthermore, we explore specific network analysis problems, such as shortest path finding and community detection, demonstrating the potential of this methodology. The results presented suggest that quantum walk-based algorithms offer a promising avenue for scalable network analysis, particularly for large networks where classical algorithms face limitations.
A quantum walk algorithm can detect the presence of a marked vertex on a graph quadratically faster than the corresponding random walk algorithm (Szegedy, FOCS 2004). However, quantum algorithms that actually find a marked element quadratically faster than a classical random walk were only known for the special case when the marked set consists of just a single vertex, or in the case of some specific graphs. We present a new quantum algorithm for finding a marked vertex in any graph, with any set of marked vertices, that is (up to a log factor) quadratically faster than the corresponding classical random walk, resolving a question that had been open for 15 years.
In this research, the computational efficiency of large-scale social network analysis is enhanced by the use of quantum random walk algorithms. The goal of this project is to address the need for high-efficiency centralized analysis of large-scale, heterogeneous social networks, community discovery, and dynamic effect mapping. In a theoretically sound framework of quantum random walks, amplitude superposition and unitary evolution principles have been used to improve both the sensitivity to local and global aspects. The solution uses real social network data with up to 5,000 nodes and more than 60,000 edges, and the testing results demonstrate its excellent scalability and fast convergence. Quantum algorithms have discovered community divisions and cut the mixing time by roughly 2.3 times after multiple optimizations. The performance indicators demonstrate that the above method has greatly improved key node detection accuracy and computation time as compared to the conventional baseline model in noisy situations. According to the aforementioned research, quantum-inspired algorithms have been used to expedite the analysis of large-scale data and reveal hidden structures that are challenging to identify using conventional techniques, such as bridge nodes and core-periphery distributions. The research assist data-driven choices in digital social ecosystems and lay the groundwork for in-depth network analysis.