Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity

• URL: http://arxiv.org/abs/2209.04562v5
• Date: Thu, 24 Oct 2024 21:45:34 GMT
• Title: Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
• Authors: Samin Aref, Mahdi Mostajabdaveh, Hriday Chheda,
• Abstract summary: We compare 30 community detection methods including our algorithm that offers optimality and approximation guarantees: the Bayan algorithm. Compared to the partitions from 29 other algorithms, maximum-modularity partitions have the best medians for description length, coverage, performance, average conductance, and well clusteredness. A Python implementation of the Bayan (bayanpy) is publicly available through the package installer for Python.
• Score: 0.8450726582512176
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Community detection is a classic network problem with extensive applications in various fields. Its most common method is using modularity maximization heuristics which rarely return an optimal partition or anything similar. Partitions with globally optimal modularity are difficult to compute, and therefore have been underexplored. Using structurally diverse networks, we compare 30 community detection methods including our proposed algorithm that offers optimality and approximation guarantees: the Bayan algorithm. Unlike existing methods, Bayan globally maximizes modularity or approximates it within a factor. Our results show the distinctive accuracy and stability of maximum-modularity partitions in retrieving planted partitions at rates higher than most alternatives for a wide range of parameter settings in two standard benchmarks. Compared to the partitions from 29 other algorithms, maximum-modularity partitions have the best medians for description length, coverage, performance, average conductance, and well clusteredness. These advantages come at the cost of additional computations which Bayan makes possible for small networks (networks that have up to 3000 edges in their largest connected component). Bayan is several times faster than using open-source and commercial solvers for modularity maximization, making it capable of finding optimal partitions for instances that cannot be optimized by any other existing method. Our results point to a few well performing algorithms, among which Bayan stands out as the most reliable method for small networks. A Python implementation of the Bayan algorithm (bayanpy) is publicly available through the package installer for Python.

Related papers

• Scaling LLM Inference with Optimized Sample Compute Allocation [56.524278187351925]
  We propose OSCA, an algorithm to find an optimal mix of different inference configurations. Our experiments show that with our learned mixed allocation, we can achieve accuracy better than the best single configuration. OSCA is also shown to be effective in agentic beyond single-turn tasks, achieving a better accuracy on SWE-Bench with 3x less compute than the default configuration.
  arXiv  Detail & Related papers  (2024-10-29T19:17:55Z)
• Multimodal Optimization with k-Cluster Big Bang-Big Crunch Algorithm and Postprocessing Methods for Identification and Quantification of Optima [0.7639610349097473]
  Multimodal optimization is often encountered in engineering problems, especially when different and alternative solutions are sought. This paper investigates whether a less-known, the Big Bang-Big Crunch (BBBC) algorithm, is suitable for multimodal optimization.
  arXiv  Detail & Related papers  (2023-12-21T06:16:32Z)
• Analyzing Modularity Maximization in Approximation, Heuristic, and Graph Neural Network Algorithms for Community Detection [1.1220356822493742]
  Our study assesses the performance of various modularity-based algorithms in obtaining optimal partitions. We observe that near-optimal partitions are often disproportionately dissimilar to any optimal partition. If modularity is to be used for detecting communities, we recommend approximate optimization algorithms for a more methodologically sound usage of modularity.
  arXiv  Detail & Related papers  (2023-10-17T00:12:18Z)
• Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar [0.0]
  We investigate the extent to which current modularity algorithms succeed in returning maximum-modularity partitions. We compare eight existing algorithms against an exact integer programming method that globally maximizes modularity. Our results show that near-optimal partitions are often disproportionately dissimilar to any optimal partition.
  arXiv  Detail & Related papers  (2023-02-28T16:11:08Z)
• Late Fusion Multi-view Clustering via Global and Local Alignment Maximization [61.89218392703043]
  Multi-view clustering (MVC) optimally integrates complementary information from different views to improve clustering performance. Most of existing approaches directly fuse multiple pre-specified similarities to learn an optimal similarity matrix for clustering. We propose late fusion MVC via alignment to address these issues.
  arXiv  Detail & Related papers  (2022-08-02T01:49:31Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum. Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges. We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
  arXiv  Detail & Related papers  (2022-03-28T21:34:16Z)
• Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs [6.084888301899142]
  We consider a learning-based LNS approach for mixed integer programs (MIPs) We train a Neural Diving model to represent a probability distribution over assignments, which, together with an off-the-shelf MIP solver, generates an initial assignment. We train a Neural Neighborhood Selection policy to select a search neighborhood at each step, which is searched using a MIP solver to find the next assignment.
  arXiv  Detail & Related papers  (2021-07-21T16:43:46Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  In many real world problems, we want to infer some property of an expensive black-box function f, given a budget of T function evaluations. We present a procedure, InfoBAX, that sequentially chooses queries that maximize mutual information with respect to the algorithm's output. On these problems, InfoBAX uses up to 500 times fewer queries to f than required by the original algorithm.
  arXiv  Detail & Related papers  (2021-04-19T17:22:11Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  We propose an efficient method for computing the partition function or MAP estimate in a pairwise MRF. We extend semidefinite relaxations from the typical binary MRF to the full multi-class setting, and develop a compact semidefinite relaxation that can again be solved efficiently using the solver.
  arXiv  Detail & Related papers  (2020-12-04T15:36:29Z)
• Learning All Credible Bayesian Network Structures for Model Averaging [3.81379858342235]
  We propose a novel approach to model averaging inspired by performance guarantees in approximation algorithms. Our approach is more efficient and scales to significantly larger Bayesian networks than existing approaches.
  arXiv  Detail & Related papers  (2020-08-27T19:56:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.