Graph Clustering Via QUBO and Digital Annealing
arXiv:2003.03872
Abstract
This article empirically examines the computational cost of solving a known hard problem, graph clustering, using novel purpose-built computer hardware. We express the graph clustering problem as an intra-cluster distance or dissimilarity minimization problem. We formulate our poblem as a quadratic unconstrained binary optimization problem and employ a novel computer architecture to obtain a numerical solution. Our starting point is a clustering formulation from the literature. This formulation is then converted to a quadratic unconstrained binary optimization formulation. Finally, we use a novel purpose-built computer architecture to obtain numerical solutions. For benchmarking purposes, we also compare computational performances to those obtained using a commercial solver, Gurobi, running on conventional hardware. Our initial results indicate the purpose-built hardware provides equivalent solutions to the commercial solver, but in a very small fraction of the time required.
arXiv comment15 page, 1 figure, 2 subfigures
References in corpus (12)
- Community detection in graphs
- Resolution limit in community detection
- Ising formulations of many NP problems
- Finding statistically significant communities in networks
- Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
- Fast community detection by SCORE
- A Tutorial on Formulating and Using QUBO Models
- Testing Network Structure Using Relations Between Small Subgraph Probabilities
- Testing for Global Network Structure Using Small Subgraph Statistics
- Axioms for graph clustering quality functions
- A Statistical Density-Based Analysis of Graph Clustering Algorithm Performance
- Testing Graph Clusterability: Algorithms and Lower Bounds