Graph clustering with Boltzmann machines
  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 $K$-medoids, yield clusters of
superior quality to those obtained with the Louvain algorithm.
