Graph clustering with Boltzmann machines

DOI10.1016/J.DAM.2023.10.012MaRDI QIDQ6140246zbMATH OpenOpenAlexFDO

Authors Pierre Miasnikof, Mohammad Bagherbeik, Ali Sheikholeslami

Publication date 2 January 2024

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2203.02471

zbMATH Keywords

Boltzmann machinecombinatorial optimizationgraph clusteringmeta-heuristicsnetwork community detection

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

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

Recommendations

• Graph clustering via intra-cluster density maximization
• scientific article; zbMATH DE number 558545
• Metric-Constrained Optimization for Graph Clustering Algorithms
• scientific article; zbMATH DE number 5360747
• Graph clustering

Cites work

• A Statistical Performance Analysis of Graph Clustering Algorithms
• Algorithms for graph partitioning on the planted partition model
• Application of statistical mechanics to NP-complete problems in combinatorial optimisation
• Bad communities with high modularity
• Community detection by modularity maximization using GRASP with path relinking
• Community structure in social and biological networks
• Fast community detection by SCORE
• Fast unfolding of communities in large networks
• Graph clustering
• Graph clustering via intra-cluster density maximization
• scientific article; zbMATH DE number 6180551 (Why is no real title available?)
• Least squares quantization in PCM
• Linear and quadratic programming approaches for the general graph partitioning problem
• Modularity in several random graph models
• Modularity of complex networks models
• Multi-way clustering and biclustering by the ratio cut and normalized cut in graphs
• Optimization by simulated annealing
• Resistance distance distribution in large sparse random graphs
• Robust optimization of graph partitioning and critical node detection in analyzing networks
• Robust optimization of graph partitioning involving interval uncertainty

This page was built for publication: Graph clustering with Boltzmann machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6140246)