Discrete-time quantum walk on complex networks for community detection

Abstract

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.