Ising-Based Louvain Method: Clustering Large Graphs with Specialized Hardware

Abstract

Recent advances in specialized hardware for solving optimization problems such quantum computers, quantum annealers, and CMOS annealers give rise to new ways for solving real-word complex problems. However, given current and near-term hardware limitations, the number of variables required to express a large real-world problem easily exceeds the hardware capabilities, thus hybrid methods are usually developed in order to utilize the hardware. In this work, we advocate for the development of hybrid methods that are built on top of the frameworks of existing state-of-art heuristics, thereby improving these methods. We demonstrate this by building on the so called Louvain method, which is one of the most popular algorithms for the Community detection problem and develop and Ising-based Louvain method. The proposed method outperforms two state-of-the-art community detection algorithms in clustering several small to large-scale graphs. The results show promise in adapting the same optimization approach to other unsupervised learning heuristics to improve their performance.

arXiv comment12 pages, 2 figures, submitted to IDA2021

References in corpus (16)

• 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
• From Louvain to Leiden: guaranteeing well-connected communities
• Uncovering the overlapping community structure of complex networks in nature and society
• Cooperative Game Theory Approaches for Network Partitioning
• Functional cartography of complex metabolic networks
• Benchmark graphs for testing community detection algorithms
• Detecting fuzzy community structures in complex networks with a Potts model
• Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
• Spectral methods for network community detection and graph partitioning
• Community detection in networks: Modularity optimization and maximum likelihood are equivalent
• Quantum Annealing for Combinatorial Clustering
• Detecting Multiple Communities Using Quantum Annealing on the D-Wave System
• Network Community Detection On Small Quantum Computers

Cited by in corpus (3)

• Airbnb Price Prediction Using Machine Learning and Sentiment Analysis
• Limitations in Parallel Ising Machine Networks: Theory and Practice
• When in Doubt, Ask: Generating Answerable and Unanswerable Questions, Unsupervised