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.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.21152Jan 30, 20260 citations

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.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.13104Physical Review ResearchJun 22, 202037 citations

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.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, 20102 citations

l

-partition graph, Karate club graph, and the dolphin's social network, among others.