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 (21)
- Community structure in social and biological networks
- Modularity and community structure in networks
- Community detection in graphs
- Finding community structure in very large 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
- Defining and identifying communities in networks
- Quantum Computation and Decision Trees
- A Quantum Random Walk Search Algorithm
- Communicability in complex networks
- Localization and Spreading of Diseases in Complex Networks
- Implementing the quantum random walk
- One-Dimensional Three-State Quantum Walk
- Localization of Two-Dimensional Quantum Walks
- Quantum walk-based search and centrality
- Anderson localization transitions with and without random potentials
- Communicability Graph and Community Structures in Complex Networks
- Anderson localization in generalized discrete time quantum walks
- Optimized evolution of networks for principal eigenvector localization
- Limit theorems for a localization model of 2-state quantum walks
Cited by in corpus (15)
- Localized creation of yellow single photon emitting carbon complexes in hexagonal boron nitride
- Review on Quantum Walk Computing: Theory, Implementation, and Application
- Efficient implementation of discrete-time quantum walks on quantum computers
- Comparative study of quantum emitter fabrication in wide bandgap materials using localized electron irradiation
- Quantum transport efficiency in noisy random-removal and small-world networks
- Coin dimensionality as a resource in quantum metrology involving discrete-time quantum walks
- Null-eigenvalue localization of quantum walks on real-world complex networks
- Quantum hub and authority centrality measures for directed networks based on continuous-time quantum walks
- NISQ-ready community detection based on separation-node identification
- Non-Markovianity in Discrete-Time Open Quantum Random Walk on Arbitrary Graphs
- Quantum walk on simplicial complexes for simplicial community detection
- QWalkVec: Node Embedding by Quantum Walk
- Universal scaling hypothesis of quantum spatial search in complex networks
- Quantum state transfer and periodicity in discrete-time quantum walks under non--Markovian dephasing noise
- Circuit Implementation of Discrete-Time Quantum Walks on Complex Networks