Discrete-time quantum walk on complex networks for community detection
arXiv:2005.13104 · doi:10.1103/PhysRevResearch.2.023378
Abstract
We define the discrete-time quantum walk on complex networks and utilize it for community detection. We numerically show that the quantum walk with the Fourier coin is localized in a community to which the initial node belongs. Meanwhile, the quantum walk with the Grover coin tends to be localized around the initial node, not over a community. The probability of the classical random walk on the same network converges to the uniform distribution with a relaxation time generally a priori. We thus claim that the time average of the probability of the Fourier-coin quantum walk on complex networks reveals the community structure more explicitly than that of the 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 US Airport network. We successfully reveals the community structure, the two communities of the instructor and the administrator in the former and major airline companies in the latter.
18 pages, 10 figures, accepted for publication in Physical Review Research
References in corpus (9)
- Modularity and community structure in networks
- Finding community structure in networks using the eigenvectors of matrices
- Cooperative Game Theory Approaches for Network Partitioning
- Maps of random walks on complex networks reveal community structure
- Communicability in complex networks
- Anderson localization transitions with and without random potentials
- Communicability Graph and Community Structures in Complex Networks
- Anderson localization in generalized discrete time quantum walks
- Limit theorems for a localization model of 2-state quantum walks