Quantum Motif Clustering
arXiv:2111.13222 · doi:10.22331/q-2023-07-03-1046
Abstract
We present three quantum algorithms for clustering graphs based on higher-order patterns, known as motif clustering. One uses a straightforward application of Grover search, the other two make use of quantum approximate counting, and all of them obtain square-root like speedups over the fastest classical algorithms in various settings. In order to use approximate counting in the context of clustering, we show that for general weighted graphs the performance of spectral clustering is mostly left unchanged by the presence of constant (relative) errors on the edge weights. Finally, we extend the original analysis of motif clustering in order to better understand the role of multiple `anchor nodes' in motifs and the types of relationships that this method of clustering can and cannot capture.
arXiv comment51 pages, 11 figures
References in corpus (13)
- The diameter of the world wide web
- Benchmark graphs for testing community detection algorithms
- Quantum Amplitude Amplification and Estimation
- Higher-order organization of complex networks
- Biological network comparison using graphlet degree distribution
- Tight bounds on quantum searching
- Large-scale topological and dynamical properties of Internet
- The phase transition in inhomogeneous random graphs
- Class of correlated random networks with hidden variables
- Generating simple random graphs with prescribed degree distribution
- Focus beyond quadratic speedups for error-corrected quantum advantage
- Counting cliques and cycles in scale-free inhomogeneous random graphs
- Hypergraph Clustering Based on PageRank