Graph clustering with Boltzmann machines
arXiv:2203.02471 · doi:10.1016/j.dam.2023.10.012
Abstract
Graph clustering is the process of grouping vertices into densely connected sets called clusters. We tailor two mathematical programming formulations from the literature, to this problem. In doing so, we obtain a heuristic approximation to the intra-cluster density maximization problem. We use two variations of a Boltzmann machine heuristic to obtain numerical solutions. For benchmarking purposes, we compare solution quality and computational performances to those obtained using a commercial solver, Gurobi. We also compare clustering quality to the clusters obtained using the popular Louvain modularity maximization method. Our initial results clearly demonstrate the superiority of our problem formulations. They also establish the superiority of the Boltzmann machine over the traditional exact solver. In the case of smaller less complex graphs, Boltzmann machines provide the same solutions as Gurobi, but with solution times that are orders of magnitude lower. In the case of larger and more complex graphs, Gurobi fails to return meaningful results within a reasonable time frame. Finally, we also note that both our clustering formulations, the distance minimization and -medoids, yield clusters of superior quality to those obtained with the Louvain algorithm.
References in corpus (15)
- Fast unfolding of communities in large networks
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Community detection in graphs
- Finding community structure in very large networks
- Resolution limit in community detection
- Ising formulations of many NP problems
- Exchange Monte Carlo Method and Application to Spin Glass Simulations
- Community detection in networks: A user guide
- Parallel Tempering: Theory, Applications, and New Perspectives
- Finding statistically significant communities in networks
- The performance of modularity maximization in practical contexts
- Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
- Fast community detection by SCORE
- A Tutorial on Formulating and Using QUBO Models