assignment exact algorithm

Browse Econ Literature

• Working papers
• Software components
• Book chapters
• JEL classification

More features

• Subscribe to new research

RePEc Biblio

Author registration.

• Economics Virtual Seminar Calendar NEW!

Some searches may not work properly. We apologize for the inconvenience.

A new exact algorithm for the Weapon-Target Assignment problem

• Author & abstract
• 11 References
• 2 Citations
• Most related
• Related works & more

Corrections

• Chen, Danny Z.

Suggested Citation

Download full text from publisher, references listed on ideas.

Follow serials, authors, keywords & more

Public profiles for Economics researchers

Various research rankings in Economics

RePEc Genealogy

Who was a student of whom, using RePEc

Curated articles & papers on economics topics

Upload your paper to be listed on RePEc and IDEAS

New papers by email

Subscribe to new additions to RePEc

EconAcademics

Blog aggregator for economics research

Cases of plagiarism in Economics

About RePEc

Initiative for open bibliographies in Economics

News about RePEc

Questions about IDEAS and RePEc

RePEc volunteers

Participating archives

Publishers indexing in RePEc

Privacy statement

Found an error or omission?

Opportunities to help RePEc

Get papers listed

Have your research listed on RePEc

Open a RePEc archive

Have your institution's/publisher's output listed on RePEc

Get RePEc data

Use data assembled by RePEc

A New Exact Algorithm for the Weapon-Target Assignment Problem

• October 2019
• Omega 98(6):102138
• 98(6):102138
• This person is not on ResearchGate, or hasn't claimed this research yet.

• University of Notre Dame

Discover the world's research

• 25+ million members
• 160+ million publication pages
• 2.3+ billion citations
• INT J INTELL SYST
• Minrui Zhao
• Jiaozhi Han
• Xiaoxue Zhang

• Comput Model Eng Sci
• Guibao Song
• Junpeng Wang
• Jin-Kao Hao

• COMPUT ELECTR ENG
• Xiaochen Wang
• Shaoming He
• Hyo-Sang Shin

• Haiyin Zhou
• Jianmai Shi
• Jiongqi Wang

• Sedat Akleylek

• Sivakumar Rathinam
• David W. Casbeer

• Jonathan Rogers

• Kang Fengju

• Pamela H. Vance
• Jun-Gun Jang

• Bong-Wan Choi
• Jae Joon Suh
• Necip Dirik
• Shane N. Hall
• James T. Moore
• Recruit researchers
• Join for free
• Login Email Tip: Most researchers use their institutional email address as their ResearchGate login Password Forgot password? Keep me logged in Log in or Continue with Google Welcome back! Please log in. Email · Hint Tip: Most researchers use their institutional email address as their ResearchGate login Password Forgot password? Keep me logged in Log in or Continue with Google No account? Sign up

Information

• Author Services

Initiatives

You are accessing a machine-readable page. In order to be human-readable, please install an RSS reader.

All articles published by MDPI are made immediately available worldwide under an open access license. No special permission is required to reuse all or part of the article published by MDPI, including figures and tables. For articles published under an open access Creative Common CC BY license, any part of the article may be reused without permission provided that the original article is clearly cited. For more information, please refer to https://www.mdpi.com/openaccess .

Feature papers represent the most advanced research with significant potential for high impact in the field. A Feature Paper should be a substantial original Article that involves several techniques or approaches, provides an outlook for future research directions and describes possible research applications.

Feature papers are submitted upon individual invitation or recommendation by the scientific editors and must receive positive feedback from the reviewers.

Editor’s Choice articles are based on recommendations by the scientific editors of MDPI journals from around the world. Editors select a small number of articles recently published in the journal that they believe will be particularly interesting to readers, or important in the respective research area. The aim is to provide a snapshot of some of the most exciting work published in the various research areas of the journal.

Original Submission Date Received: .

• Active Journals
• Find a Journal
• Journal Proposal
• Proceedings Series
• For Authors
• For Reviewers
• For Editors
• For Librarians
• For Publishers
• For Societies
• For Conference Organizers
• Open Access Policy
• Institutional Open Access Program
• Special Issues Guidelines
• Editorial Process
• Research and Publication Ethics
• Article Processing Charges
• Testimonials
• Preprints.org
• SciProfiles
• Encyclopedia

Article Menu

• Subscribe SciFeed
• Recommended Articles
• Google Scholar
• on Google Scholar
• Table of Contents

Find support for a specific problem in the support section of our website.

Please let us know what you think of our products and services.

Visit our dedicated information section to learn more about MDPI.

JSmol Viewer

Swarm intelligence algorithms for weapon-target assignment in a multilayer defense scenario: a comparative study.

1. Introduction

2. multilayer defense wta model and benchmark problem, 2.1. wta model under multilayer defense, 2.2. benchmark problem and optimal solution, 3. solving methods, 3.1. aco algorithm, 3.1.1. coding scheme, 3.1.2. definition of search space, 3.1.3. transit probability, 3.1.4. pheromone trail updating, 3.2. bpso algorithm, 3.2.1. coding scheme, 3.2.2. initialization of particle population, 3.2.3. fitness measure, 3.2.4. particle velocity and position updating, 3.3. ipso algorithm, 3.3.1. coding scheme, 3.3.2. initialization of particle population, 3.3.3. fitness measure, 3.3.4. particle velocity and position updating, 3.4. sca algorithm, 4. performance evaluation based on a benchmark problem, 4.1. solving results, 4.2. discussion, 4.2.1. algorithm effectiveness, 4.2.2. comparison of algorithms, 5. solving a large-scale wta problem using ipso, 5.1. solving results, 5.2. discussion, 6. conclusions, author contributions, conflicts of interest.

• Manne, A.S. A Target-Assignment Problem. Oper. Res. 1958 , 6 , 346–351. [ Google Scholar ] [ CrossRef ]
• Day, R.H. Allocating Weapons to Target Complexes by Means of Nonlinear Programming. Oper. Res. 1966 , 14 , 992–1013. [ Google Scholar ] [ CrossRef ]
• Lloyd, S.P.; Witsenhausen, H.S. Weapons Allocation is NP-complete. In Proceedings of the 1986 Summer Conference on Simulation, Reno, NV, USA, 1 January 1986; pp. 1054–1058. [ Google Scholar ]
• Denbroeder, G.G.; Ellison, R.E.; Emerling, L. On Optimum Target Assignments. Oper. Res. 1959 , 7 , 322–326. [ Google Scholar ] [ CrossRef ]
• Orlin, D. Optimal weapons allocation against layered defenses. Nav. Res. Logist. 1987 , 34 , 605–617. [ Google Scholar ] [ CrossRef ]
• Chang, T.; Kong, D.; Hao, N.; Xu, K.; Yang, G. Solving the dynamic weapon target assignment problem by an improved artificial bee colony algorithm with heuristic factor initialization. Appl. Soft Comput. 2018 , 70 , 845–863. [ Google Scholar ] [ CrossRef ]
• Wang, C.; Fu, G.; Zhang, D.; Wang, H.; Zhao, J. Genetic Algorithm-Based Variable Value Control Method for Solving the Ground Target Attacking Weapon-Target Allocation Problem. Math. Probl. Eng. 2019 , 2019 , 1–9. [ Google Scholar ] [ CrossRef ] [ Green Version ]
• Guo, D.; Liang, Z.; Jiang, P.; Dong, X.; Li, Q.; Ren, Z. Weapon-Target Assignment for Multi-to-Multi Interception with Grouping Constraint. IEEE Access 2019 , 7 , 34838–34849. [ Google Scholar ] [ CrossRef ]
• Xin, B.; Wang, Y.; Chen, J. An Efficient Marginal-Return-Based Constructive Heuristic to Solve the Sensor–Weapon–Target Assignment Problem. IEEE Trans. Syst. Man Cybern. Syst. 2019 , 49 , 2536–2547. [ Google Scholar ] [ CrossRef ]
• De Rezende, M.; De Lima, B.S.L.P.; Guimarães, S. A Greedy Ant Colony System for Defensive Resource Assignment Problems. Appl. Artif. Intell. 2018 , 32 , 138–152. [ Google Scholar ] [ CrossRef ]
• Cao, M.; Fang, W. Distributed MMAS for weapon target assignment based on Spark framework. J. Intell. Fuzzy Syst. 2018 , 35 , 3685–3696. [ Google Scholar ] [ CrossRef ]
• Jaiswal, N.; Shrotri, P.; Nagabhushana, B. Optimal Weapon Mix, Deployment and Allocation Problems in Multiple Layer Defense. Am. J. Math. Manag. Sci. 1993 , 13 , 53–82. [ Google Scholar ] [ CrossRef ]
• Jaiswal, N.K. Military Operations Research: Quantitative Decision Making ; Kluwer Academic Publishers: Norwell, MA, USA, 1997. [ Google Scholar ]
• Malhotra, A.; Jain, R.K. Genetic algorithm for optimal weapon allocation in multilayer defence scenario. Def. Sci. J. 2001 , 51 , 285–293. [ Google Scholar ] [ CrossRef ] [ Green Version ]
• Ciobanu, C.; Marin, G. On Heuristic Optimization. An. St. Univ. Ovidius Constantza 2001 , 9 , 17–30. [ Google Scholar ]
• Bisht, S. Hybrid Genetic-simulated Annealing Algorithm for Optimal Weapon Allocation in Multilayer Defence Scenario. Def. Sci. J. 2004 , 54 , 395–405. [ Google Scholar ] [ CrossRef ] [ Green Version ]
• Dorigo, M. Optimization, Learning and Natural Algorithms. Ph.D Thesis, Politecnico di Milano, Milano, Italy, 1992. [ Google Scholar ]
• Dorigo, M.; Maniezzo, V.; Colorni, A. Ant system: Optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern. Part B 1996 , 26 , 29–41. [ Google Scholar ] [ CrossRef ] [ Green Version ]
• Kennedy, J.; Eberhart, R. Particle Swarm Optimization. In Proceedings of the IEEE International Conference on Neural Networks (ICNN’95), Perth, Australia, 27 November–1 December 1995; Volume 1944, pp. 1942–1948. [ Google Scholar ]
• Bonabeau, E.; Dorigo, M.; Theraulaz, G. Swarm Intelligence: From Natural to Artificial Systems ; Oxford University Press: Oxford, UK, 1999. [ Google Scholar ]
• Kennedy, J. Review of Engelbrecht’s Fundamentals of Computational Swarm Intelligence. Genet. Program. Evolvable Mach. 2007 , 8 , 107–109. [ Google Scholar ] [ CrossRef ]
• Dorigo, M.; Gambardella, L.M.; Birattari, M.; Martinoli, A.; Poli, R.; Stützle, T. Ant Colony Optimization and Swarm Intelligence ; Springer: Berlin/Heidelberg, Germany, 2006. [ Google Scholar ]
• Vuppalapati, S.; Srivastava, A. Application of ant colony optimization for reconfiguration of shipboard power system. Int. J. Eng. Sci. Technol. 2010 , 2 , 119–131. [ Google Scholar ] [ CrossRef ]
• Jeung, H.-S.; Choi, H.-G. Particle swarm optimization in multi-stage operations for operation sequence and DT allocation. Comput. Ind. Eng. 2012 , 62 , 442–450. [ Google Scholar ] [ CrossRef ]
• Huang, H.; Qin, H.; Hao, Z.; Lim, A. Example-based learning particle swarm optimization for continuous optimization. Inf. Sci. 2012 , 182 , 125–138. [ Google Scholar ] [ CrossRef ]
• Lee, Z.-J.; Lee, C.-Y.; Su, S.-F. An immunity-based ant colony optimization algorithm for solving weapon–target assignment problem. Appl. Soft Comput. 2002 , 2 , 39–47. [ Google Scholar ] [ CrossRef ]
• Lee, Z.-J.; Lee, C.-Y. A hybrid search algorithm with heuristics for resource allocation problem. Inf. Sci. 2005 , 173 , 155–167. [ Google Scholar ] [ CrossRef ]
• Ghazanfar, A.; Fang, W.; Shi, R. Decision Making Using Discrete Particle Swarm Optimization on Weapon Target Allocation in Multilayer Air Defense. In Proceedings of the 9th International Conference on Industrial Management, Osaka, Japan, 16–18 September 2008; pp. 737–745. [ Google Scholar ]
• Selvi, S.T.; Malmathanraj, R.; Raj, S.M. Solving Missile Defense and Interceptor Allocation Problem Using Reinforcement Learning and Optimization Techniques. Int. J. Recent Trends Eng. 2009 , 2 , 117–119. [ Google Scholar ]
• Li, X.; Zhou, D.; Yang, Z.; Pan, Q.; Huang, J. A Novel Genetic Algorithm for the Synthetical Sensor-Weapon-Target Assignment Problem. Appl. Sci. 2019 , 9 , 3803. [ Google Scholar ] [ CrossRef ] [ Green Version ]
• Mirjalili, S. SCA: A Sine Cosine Algorithm for solving optimization problems. Knowl. Based Syst. 2016 , 96 , 120–133. [ Google Scholar ] [ CrossRef ]
• Khooban, M.-H.; Vafamand, N.; Liaghat, A.; Dragicevic, T. An optimal general type-2 fuzzy controller for Urban Traffic Network. ISA Trans. 2017 , 66 , 335–343. [ Google Scholar ] [ CrossRef ] [ PubMed ]
• Song, Y.N.; Zhang, F.R.; Liu, C.C. The Risk of Block Chain Financial Market Based on Particle Swarm Optimization. J. Comput. Appl. Math. 2020 , 370 , 10. [ Google Scholar ] [ CrossRef ]
• Farshi, T.R.; Drake, J.H.; Ozcan, E. A Multimodal Particle Swarm Optimization-Based Approach for Image Segmentation. Expert Syst. Appl. 2020 , 149 , 13. [ Google Scholar ] [ CrossRef ]
• Cao, M.; Fang, W. Distributed Computation Based on Spark Framework: A Solution for Weapon Target Assignment Decision Making. In Proceedings of the Service System Engineering Conference & Symposium on Analytics and Risk 2017, Shanghai, China, 7–9 July 2017; pp. 125–137. [ Google Scholar ]
• Marco, D.; Thomas, S. Ant Colony Optimization Theory. In Ant Colony Optimization ; MITP: Moscow Oblast, Russian, 2004. [ Google Scholar ]
• Song, Y.-H.; Lu, H.; Lee, K.Y.; Yu, I.K. Fundamentals of Ant Colony Search Algorithms. In Modern Heuristic Optimization Techniques: Theory and Applications to Power Systems ; Kwang, Y.L., Mohamed, A.E.-S., Eds.; IEEE: Piscataway, NJ, USA, 2008; pp. 71–87. [ Google Scholar ] [ CrossRef ]
• Yoshikazu, F. Fundamentals of Particle Swarm Optimization Techniques. In Modern Heuristic Optimization Techniques: Theory and Applications to Power Systems ; Kwang, Y.L., Mohamed, A.E.-S., Eds.; IEEE: Piscataway, NJ, USA, 2008; pp. 89–100. [ Google Scholar ] [ CrossRef ]
• Kennedy, J.; Eberhart, R.C. A discrete binary version of the particle swarm algorithm. In Proceedings of the 1997 IEEE International Conference on Systems, Man, and Cybernetics. Computational Cybernetics and Simulation, Orlando, FL, USA, 12–15 October 1997; Volume 5, pp. 4104–4108. [ Google Scholar ]
• Črepinšek, M.; Liu, S.-H.; Mernik, M. Exploration and exploitation in evolutionary algorithms. ACM Comput. Surv. 2013 , 45 , 1–33. [ Google Scholar ] [ CrossRef ]

Click here to enlarge figure

Share and Cite

Cao, M.; Fang, W. Swarm Intelligence Algorithms for Weapon-Target Assignment in a Multilayer Defense Scenario: A Comparative Study. Symmetry 2020 , 12 , 824. https://doi.org/10.3390/sym12050824

Cao M, Fang W. Swarm Intelligence Algorithms for Weapon-Target Assignment in a Multilayer Defense Scenario: A Comparative Study. Symmetry . 2020; 12(5):824. https://doi.org/10.3390/sym12050824

Cao, Ming, and Weiguo Fang. 2020. "Swarm Intelligence Algorithms for Weapon-Target Assignment in a Multilayer Defense Scenario: A Comparative Study" Symmetry 12, no. 5: 824. https://doi.org/10.3390/sym12050824

Article Metrics

Article access statistics, further information, mdpi initiatives, follow mdpi.

Subscribe to receive issue release notifications and newsletters from MDPI journals

• DOI: 10.17485/IJST/2013/V6I4/31867
• Corpus ID: 122445360

A New Reformulation and an Exact Algorithm for the Quadratic Assignment Problem

• Published 1 April 2013
• Mathematics, Computer Science
• Indian journal of science and technology

13 Citations

A data-guided lexisearch algorithm for the quadratic assignment problem, a hybrid tabu search-simulated annealing method to solve quadratic assignment problem, a simple genetic algorithm using sequential constructive crossover for the quadratic assignment problem, a lexisearch algorithm for the distance-constrained vehicle routing problem, application of lexisearch algorithm to vehicle routing problem with time windows, a hybrid algorithm combining lexisearch and genetic algorithms for the quadratic assignment problem.

• Highly Influenced

A Hybrid Method Integrating a Discrete Differential Evolution Algorithm with Tabu Search Algorithm for the Quadratic Assignment Problem: A New Approach for Locating Hospital Departments

Comparison of three neighbor generation structures by simulated annealing method to solve quadratic assignment problem, distance constrained capacitated vehicle touting problem for the abuja post office using lexisearch algorithm, experimental analysis of crossover and mutation operators on the quadratic assignment problem, 35 references, an exact algorithm for the quadratic assignment problem on a tree, a branch-and-bound algorithm for the quadratic assignment problem based on the hungarian method, effective formulation reductions for the quadratic assignment problem, a branch-and-cut algorithm for quadratic assignment problems based on linearizations, solving quadratic assignment problems using convex quadratic programming relaxations, benders' partitioning scheme applied to a new formulation of the quadratic assignment problem, tree elaboration strategies in branch-and- bound algorithms for solving the quadratic assignment problem, assignment and matching problems: solution methods with fortran-programs, qaplib – a quadratic assignment problem library, solution procedures for the dynamic facility layout problem, related papers.

Showing 1 through 3 of 0 Related Papers

]Corresponding author’s email: [email protected]

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

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 (pip).

I Introduction

Community detection (CD), the data-driven process of partitioning nodes within a network [ 1 ] , is a core problem in several fields including physics, mathematics, computer science, biology, and other computational sciences [ 2 ] . Among common approaches for CD are the algorithms which are designed to maximize a utility function, modularity [ 3 ] , across all possible ways that the nodes of the input network can be partitioned into an unspecified number of communities. Modularity measures the fraction of edges within communities minus the expected fraction under a random degree-preserving distribution of the edges. Despite their name and design philosophy, current modularity maximization algorithms, which are used by no less than tens of thousands of peer-reviewed studies [ 4 ] , generally fail to maximize modularity or guarantee proximity to a globally maximum-modularity partition (an optimal partition) [ 5 ] . They have a high risk of failing to obtain relevant communities [ 6 ] and may result in degenerate partitions [ 7 ] that are provably far from the underlying community structure [ 8 , 9 ] .

Modularity is among the first objective functions proposed for optimization-based CD [ 3 , 10 ] . Several limitations of modularity [ 11 ] , including its resolution limit [ 12 ] , have led researchers develop alternative methods for detecting communities using information theory [ 13 , 14 ] , stochastic block modeling (inferential methods) [ 15 , 16 , 17 , 18 , 19 ] , and alternative objective functions [ 20 , 21 , 22 , 23 , 24 ] . In spite of its shortcomings, modularity is the most commonly used method for CD [ 25 , 2 ] , while its mathematically rigorous maximization has remained relatively underexplored [ 26 , 27 , 28 , 5 ] .

We propose the Bayan algorithm: an exact and approximation algorithm for the global maximization of modularity in networks with up to 3000 edges. Bayan resolves a fundamental limitation [ 5 ] of previous modularity-based community detection algorithms which rely on heuristic rules rather than rigorous mathematical optimization (e.g. Integer Programming - IP). We deploy standard techniques from integer programming (and operations research) for solving a network science (and physics) problem. We present in this article the fundamentals of our method using accessible language for network scientists and other practitioners who may deal with optimization for network clustering. We provide detailed references to the Supplementary Information document for additional technical optimization details.

II Exact and approximate vs. heuristic modularity maximization

Maximizing modularity is an NP-hard problem [ 29 ] , which explains the abundance of heuristic algorithms for modularity-based CD. These heuristic algorithms are widely used not only because of their scalability to large networks [ 30 ] , but also because their high risk of failing to obtain relevant communities is not well understood [ 6 ] . The scalability of these heuristics come at a cost: their partitions have no guarantee of proximity to an optimal partition [ 7 ] . In an earlier study [ 5 ] , we compared eight modularity-based methods based on the extent to which they maximize modularity. This included the heuristics known as greedy [ 31 ] , Louvain [ 32 ] , Leicht-Newman (LN) (a.k.a Reichardt-Bornholdt) [ 33 ] , Combo [ 25 ] , Belief [ 34 ] , Paris [ 35 ] , Leiden [ 36 ] , and EdMot [ 37 ] . The results showed that these heuristics rarely return an optimal partition [ 5 ] . Moreover, their sub-optimal partitions tend to be disproportionally dissimilar to any optimal partition [ 8 , 5 ] according to results based on an adjusted mutual information notion of partition similarity [ 38 ] .

There are hundreds of heuristic CD algorithms [ 2 ] , including tens of CD algorithms in publicly available libraries [ 39 , 40 , 41 , 42 ] . However, to the best of our knowledge, there is no study comparing as many as 30 algorithms on standard benchmarks. This gap often leads empirical studies to rely on algorithms that are conveniently accessible or widely adopted [ 4 ] , rather than selecting the most suitable algorithm for the specific CD task at hand.

Given the intricacies and nuances of different CD tasks, it is recommended [ 43 ] to transition from developing general CD algorithms (one-size-fits-all methods) to specialized CD algorithms that perform well on a narrow set of tasks. For the narrow set of small networks with up to 3000 edges (in their largest connected component), advances in IP may push the limits on large networks whose optimal partitions can be obtained using regular computers. While such small networks are sometimes dismissed as having no bearing on practical applications, there are disciplines and application areas where the large majority of networks are small. For example, in psychometric network analysis where community detection is a prevalent method, most networks have fewer than 100 nodes and 89% of networks have fewer than 30 nodes [ 44 ] . For many offline social networks where the nodes are sentient beings (people, animals, or other social collectives), the data collection methods impose some practical bounds on the size and order of the network. For example, unless archival records are used, it is often not practical to survey or interview more than a few hundred people, especially when the tolerance for missing data is very low. Therefore, we argue that small networks are not just toy examples for fields where networks tend to be large-scale, but they are common examples in several other fields, in which network computations can be made more accurate.

The community detection literature offers much fewer exact and approximation methods 1 1 1 We make a distinction between heuristic and approximation methods for optimization in that approximation method have guarantees of proximity to optimal solutions. than heuristics. Each previous exact method has been restricted to a specific network size: Aloise et al. have used column generation to find optimal partitions in networks with up to 512 nodes and 819 edges [ 26 ] (within a 27-hour time limit). Dinh and Thai have used linear programming rounding to approximate optimal partitions for networks with 78-2742 edges while reporting that the exact modularity maximization for such networks is cost-prohibitive [ 27 ] . Sobolevsky et al. have reported guaranteed optimal partitions for networks with up to 50 nodes [ 28 ] . In 2023, Brusco et al. have reported results on optimal partitions for networks with up to 613 edges [ 45 ] .

III Our contributions

Given the recommended directions [ 43 , 5 ] , we propose the Bayan algorithm, a specialized CD method capable of providing a globally optimal partition for small networks.

Bayan can alternatively be used to approximate maximum modularity within a user specified factor at a reduced computation time. This algorithm is theoretically grounded by an IP formulation of the modularity maximization problem [ 27 ] and relies on an exact branch-and-cut scheme for solving the NP-hard optimization problem to global optimality.

We compare Bayan with 29 other CD algorithms. This also allows us to (1) find other accurate and suitable methods regardless of whether they use modularity or not and (2) assess the practical relevance of modularity as an objective function in comparison to a wide range of other proposed approaches for CD.

Our proposed algorithm pushes the largest instances whose maximum-modularity partitions can be obtained exactly on an ordinary computer. Bayan handles previously challenging instances of modularity maximization more efficiently. It also solves new instances that cannot be optimized by any other existing methods (see Tables S3–S5 in the SI for the detailed results).

IV Mathematical Preliminaries

Iv.1 notations.

We represent the simple undirected and unweighted 2 2 2 For the sake of simplicity, we focus on unweighted graphs in this paper. graph G 𝐺 G italic_G with node set V 𝑉 V italic_V and edge set E 𝐸 E italic_E as G = ( V , E ) 𝐺 𝑉 𝐸 G=(V,E) italic_G = ( italic_V , italic_E ) . Graph G 𝐺 G italic_G has | V | = n 𝑉 𝑛 |V|=n | italic_V | = italic_n nodes and | E | = m 𝐸 𝑚 |E|=m | italic_E | = italic_m edges. n 𝑛 n italic_n and m 𝑚 m italic_m are called the order and size of the graph, respectively. The symmetric adjacency matrix of graph G 𝐺 G italic_G is represented by A = [ a i ⁢ j ] A delimited-[] subscript 𝑎 𝑖 𝑗 \textbf{A}=[a_{ij}] A = [ italic_a start_POSTSUBSCRIPT italic_i italic_j end_POSTSUBSCRIPT ] whose entry at row i 𝑖 i italic_i and column j 𝑗 j italic_j is a i ⁢ j subscript 𝑎 𝑖 𝑗 a_{ij} italic_a start_POSTSUBSCRIPT italic_i italic_j end_POSTSUBSCRIPT . Entry a i ⁢ j subscript 𝑎 𝑖 𝑗 a_{ij} italic_a start_POSTSUBSCRIPT italic_i italic_j end_POSTSUBSCRIPT indicates whether node i 𝑖 i italic_i is connected to node j 𝑗 j italic_j ( a i ⁢ j = 1 subscript 𝑎 𝑖 𝑗 1 a_{ij}=1 italic_a start_POSTSUBSCRIPT italic_i italic_j end_POSTSUBSCRIPT = 1 ) or not ( a i ⁢ j = 0 subscript 𝑎 𝑖 𝑗 0 a_{ij}=0 italic_a start_POSTSUBSCRIPT italic_i italic_j end_POSTSUBSCRIPT = 0 ). The degree of node i 𝑖 i italic_i is represented by d i = ∑ j a i ⁢ j subscript 𝑑 𝑖 subscript 𝑗 subscript 𝑎 𝑖 𝑗 d_{i}=\sum_{j}{a_{ij}} italic_d start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT = ∑ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT italic_a start_POSTSUBSCRIPT italic_i italic_j end_POSTSUBSCRIPT . The modularity matrix of graph G 𝐺 G italic_G is represented by B = [ b i ⁢ j ] B delimited-[] subscript 𝑏 𝑖 𝑗 \textbf{B}=[b_{ij}] B = [ italic_b start_POSTSUBSCRIPT italic_i italic_j end_POSTSUBSCRIPT ] whose entries are b i ⁢ j = a i ⁢ j − γ ⁢ d i ⁢ d j / 2 ⁢ m subscript 𝑏 𝑖 𝑗 subscript 𝑎 𝑖 𝑗 𝛾 subscript 𝑑 𝑖 subscript 𝑑 𝑗 2 𝑚 b_{ij}=a_{ij}-{\gamma d_{i}d_{j}}/{2m} italic_b start_POSTSUBSCRIPT italic_i italic_j end_POSTSUBSCRIPT = italic_a start_POSTSUBSCRIPT italic_i italic_j end_POSTSUBSCRIPT - italic_γ italic_d start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_d start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT / 2 italic_m . γ 𝛾 \gamma italic_γ is the resolution parameter 3 3 3 Without loss of generality, we set γ = 1 𝛾 1 \gamma=1 italic_γ = 1 for all the analysis in this paper. The Bayan algorithm also supports other user-specified γ 𝛾 \gamma italic_γ values for multi-resolution modularity maximization. [ 46 ] .

Node set V 𝑉 V italic_V of the input graph G 𝐺 G italic_G can be partitioned into an unspecified number of k 𝑘 k italic_k non-overlapping communities 4 4 4 We focus on the more general CD problem where k 𝑘 k italic_k is not specified by the user. The desired number of communities can be indirectly controlled by changing γ 𝛾 \gamma italic_γ in Bayan. based on the partition P = { V 1 , V 2 , … , V k } 𝑃 subscript 𝑉 1 subscript 𝑉 2 … subscript 𝑉 𝑘 P=\{V_{1},V_{2},\dots,V_{k}\} italic_P = { italic_V start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT , italic_V start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT , … , italic_V start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT } such that ⋃ 1 k V i = V superscript subscript 1 𝑘 subscript 𝑉 𝑖 𝑉 \bigcup_{1}^{k}V_{i}=V ⋃ start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_k end_POSTSUPERSCRIPT italic_V start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT = italic_V and V i ∩ V j = ∅ subscript 𝑉 𝑖 subscript 𝑉 𝑗 V_{i}\cap V_{j}=\emptyset italic_V start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ∩ italic_V start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT = ∅ . Under partition P 𝑃 P italic_P , the relative community assignment of a pair of arbitrary nodes ( i , j ) 𝑖 𝑗 (i,j) ( italic_i , italic_j ) , is either same (represented by 1 − x i ⁢ j = δ ⁢ ( i , j ) = 1 1 subscript 𝑥 𝑖 𝑗 𝛿 𝑖 𝑗 1 1-x_{ij}=\delta(i,j)=1 1 - italic_x start_POSTSUBSCRIPT italic_i italic_j end_POSTSUBSCRIPT = italic_δ ( italic_i , italic_j ) = 1 ) or different (represented by 1 − x i ⁢ j = δ ⁢ ( i , j ) = 0 1 subscript 𝑥 𝑖 𝑗 𝛿 𝑖 𝑗 0 1-x_{ij}=\delta(i,j)=0 1 - italic_x start_POSTSUBSCRIPT italic_i italic_j end_POSTSUBSCRIPT = italic_δ ( italic_i , italic_j ) = 0 ). The partition P 𝑃 P italic_P can therefore be represented as a symmetric partition matrix X = [ x i ⁢ j ] X delimited-[] subscript 𝑥 𝑖 𝑗 \textbf{X}=[x_{ij}] X = [ italic_x start_POSTSUBSCRIPT italic_i italic_j end_POSTSUBSCRIPT ] with binary entries x i ⁢ j subscript 𝑥 𝑖 𝑗 x_{ij} italic_x start_POSTSUBSCRIPT italic_i italic_j end_POSTSUBSCRIPT each indicating the relative community assignment of nodes i 𝑖 i italic_i and j 𝑗 j italic_j .

IV.2 The optimization problem statement

Given undirected and unweighted graph G 𝐺 G italic_G and partition X as input, the modularity function Q ( G , X ) subscript 𝑄 𝐺 X Q_{(G,\textbf{X})} italic_Q start_POSTSUBSCRIPT ( italic_G , X ) end_POSTSUBSCRIPT maps its input to a real value in the range of [ − 0.5 , 1 ] 0.5 1 [-0.5,1] [ - 0.5 , 1 ] according to Eq. ( 1 ).

In the modularity maximization problem for graph G 𝐺 G italic_G , we look for an optimal partition: a partition X ( G ) ∗ subscript superscript X 𝐺 \textbf{X}^{*}_{(G)} X start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT start_POSTSUBSCRIPT ( italic_G ) end_POSTSUBSCRIPT whose modularity is maximum over all possible partitions: X ( G ) ∗ = arg ⁡ max X ⁡ Q ( G , X ) subscript superscript X 𝐺 subscript X subscript 𝑄 𝐺 X \textbf{X}^{*}_{(G)}=\operatorname*{\arg\max}_{\textbf{X}}Q_{(G,\textbf{X})} X start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT start_POSTSUBSCRIPT ( italic_G ) end_POSTSUBSCRIPT = start_OPERATOR roman_arg roman_max end_OPERATOR start_POSTSUBSCRIPT X end_POSTSUBSCRIPT italic_Q start_POSTSUBSCRIPT ( italic_G , X ) end_POSTSUBSCRIPT . Any partition of G 𝐺 G italic_G that in not an optimal partition is a sub-optimal partition.

IV.3 Sparse IP formulation of modularity maximization

The modularity maximization problem can be formulated as an IP model as in Eq. ( 2 ) which is proposed in [ 27 ] .

In the IP model in Eq. ( 2 ) for the input graph G 𝐺 G italic_G , the optimal objective function value Q ( G ) ∗ subscript superscript 𝑄 𝐺 Q^{*}_{(G)} italic_Q start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT start_POSTSUBSCRIPT ( italic_G ) end_POSTSUBSCRIPT equals the maximum modularity of graph G 𝐺 G italic_G . An optimal partition X ( G ) ∗ subscript superscript X 𝐺 \textbf{X}^{*}_{(G)} X start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT start_POSTSUBSCRIPT ( italic_G ) end_POSTSUBSCRIPT is represented by the optimal values of the x i ⁢ j subscript 𝑥 𝑖 𝑗 x_{ij} italic_x start_POSTSUBSCRIPT italic_i italic_j end_POSTSUBSCRIPT variables.

Solving this optimization problem is NP-hard [ 29 ] , but Bayan uses a branch-and-cut scheme for pushing the limit on the largest instances whose maximum-modularity partitions can be obtained exactly (or approximated within a factor) on an ordinary computer within a reasonable time. A narrative description on how the Bayan algorithm solves the IP model in Eq. ( 2 ) is provided in Section V while more technical details are provided in the Supplementary Information (SI) document. A Python implementation of the Bayan algorithm ( bayanpy ) is publicly available through the package installer for Python (pip) .

V The Bayan Algorithm

In this section, we provide a narrative description on the main methodological details of the Bayan algorithm.

V.1 Triangular constraints as a disjunction

Given that the decision variables in the IP model in Eq. ( 2 ) are all binary, the triangular constraints for the triple ( i , j , k ) 𝑖 𝑗 𝑘 (i,j,k) ( italic_i , italic_j , italic_k ) can be written as the logical disjunction of Eq. ( 3 ) and Eq. ( 4 ).

V.2 Branch-and-cut scheme

To maximize modularity using a branch-and-cut scheme, we start by obtaining lower and upper bounds for the IP model in Eq. ( 2 ). Solving the Linear Programming (LP) relaxation resulted from dropping the integrality constraint from the IP model in Eq. ( 2 ) provides an upperbound. Bayan uses Gurobi [ 48 ] to solve all the LP models involved within the branch and cut process. The modularity value of any feasible partition (e.g. obtained using the Combo algorithm, given the relative closeness of its partition to optimal partitions [ 49 ] ) provides a lower bound. These two values form the bounds for the root node of an IP search tree.

V.3 Branching on node triples

We then select a triple ( i , j , k ) 𝑖 𝑗 𝑘 (i,j,k) ( italic_i , italic_j , italic_k ) for which the LP optimal solution violates both Eq. ( 3 ) and Eq. ( 4 ) (see Subsection 1.6 in the SI for more details on triple selection). On the selected triple, we partition the feasible space into two sub-spaces by adding either Eq. ( 3 ) or Eq. ( 4 ) as a cut to the root node problem which leads to a left and a right subproblem. For each subproblem, an upper bound can be obtained by solving the corresponding LP relaxation. Similarly, for each subproblem, a lower bound can be obtained by computing the modularity of a feasible partition obtained using a heuristic (e.g., the Combo algorithm) for the graph modified based on the added cut.

V.4 Manipulating the graph for left subproblems

V.5 manipulating the modularity function for right subproblems, v.6 upperbound and lowerbound for maximum modularity.

The search tree can further be explored by branching based on another triple whose triangular constraints are violated by the new LP optimal solutions. Throughout the search, the largest lower bound is continuously updated and stored as the incumbent , while the largest upper bound (of each level) is stored as the best bound only after completing the computations for each level of the tree.

V.7 Closing nodes in the search tree

Throughout the branching process, three conditions lead to designating a tree node as fathomed . First, the LP solution becoming integer. Second, the LP becoming infeasible. Third, the LP solution becoming smaller than the current incumbent. In all these cases, we do not branch on the node and close it.

V.8 Termination of exact and approximate Bayan

The convergence of incumbent and best bound guarantees that a globally optimal solution has been found. This branch-and-cut scheme gives rise to the Bayan exact algorithm if this convergence is used as the termination criterion. Alternatively, users can set a different termination criterion (specifying a desired run time or an optimality gap tolerance) which leads to the Bayan approximate algorithm for approximating maximum modularity within an optimality gap (the relative gap between the incumbent and best bound at the termination of the algorithm).

Section 1 of the SI document provides six detailed subsections on specific technical details about the more nuanced design aspects of the Bayan algorithm. Having provided an accessible explanation of the Bayan algorithm, we move on to describing how standard benchmarks and partition quality measures are used in our study for comparing 30 algorithms including Bayan on an equal footing.

VI Technical Background for the Comparisons

Vi.1 partition similarity measure.

We quantify the similarity of a partition obtained by an algorithm to a desirable partition (e.g. a planted ground-truth partition) using adjusted mutual information [ 38 ] and normalize it symmetrically [ 52 ] . The normalized adjusted mutual information (AMI) is a measure of similarity of partitions which (unlike normalized mutual information [ 53 , 52 ] ) adjusts the measurement based on the similarity that two partitions may have by pure chance. AMI for a pair of identical partitions (or permutations of the same partition) equals 1. For two partitions which have no similarity beyond the similarity caused by random chance, AMI takes a small (positive or negative) value close to 0 [ 38 ] .

We use AMI because it is shown to be a reliable measure of partition similarity [ 38 , 54 ] , and avoid using Normalized Mutual Information (NMI) because, despite its common use [ 55 , 56 ] , several studies indicate that using it leads to incorrect assessments [ 38 , 57 , 54 , 58 ] and incorrect evaluation of competing algorithms [ 52 ] . Similar to the NMI, other popularly used measures of partition similarity (the Jaccard index, the Fowlkes-Mallows index, the adjusted Rand index, and the F measure) suffer from at least one form of undesirable bias [ 54 ] and therefore, we avoid using them.

VI.2 Generating structurally diverse benchmark networks

To evaluate the performance of different community detection algorithms, we use Lancichinetti-Fortunato-Radicchi (LFR) benchmark graphs [ 59 ] as well as Artificial Benchmarks for Community Detection (ABCD) graphs [ 60 ] . We generate 1000 synthetic graphs with randomized parameters described below to ensure that the differences observed in performance of the algorithms are not restricted for specific graph structures.

We generate LFR benchmarks based on the following randomized parameters: number of nodes ( n 𝑛 n italic_n ) randomly chosen from the range [ 20 , 300 ] 20 300 [20,300] [ 20 , 300 ] , maximum degree ⌊ 0.3 ⁢ n ⌋ 0.3 𝑛 \lfloor 0.3n\rfloor ⌊ 0.3 italic_n ⌋ , maximum community size ⌊ 0.5 ⁢ n ⌋ 0.5 𝑛 \lfloor 0.5n\rfloor ⌊ 0.5 italic_n ⌋ , power law exponent for the degree distribution τ 1 = 3 subscript 𝜏 1 3 \tau_{1}=3 italic_τ start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT = 3 , power law exponent for the community size distribution τ 2 = 1.5 subscript 𝜏 2 1.5 \tau_{2}=1.5 italic_τ start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT = 1.5 , and average degree of 4. The parameter μ 𝜇 \mu italic_μ (mixing parameter) is chosen from the set { 0.01 , 0.1 , 0.3 , 0.5 , 0.7 } 0.01 0.1 0.3 0.5 0.7 \{0.01,0.1,0.3,0.5,0.7\} { 0.01 , 0.1 , 0.3 , 0.5 , 0.7 } for five experiment settings (each with 100 LFR graphs).

subscript 𝑑 𝑚 𝑖 𝑛 1 𝑛 [d_{min}+1,n) [ italic_d start_POSTSUBSCRIPT italic_m italic_i italic_n end_POSTSUBSCRIPT + 1 , italic_n ) ; and power law exponents for the degree distribution and community size distribution randomly from ( 1 , 8 ) 1 8 (1,8) ( 1 , 8 ) and then rounded off to 2 decimal places. The parameter ξ 𝜉 \xi italic_ξ (mixing parameter) is chosen from the set { 0.1 , 0.3 , 0.5 , 0.7 , 0.9 } 0.1 0.3 0.5 0.7 0.9 \{0.1,0.3,0.5,0.7,0.9\} { 0.1 , 0.3 , 0.5 , 0.7 , 0.9 } for five experiment settings (each with 100 ABCD graphs). The mixing parameters μ 𝜇 \mu italic_μ and ξ 𝜉 \xi italic_ξ can be considered as indicators of the noise in the LFR and ABCD data generation process respectively.

VI.3 Partition quality measures

Retrieval tests based on LFR and ABCD benchmarks provide a level playing field for the community detection algorithms to be compared against each other in a method-agnostic way [ 59 , 60 ] . We also provide six partition quality measures for additional comparisons of the 30 CD algorithms without relying on the retrieval of planted partitions.

Comparing CD algorithms based on a single quality function that is used in some of them (e.g. description length or modularity) is suggested to be unfair and not rigorous [ 60 ] . Such an approach favors algorithms that were designed based on that specific measure and disfavor other CD algorithms. Given the disagreements on the suitability of partition quality measures [ 61 ] , we refrain from relying on a single measure and instead report all the following measures: description length [ 17 ] , modularity, average conductance [ 62 ] , coverage [ 63 ] , performance [ 63 ] , and well clusteredness [ 61 ] .

All these six partition quality measures are functions that take input graph G 𝐺 G italic_G and input partition P 𝑃 P italic_P and return a value as the output. For description length and average conductance, a lower value indicates a better partition. For the other four measures, a higher value indicates a better partition. Except description length and modularity, the other four partition quality measures return values in the unit interval. Well clusteredness returns a binary value. We briefly describe these six partition quality measures:

Description length : The description length of a dataset refers to the amount of information required to describe the data. According to the minimum description length principle, a model that can compress the data more effectively has captured more of its regularities and is therefore considered to have shown a better performance [ 64 ] .

To evaluate a partition P 𝑃 P italic_P of a graph G = ( V , E ) 𝐺 𝑉 𝐸 G=(V,E) italic_G = ( italic_V , italic_E ) using a Stochastic Block Model (SBM) [ 16 ] with parameters θ 𝜃 \theta italic_θ , the description length is calculated as:

Modularity : The modularity value Q ( G , X ) subscript 𝑄 𝐺 X Q_{(G,\textbf{X})} italic_Q start_POSTSUBSCRIPT ( italic_G , X ) end_POSTSUBSCRIPT for graph G 𝐺 G italic_G and partition P 𝑃 P italic_P (that corresponds to the partition matrix X ) is calculated based on Eq. ( 1 ).

Average conductance : The average conductance of partition P 𝑃 P italic_P and graph G 𝐺 G italic_G is the mean of conductance values over communities of partition P 𝑃 P italic_P . A value for conductance can be calculated for each community, i 𝑖 i italic_i , of partition P = { V 1 , V 2 , … , V k } 𝑃 subscript 𝑉 1 subscript 𝑉 2 … subscript 𝑉 𝑘 P=\{V_{1},V_{2},\dots,V_{k}\} italic_P = { italic_V start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT , italic_V start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT , … , italic_V start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT } and graph G 𝐺 G italic_G based on

where | E i | subscript 𝐸 𝑖 |E_{i}| | italic_E start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT | denotes the number of edges with one endpoint in community V i subscript 𝑉 𝑖 V_{i} italic_V start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT , d ⁢ ( V i ) 𝑑 subscript 𝑉 𝑖 d(V_{i}) italic_d ( italic_V start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) is the sum of degrees of nodes assigned to community V i subscript 𝑉 𝑖 V_{i} italic_V start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT , and d ⁢ ( V ∖ V i ) 𝑑 𝑉 subscript 𝑉 𝑖 d(V\setminus V_{i}) italic_d ( italic_V ∖ italic_V start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) is the sum of degrees of nodes not assigned to community V i subscript 𝑉 𝑖 V_{i} italic_V start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT .

Coverage : The coverage of partition P 𝑃 P italic_P is the ratio of the number of its intra-community edges to the total number of edges in graph G 𝐺 G italic_G .

Performance : The performance of partition P 𝑃 P italic_P is the total count of intra-community edges plus inter-community non-edges divided by n ⁢ ( n − 1 ) / 2 𝑛 𝑛 1 2 n(n-1)/2 italic_n ( italic_n - 1 ) / 2 . This denominator is the size of the complete graph that has n 𝑛 n italic_n nodes just like G 𝐺 G italic_G .

Well clusteredness : The well clusteredness is a binary measure based on the the three measures K ¯ inter subscript ¯ 𝐾 inter \bar{K}_{\text{inter}} over¯ start_ARG italic_K end_ARG start_POSTSUBSCRIPT inter end_POSTSUBSCRIPT , K 𝐾 K italic_K , and K ¯ intra subscript ¯ 𝐾 intra \bar{K}_{\text{intra}} over¯ start_ARG italic_K end_ARG start_POSTSUBSCRIPT intra end_POSTSUBSCRIPT proposed in [ 61 ] and defined as follows:

where k 𝑘 k italic_k is the number of communities in partition P 𝑃 P italic_P , V i subscript 𝑉 𝑖 V_{i} italic_V start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT denotes the i-th community in partition P 𝑃 P italic_P , | E i ⁢ j | subscript 𝐸 𝑖 𝑗 |E_{ij}| | italic_E start_POSTSUBSCRIPT italic_i italic_j end_POSTSUBSCRIPT | denotes the number of edges with one endpoint in community i 𝑖 i italic_i and one endpoint in community j 𝑗 j italic_j ;

where K ⁢ ( G ) 𝐾 𝐺 K(G) italic_K ( italic_G ) is the density of graph G 𝐺 G italic_G ; and

where K ⁢ ( V i ) 𝐾 subscript 𝑉 𝑖 K(V_{i}) italic_K ( italic_V start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) denotes the density of community V i subscript 𝑉 𝑖 V_{i} italic_V start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT .

The necessary condition for graph G 𝐺 G italic_G to be well clustered by partition P 𝑃 P italic_P is for the two inequalities K ¯ inter < K < K ¯ intra subscript ¯ 𝐾 inter 𝐾 subscript ¯ 𝐾 intra \bar{K}_{\text{inter}}<K<\bar{K}_{\text{intra}} over¯ start_ARG italic_K end_ARG start_POSTSUBSCRIPT inter end_POSTSUBSCRIPT < italic_K < over¯ start_ARG italic_K end_ARG start_POSTSUBSCRIPT intra end_POSTSUBSCRIPT to hold [ 61 ] . For any graph G 𝐺 G italic_G and partition P 𝑃 P italic_P , the binary measure, well clusteredness, takes 1 if graph G 𝐺 G italic_G is well clustered by partition P 𝑃 P italic_P , and it takes 0 otherwise.

VI.4 Comparing CD algorithms

There are different views on how CD algorithms can be assessed. The two major, and often opposing views, rely on theoretical argumentation vs. practical argumentation.

Some experts use a theoretical argumentation and suggest that when we generate networks using some generative process, like the LFR or ABCD benchmark, then provably the Bayes-optimal algorithm for inferring the planted communities is the one that simply inverts the generative process for inference. Therefore, without performing any comparisons, we know that Maximum A Posteriori estimation with a Degree-Corrected SBM with appropriate priors and mixing structure will perform the best for the LFR benchmark if an infinite number of trials are conducted and we use a suitable error measure for the performance (an ideal partition similarity measure). They argue that similar guarantees hold for other estimators and loss functions. This argument concludes that any distinction among algorithm performance is thus a finite sample size issue or because the error measure used is different (e.g. AMI or NMI).

Other experts use a practical argumentation and suggest that standard LFR and ABCD benchmarks are informative for comparing the capabilities of CD algorithms [ 59 , 60 ] . LFR and ABCD are standard and widely adopted benchmarks developed to serve this specific purpose of comparing the practical capabilities of CD algorithms in a controlled environment. In practical situations, appropriate priors and mixing structure cannot be simply assumed and an infinite number of trials cannot be performed. Therefore, the LFR and ABCD benchmarks provide valuable insights on the performance of CD algorithms that may violate theoretical expectations. Moreover, if we generate benchmarks and use the information on how they are generated (LFR/ABCD) to reach analytical results for supporting a specific algorithm, we would defeat the purpose of the benchmark models.

Our problem definition in Section I is aligned with the practical perspective rather than the theoretical perspective. Therefore, after acknowledging the merits and limitations of the theoretical perspective that suggests comparing CD algorithms is fruitless, we continue to compare 30 CD algorithms using standard LFR and ABCD benchmarks as well as six partition quality measures to assess their practical capabilities on structurally diverse benchmarks across different mixing parameter values. We briefly describe the motivations behind the development of several benchmark models for community detection to prepare the context for the interpretation of our results in Section VII .

The LFR benchmarks are developed with a timely observation on the part of its developers arguing that “many algorithms have been proposed [ … … \dots … ] the question of how good an algorithm is, with respect to others, is still open” [ 59 , pp 046110-1] . The LFR benchmark model attempt to address a methodological problem of crucial importance [ 65 , 66 ] : comparing the accuracy of CD methods. The LFR benchmark improved upon earlier benchmarks [ 67 ] which were preferential attachment networks of 128 nodes with fixed degrees and fixed communities sizes.

The development of the ABCD benchmarks was motivated by the necessity of comparing CD algorithms on synthetic graphs that resemble some key features of typical real-world networks like community structure and heterogeneous degrees and heterogeneous community sizes [ 60 ] . Algorithms should be compared based on networks with a varying strength of community structure which is operationalized through the ξ 𝜉 \xi italic_ξ mixing parameter. Emphasizing on the usefulness of the LFR benchmark model, ABCD builds upon the same foundation, but resolves three limitations of the LFR model [ 60 ] .

VI.5 CD algorithms included in our evaluations

Using LFR and ABCD as two different families of benchmarks, six partition quality measures, and four real networks from different contexts, we compare the following 30 CD algorithms: Bayan, eight modularity-based heuristics, other optimization-based algorithms, and CD methods which do not rely on modularity or optimization. The 29 algorithms compared to Bayan (in the chronological order of 1970-2023) are the CD methods known as Kernighan-Lin bisection [ 68 ] , greedy [ 31 ] , Chinese whispers [ 69 ] , Reichardt Bornholdt with Erdős-Rényi as the null model (RB) [ 70 ] , Walktrap [ 71 ] , k-cut [ 72 ] , asynchronous label propagation [ 73 ] , Louvain [ 32 ] , Infomap [ 14 ] , Reichardt Bornholdt with the configuration model as the null model (LN) [ 70 , 33 ] , Genetic Algorithm (GA) [ 74 ] , semi-synchronous label propagation [ 75 ] , CPM [ 76 ] , significant scales [ 77 ] , Weighted Community Clustering (WCC) [ 78 ] , Combo [ 25 ] , Belief [ 34 ] , Stochastic Block Model (SBM) (minimum description length) [ 16 ] , SBM with Markov Chain Monte Carlo (MCMC) [ 16 ] , Surprise [ 20 ] , Diffusion Entropy Reducer (DER) [ 79 ] , Paris [ 35 ] , Leiden [ 36 ] , EdMot [ 37 ] , GemSec [ 80 ] , Bayesian Planted Partition (BPP) [ 17 ] , BPP with MCMC [ 17 ] , Markov stability (PyGenStability 5 5 5 The Markov stability algorithm in the PyGenStability library produces multiple partitions at different scales for one input network [ 42 ] . We use two simple adaptations of it (MR and MV) to obtain one partition for each input network. These two adaptations involve running PyGenStability with its automated optimal scale selection [ 42 ] which returns multiple candidate partitions corresponding to different scales. In MV, we select the partition with the minimum normalized variance of information. In MR, we select a partition randomly. ) [ 42 ] with random partition selection (MR), and Markov stability [ 42 ] with minimum normalized variance of information (MV).

We use the public implementations of these 29 algorithms from the following Python libraries. For the two Markov stability algorithms (MR and MV), we use the PyGenStability library (version 0.2.2) [ 42 ] . For the four inferential methods (SBM, SM, BPP, and BM), we use the graph_tool library (version 2.57) [ 40 ] . For the two algorithms, Kernighan-Lin and asynchronous label propagation, we use the NetworkX library (version 3.1) [ 39 ] . For the remaining 21 algorithm, we use the Community Discovery library ( CDlib ) (version 0.2.6) [ 41 ] .

Three comparisons are provided on these 30 algorithms in Sections VII – IX .

VII Partition Retrieval Comparisons

This section provides the first of the three comparisons which assesses the 30 algorithms on the extent to which they retrieve planted partitions of LFR and ABCD networks.

VII.1 Comparison of 30 algorithms based on retrieving planted communities in LFR graphs

In our first retrieval comparison, we use the LFR benchmarks [ 59 ] introduced and parameterized earlier, and measure the performance of each method using the AMI of the partition with the planted partition from the LFR graph generation process.

In this evaluation, we use 500 LFR benchmark graphs in five experiment settings; each having 100 LFR graphs generated based on a specific μ 𝜇 \mu italic_μ value ( μ ∈ { 0.01 , 0.1 , 0.3 , 0.5 , 0.7 } 𝜇 0.01 0.1 0.3 0.5 0.7 \mu\in\{0.01,0.1,0.3,0.5,0.7\} italic_μ ∈ { 0.01 , 0.1 , 0.3 , 0.5 , 0.7 } ). The mixing parameter μ 𝜇 \mu italic_μ in the LFR model determines the fraction of inter-community edges. Larger values of μ 𝜇 \mu italic_μ complicate the accurate discovery of communities by decreasing the association between the structure and the planted communities.

Results on the average AMI of each algorithm in each experiment setting are provided in the appendix (Table LABEL:tab:lfr ). Figure  1 illustrates the ranking of the 30 algorithms, including Bayan, according to AMI averaged over 100 LFR graphs in each of the five experiment settings (five values of μ 𝜇 \mu italic_μ ). Among the 30 algorithms, Bayan is always among the three algorithms with the highest average AMIs. Bayan also has the most stable performance across the five values of μ 𝜇 \mu italic_μ . Walktrap and RB are two other algorithms demonstrating high performance; each of them achieves average AMI higher than Bayan’s on two out of five experiment settings. However, their performance ranking across the five values of μ 𝜇 \mu italic_μ is less stable than Bayan’s.

In Figure  1 , the two algorithms Paris and Combo seem to perform comparatively well for small values of μ 𝜇 \mu italic_μ , but their performance rankings decrease substantially when the μ 𝜇 \mu italic_μ mixing parameter passes the threshold value of 0.1 0.1 0.1 0.1 . Contrary to this pattern, there are algorithms like EdMot whose comparative performance improves when μ 𝜇 \mu italic_μ increases. Infomap and three modularity-based heuristics, Combo, LN, and Leiden, show a comparatively decent performance, having higher AMIs than most other methods. Our observations on the high performance of modularity-based methods on LFR graphs are aligned with the results on LFR graphs reported in [ 52 ] , where modularity-based methods return AMIs higher than asynchronous label propagation, walktrap, Bayesian planted partition, and sometimes higher than Infomap.

The descriptive AMI ranking results of the 30 algorithms in each experiment setting are validated using a Friedman test of multiple groups [ 81 ] followed by a post-hoc Li test of multiple hypotheses [ 82 ] . More information about these statistical procedures is provided in Section 2 of the SI. The AMI results on the 100 LFR graphs with μ = 0.01 𝜇 0.01 \mu=0.01 italic_μ = 0.01 with Bayan as the control method lead to the rejection of the null hypotheses in 19 out of 29 post-hoc Li tests. This suggests that for LFR graphs with μ = 0.01 𝜇 0.01 \mu=0.01 italic_μ = 0.01 , Bayan returns partitions with statistically significant higher similarity to the planted partition compared to each of those 19 other algorithms. For μ = 0.1 𝜇 0.1 \mu=0.1 italic_μ = 0.1 , the null hypotheses are rejected in 28 out of 29 post-hoc Li tests. The only exception is the Walktrap algorithm, for which there is insufficient evidence of difference from Bayan in AMI. This is partly due to the limitations in the statistical power of conducting a large number of tests among 30 algorithms while controlling the family-wise error rate to 0.05 0.05 0.05 0.05 [ 82 ] . Overall, the statistical results (in Table S1 in the SI) show that Bayan has a significantly higher AMI means in comparison to most of the 29 other algorithms considered confirming the descriptive results in Figure  1 (and Table LABEL:tab:lfr in the Appendix).

VII.2 Comparison of 30 algorithms based on retrieving planted communities in ABCD graphs

We conduct additional retrieval tests to ensure that the results are not artifacts of using LFR benchmarks. In our second retrieval comparison, we use the ABCD benchmarks [ 60 ] introduced and parameterized earlier, and compare Bayan to the same set of 29 other CD algorithms and rank them based on their average AMI with the planted partitions on ABCD benchmark graphs.

To evaluate the 30 algorithms based on retrieval of the planted communities, we use 500 ABCD benchmark graphs in five experiment settings; each having 100 ABCD graphs generated based on a specific ξ 𝜉 \xi italic_ξ value ( ξ ∈ { 0.1 , 0.3 , 0.5 , 0.7 , 0.9 } 𝜉 0.1 0.3 0.5 0.7 0.9 \xi\in\{0.1,0.3,0.5,0.7,0.9\} italic_ξ ∈ { 0.1 , 0.3 , 0.5 , 0.7 , 0.9 } ). The mixing parameter ξ ∈ [ 0 , 1 ] 𝜉 0 1 \xi\in[0,1] italic_ξ ∈ [ 0 , 1 ] determines the independence of the edge distribution from the communities [ 60 ] . At the extreme value of ξ = 0 𝜉 0 \xi=0 italic_ξ = 0 , all edges are within communities. In contrast, at the other extreme value, ξ = 1 𝜉 1 \xi=1 italic_ξ = 1 indicates that communities do no influence the distribution of edges [ 60 ] . Therefore, larger values of ξ 𝜉 \xi italic_ξ complicate the discovery of communities by decreasing the association between the structure and the planted communities.

Results on the average AMI of each algorithm in each experiment setting are provided in the appendix (Table LABEL:tab:abcd ). Figure  2 illustrates the comparative ranking of the algorithms, including Bayan, according to AMI values averaged over 100 ABCD graphs in each of the five experiment settings (five values of ξ 𝜉 \xi italic_ξ ). Bayan has the highest or the second highest average AMI in four out of five experiment settings. Among the 30 algorithms for ξ ∈ { 0.1 , 0.3 , 0.5 , 0.7 } 𝜉 0.1 0.3 0.5 0.7 \xi\in\{0.1,0.3,0.5,0.7\} italic_ξ ∈ { 0.1 , 0.3 , 0.5 , 0.7 } , Bayan and Combo are consistently in the top three algorithms with the highest average AMIs. Setting aside the high-noise experiment setting of ξ = 0.9 𝜉 0.9 \xi=0.9 italic_ξ = 0.9 where AMIs substantially drop across the board, Bayan and Combo have the most stable performance in accurate retrieval of the planted partitions of these ABCD graphs.

In Figure  2 , the three algorithms walktrap, LN, and Leiden seem to perform comparatively well especially for small values of ξ 𝜉 \xi italic_ξ . Contrary to this pattern, there are algorithms like EdMot and surprise whose comparative performance monotonically improves when ξ 𝜉 \xi italic_ξ increases. Averaging the AMI values for all 500 ABCD graphs, Bayan has the highest total average AMI followed by Combo and Leiden respectively. Note that these three high-performing algorithms are all based on modularity while Bayan differs from the others in having optimality guarantees.

Similar to the rankings on LFR graphs, the descriptive ranking results on ABCD graphs are validated using a Friedman test of multiple groups [ 81 ] followed by a post-hoc Li test of multiple hypotheses [ 82 ] . The AMI results on the 100 ABCD graphs with ξ = 0.1 𝜉 0.1 \xi=0.1 italic_ξ = 0.1 with Bayan as the control method lead to the rejection of the null hypotheses in 19 out of 29 post-hoc Li tests. This suggests that for ABCD graphs with ξ = 0.1 𝜉 0.1 \xi=0.1 italic_ξ = 0.1 , Bayan statistically significantly differs from each of the 19 other algorithms in retrieving the ground truth partition. The exceptions are ten algorithms for which there is insufficient evidence of statistically significant difference from Bayan in AMI. Detailed statistical test results on ABCD graphs are provided in the SI (Table S2) confirming the results in Figure  2 (and Table LABEL:tab:abcd in the Appendix).

Take together with the results on LFR graphs, maximum-modularity partitions are shown to have a distinctive accuracy in retrieving planted partitions across a wide range of parameter settings for both standard CD benchmark models. Our results in Figures  1 – 2 (and Tables LABEL:tab:lfr – LABEL:tab:abcd ) show the major differences between the extent to which these 30 algorithms retrieve planted partitions in practice where the sample size is not infinite.

Designed as a specialized algorithm for solving an NP-hard problem in small networks (with up to 3000 edges), Bayan is not suitable for and does not scale to large-scale networks. Figures 1 – 2 also provide insight on algorithms other than Bayan that have reasonably good performance on both LFR and ABCD assessments. At the low extreme of performance ranks, there are several algorithms whose capability of retrieving ground-truth communities is not better than that of the Kernighan-Lin bisection algorithm from 1970. Note that for comparing all these 30 algorithms, including several algorithms that do not (and cannot possibly) scale to large instances, we could not include large-scale benchmark networks in our assessments. Given this limitation, our results are safer to be interpreted within the context of the comparative performance of 30 algorithms on small networks with up to 3000 edges. Moreover, from a theoretical standpoint, the finite sample size prevents us from making a firm determination about how these algorithms compare asymptotically.

VII.3 Comparison of 30 algorithms based on similarity to node attributes of fairly modular real networks

We also assess the similarity between the partitions of the same 30 algorithms and a set of node metadata (discrete-valued node attributes) on five real benchmark networks which are commonly used [ 83 , 84 , 85 , 28 , 86 , 87 , 37 , 88 ] in the literature for demonstrating the output of CD algorithms. Retrieving node label communities is not the purpose of CD algorithms, and network formation may poorly correlate with any arbitrary chosen node attribute [ 43 ] . Therefore, we do not consider a given set of node metadata as ground truth. However, it is useful to compare the partitions returned by different algorithms based on their similarity with node metadata [ 84 , 85 ] to evaluate them in a setting without synthetic benchmarks on networks where node labels are aligned with the structure. Consistent with the literature [ 37 , 87 , 83 , 89 ] , we use the five real networks commonly referred to as dolphins , football , karate , polbooks , and risk_game which all have node attributes. Information on accessing all networks are in Section 4 of the SI.

Figure  3 shows the AMI of the partitions from each of the 30 algorithms and the node attributes of the networks. As the node attribute considered is at most one factor among a multitude of factors determining the formation of these networks, the AMI values confound several effects and cannot be reliably interpreted as a performance measure of the algorithms [ 43 ] . They simultaneously measure the metadata’s relevance to the structure and the performance of the algorithms in retrieving communities corresponding to the structure. Bearing these limitations in mind, the results indicate that some algorithms including Bayan return partitions with reasonably high similarity to the node attributes for all five networks, whereas, other algorithms like CPM, k-cut, and SBM return partitions with a less straightforward correspondence to the node metadata. Some algorithms like walktrap, which comparatively had good performance on LFR and ABCD graphs, return some partitions with low similarity to node attributes in this assessment. A No-Free-Lunch theorem for CD [ 43 ] implies that no single method can consistently outperform others in accurately retrieving the possible node attributes of real networks. Maximum-modularity partitions are (happen to be) reasonably similar to the node attributes for these networks.

So far, we have discussed the advantage of maximum-modularity partitions in retrieving planted communities in LFR and ABCD graphs, and discovering partitions with strong associations with node attributes in some commonly used real networks. Next, we report six comparisons of the 30 algorithms based on partition quality measures which do not depend on partition similarity measures.

VIII Partition Quality Comparisons

This section provides the second comparison out of the three comparisons of the 30 CD algorithms. Here, we assess the algorithms based on six partition quality measures on the same LFR and ABCD networks.

We compute and report the six partition quality measures (defined in Subsection VI.3 ) for the partitions produced by the 30 30 30 30 algorithms on the 500 500 500 500 LFR networks and the 500 500 500 500 ABCD networks in Figures 4 – 9 . The algorithms with the most desirable median value are shown in the left-most positions in Figures 4 – 9 .

Figure 4 illustrates a box plot for the 500 description length values of each algorithm separately for LFR networks and ABCD networks. Bayan, Louvain, and Leiden have the best (lowest) median values of description length among the 30 algorithms, respectively, for both the LFR and the ABCD instances. Unlike the inferential methods, these three modularity-based algorithms are not designed to minimize the description length. However, they produce partitions with a lower median description length compared to the four inferential algorithms SBM, SM, BPP, and BM. This paradoxical result highlights the importance of a practical comparison of algorithms. Their theoretical motivations seems to be unreliable for choosing algorithms because they may not materialize in practice as illustrated for the inferential algorithms SBM, SM, BPP, and BM in Fig.  4 .

Figure 5 illustrates a box plot for the 500 modularity values of each algorithm separately for LFR networks and ABCD networks. As expected Bayan has the best median value of modularity among the 30 algorithms for both the LFR and the ABCD instances. We do not consider this comparison as a fair assessment and only provide it for completeness. Using any single partition quality measure for choosing a CD algorithm is contestable. Moreover, modularity is not a suitable partition quality measure 6 6 6 There is a distinction between a quality measure (a score function) and an objective function (loss function). [ 61 ] .

Figure 6 illustrates a box plot for the 500 average conductance values of each algorithm separately for LFR networks and ABCD networks. Similarly, the distributions of coverage values are provided in Figure 7 and the distributions of performance values are shown in Figure 8 .

Bayan, Infomap, and SBM have the best median values of average conductance respectively on the LFR networks in Figure 6 . The same three algorithms also have the best median values for coverage and performance on LFR networks as shown in Figures 7 – 8 . On ABCD instances, Bayan, Louvain, and Leiden have the best median values of average conductance, respectively. The same three algorithms also have the best median values for coverage and performance on ABCD networks as shown in Figures 7 – 8 .

The results for well clusteredness are reported slightly differently in Figure 9 . Given that well clusteredness is a binary value, we report for each algorithm the percentage of LFR graphs that are well clustered and separately report the similar percentage for ABCD graphs in Figure 9 . The majority of the 30 algorithms including Bayan produce well clustered partitions on all 100 % percent 100 100\% 100 % of LFR networks. For ABCD networks, there are 14 algorithms including Bayan that produce well clustered partitions on all 100 % percent 100 100\% 100 % instances. For both LFR and ABCD networks, the four inferential algorithms, SBM, SM, BPP, and BM, produce partitions that are not well clustered, more often than not. The two algorithms CPM and kcut never produce well clustered partitions on either LFR or ABCD networks.

In this section, we compared the 30 algorithms based on partition quality measures which do not depend on the planted (ground-truth) partitions. Next, we focus on how the algorithms compare from a run time perspective.

IX Run Time Comparisons

This section provides the last of the three comparisons for the 30 CD algorithms which assesses them based on their run times. We also include two alternative exact modularity maximization methods in Subsection IX.2 . These run time analyses are conducted in Python 3.9 using a notebook computer with an Intel Core i7-11800H @ 2.30GHz CPU and 64 GBs of RAM running Windows 10.

IX.1 Comparison of 30 algorithms based on empirical run time

1 𝑒 3 1e+3 1 italic_e + 3 , with larger networks typically taking longer time. For most algorithms except Infomap, we observe a clear increase in run time as the number of edges goes up. The algorithms Bayan, GA, GemSec, and Belief, are the slowest algorithms on the LFR networks. There are many instances for which Bayan has the longest run time.

1 𝑒 4 1e+4 1 italic_e + 4 for the ABCD instances (which are on average large networks than our LFR instances). Except Infomap, we observe a clear increase in run time as the number of edges goes up. The four algorithms Bayan, GA, GemSec, and Belief, are the slowest algorithms on the ABCD networks as well. There is difference of several orders of magnitude between the run times of some of these CD algorithms on the same network instances.

Next, we focus on the efficiency of Bayan and two alternative exact approaches for obtaining maximum-modularity partitions.

IX.2 Comparison of three approaches for exact modularity maximization based on time and optimality

In this subsection, we compare Bayan with two alternative approaches for exact modularity maximization based on run time and highest modularity found within a maximum limited time.

The first alternative approach is using a function 7 7 7 https://igraph.org/python/doc/api/igraph.Graph.html from the igraph library [ 90 ] (IG for short) 8 8 8 The IG algorithm has not been explicitly proposed as a method for CD, but as a complementary tool in the igraph library [ 90 ] . . IG calls the open-source solver, GNU Linear Programming Kit (GLPK), to solve an IP formulation [ 29 ] of the modularity maximization problem and returns an optimal partition when/if the optimization problem is solved.

The second alternative approach is solving the sparse IP formulation of the modularity maximization problem [ 27 ] from Eq. ( 2 ) using the commercial solver Gurobi [ 48 ] . Recent performance assessments from March 2024 show Gurobi to be one of the fastest mathematical solvers for IP models [ 91 ] . This sets a high performance baseline to compare Bayan against. Out-of-the-box Gurobi IP has been used in [ 5 ] to solve Eq. ( 2 ) and was shown to be feasible for networks with up to 2812 edges, given relatively long computation time.

To compare IG, Gurobi IP, and Bayan, we consider 94 structurally diverse networks including real networks from different contexts and random graphs. These 94 instances includes 74 real networks with no more than 8405 edges as well as 10 Erdős-Rényi graphs and 10 Barabási-Albert graphs 9 9 9 These 94 networks are loaded as simple undirected unweighted graphs. Additional details and information on accessing these 94 networks are provided in the SI. . For each of these 94 instances, we use Bayan, Gurobi IP, and IG with a time limit of 4 hours and compare their empirical run times and objective function values (highest modularity found at termination).

There are ten instances for which none of the three methods finds a guaranteed optimal partition within the time limit of 4 hours (see Table S3 in the SI). For these ten instances, Bayan returns a feasible partition with a higher modularity ( 49.4 % percent 49.4 49.4\% 49.4 % higher on average) compared to the feasible partition from Gurobi IP at the time limit 10 10 10 Difference in modularity values are reported not as a CD score/quality function, but to compare the objective function values of Bayan and Gurobi IP on the challenging instances. .

Among the remaining 84 instances, Gurobi IP and IG fail to converge within the time limit respectively on six and 23 others instances respectively. However, all those 84 instances are solved to global optimality by Bayan (detailed results are provided in Tables S4, S5, and S6 in the SI). The six networks adjnoun , london_transport , copenhagen , macaques , malaria_genes , and celegans_2019 11 11 11 See the network repository Netzschleuder for more information on the networks. cannot be solved by Gurobi IP or IG within the time limit. To our knowledge, the guaranteed maximum-modularity partitions for these six networks have not been previously determined [ 26 , 92 , 93 , 27 , 8 , 28 , 5 ] .

On these 84 instances, the average run times of Bayan, Gurobi IP, and, IG are 295.08, 1110.60, and 4588.52 seconds respectively. This implies that on average, Bayan is 815.52 seconds per instance (or over 3.7 times) faster than the Gurobi IP, and 4289.15 seconds per instance (or over 15.5 times) faster than the IG on these 84 instances. Both of these run time comparisons are conservative because Bayan solves all these 84 instances to global optimality while Gurobi IP and IG fail to terminate within the time limit for six and 23 networks respectively. On all these failed cases, we have conservatively considered 4 hours as the run time for Gurobi IP and IG while the actual run time may be substantially higher. Therefore, the actual performance comparison would be even more favourable to Bayan. The complete results on run times and modularity values of the three exact methods are provided in the SI (see Tables S3-S6).

Overall, these results indicate that Bayan is considerably faster than IG and Gurobi IP for most of the networks considered. The run time advantage of Bayan makes a practical difference on the real network instances and especially the six challenging instances noted earlier which are solvable by Bayan but not solvable by IG or Gurobi IP (or any other exact method to the best of our knowledge).

X Discussion and Future Directions

There are two fundamental questions to be answered regarding the Bayan algorithm: (1) How suitable is Bayan for maximizing modularity? (2) How suitable is Bayan for community detection?

For the first question, Fig. 5 provides some answers. For more conclusive answers about global maximization of modularity, one can also refer to another study [ 49 ] , where we have compared ten modularity-based methods based on the extent to which they globally maximized modularity. This included Bayan, eight modularity-based heuristics and a graph neural network algorithm [ 88 ] . Using real and synthetic networks with fairly modular structure, we showed the following: At the cost of longer computation time, Bayan has the advantage of reaching global optimality at higher rates and returning partitions more similar to the globally optimal partitions, compared to the other 9 modularity maximization algorithms. Bayan was followed by the Combo algorithm as the heuristic method demonstrating the most promising performance in returning partitions that were optimal or were similar to an optimal partition.

The results provided in Sections VII – VIII allow us to answer the second question from a practical standpoint. The results in Subsections VII.1 – VII.2 demonstrate the comparative suitability of Bayan based on retrieving planted partitions of LFR and ABCD benchmarks. Bayan was observed to be among the top algorithms in retrieving planted partitions across different mixing parameters. The results in Sections VII.3 show that, for networks where node labels are aligned with the structure, Bayan retrieves partitions that are similar with node labels. Overall, the results in Section VII demonstrate the suitability of Bayan as a community detection method for networks with up to 3000 edges. Our results in Section VIII show Bayan’s competitive advantages in comparison with 29 other methods based on five partition quality measures other than modularity: description length, average conductance, coverage, performance, and well clusteredness. In what follows, we discuss five key insights from our results.

Global modularity maximization retrieve planted partitions at rates higher than other existing algorithms

The results provided in Section VII indicate the practical relevance of maximum-modularity partitions in comparison with 29 other alternatives for CD. Despite the well-document theoretical flaws of modularity [ 11 ] , the high accuracy and stability of globally maximum-modularity partitions (shown in this study) are not challenged by other existing methods for community detection.

In modularity optimization, guaranteed closeness to optimality matters.

The results from Figures 1 – 2 and Figures 4 – 9 offer additional insights when we focus on the performance of the nine algorithms that attempt to maximize modularity. The comparative performance of nine modularity-based algorithms (Bayan, greedy, Louvain, LN, Combo, Belief, Paris, Leiden, and EdMot) shows the practical benefits of global optimization in the context of using modularity for CD. The practical benefit of global optimization is in both achieving better performance in retrieving planted communities and achieving better partition quality measures (other than modularity). The key lesson learned is that in the context of community detection through modularity optimization, guaranteed closeness to optimality matters. This crucial, yet often overlooked [ 4 ] , lesson was foreshadowed in [ 25 , pp. 012811-5] which reads “to stress the importance of looking for even the minor gains in the modularity score, […] relatively small changes in this partition quality function can be reflected by macroscopic variation of the communities involved”.

Exact modularity maximization is within reach for small networks, but requires substantially longer computation.

The scatter plots provided in Figures 10 – 11 demonstrate the substantial differences between the run times of algorithms. As expected and being an exact method, Bayan takes considerably longer than most heuristic methods. However, it is, on average, over 15.5 times faster than using the open-source IP solver, GLPK, and over 3.7 times faster than using the commercial solver, Gurobi, for modularity maximization. Also, we reiterate that Bayan (as well as any attempt at solving an NP-hard problem exactly) does not scale to large instances and suffers from asymptotic worst-case running times that are far from ideal. The NP-hardness of the problem implies that efficient running times of scalable heuristics (like Leiden) cannot be beaten by developing an exact method for solving it; scaling to large networks has not been a purpose of this study but the topic of a tempting and recurring questions. Having said that, exact and approximate optimization has provided more accurate and reliable solutions to increasingly larger instances of many similar NP-hard graph partitioning problems [ 94 , 95 , 96 , 97 , 98 ] and modularity maximization is not an exception. Using decades-old heuristics (including methods that were groundbreaking for their time) is not justified for small networks and come at the cost of lower performance.

Bayan’s mathematically rigorous operationalization of modularity maximization is a reliable choice for CD in small networks with up to 3000 edges.

While it is tempting to interpret our results as suggesting modularity is a better objective function than the objective functions of other optimization-based algorithms considered, we refrain from drawing such a conclusion because our comparative results of algorithms in Figures 1 – 2 and Figures 4 – 9 are confounded by the difference in the objective functions and the difference between mathematically rigorous optimization vs. local/greedy/heuristic optimization. We simply recommend using mathematically rigorous optimization in optimization-based tasks for small input. Our results justify the exact optimization approach for modularity where optimality matters [ 25 ] and sub-optimality has a disproportionate cost [ 5 ] . Future research may investigate the potential advantages of using global optimization and guaranteed approximations for other objective functions (e.g., Markov stability [ 42 ] , description length [ 16 ] , modularity density [ 21 ] , surprise [ 20 , 22 ] , or a new objective function inspired by the map equation [ 14 ] ) for CD. To the best of our knowledge, exact optimization of these alternative objectives are underexplored, and therefore each has the potential to outperform maximum-modularity partitions (and in turn outperform most other algorithms considered in this study) in retrieval tests and partition quality measures. We hope that our publicly available data and algorithm facilitate these prospective advances in the field. As a specialized algorithm [ 43 ] for accurate CD in small networks, Bayan maximizes modularity in networks with up to 3000 edges (in their largest connected component) and approximates maximum modularity in slightly larger instances on ordinary computers. Prospective advances in IP solvers (like Gurobi which is used in Bayan and is actively improved) pushes this limit further. Exact maximization of modularity for larger networks may require a substantially longer time or high performance computing resources. For slightly larger networks on an ordinary computer, one may run Bayan with a desired optimality gap tolerance (e.g. 0.1 0.1 0.1 0.1 ) or a desired time limit so that it returns a partition with a guaranteed proximity to the maximum modularity.

Bayan contributes new computational capabilities of both methodological and empirical relevance.

On the methodological side, the contributions of Bayan is threefold. (1) Bayan offers a principled way of quantifying the optimality of current and future modularity-based heuristics for CD. (2) Bayan demonstrates the advantages of a mathematically rigorous implementation of a long-lasting yet paradoxically underexplored optimization idea. (3) Bayan reaffirms that the practical relevance of modularity as an objective function, despite its theoretical flaws [ 11 ] , is yet to be challenged by a practical method that is more accurate and stable. On the empirical side, Bayan tackles a practical task in network science for small input, thereby improving upon open-access computational capabilities for a narrow but relevant set of tasks in networked systems.

Data and materials availability

A Python implementation of the Bayan algorithm ( bayanpy ) is publicly available through the package installer for Python (pip) . All network data used in the experiments and evaluations of the Bayan algorithm are available in a FigShare data repository [ 99 ] .

This study has been supported by the Data Sciences Institute at the University of Toronto.

CRediT Author Contribution Statement

Conceptualization (SA); data curation (SA, HC); formal analysis (SA, MM); funding acquisition (SA); investigation (SA, MM); methodology (SA, MM); project administration (SA); resources (SA, MM, HC); software (SA, MM, HC); supervision (SA, MM); validation (SA, MM, HC); visualization (MM); writing - original draft preparation (SA, MM); writing - review & editing (SA, MM, HC).

Acknowledgements

Authors acknowledge Sanchaai Mathiyarasan for technical assistance and Giulio Rossetti, Rémy Cazabet, Pawel Pralat, and Tiago P. Peixoto for helpful discussions.

• Schaub  et al. [2017] M. T. Schaub, J.-C. Delvenne, M. Rosvall, and R. Lambiotte, Applied Network Science  2 , 1 (2017).
• Fortunato and Newman [2022] S. Fortunato and M. E. J. Newman, Nature Physics  18 , 848 (2022).
• Newman [2006] M. E. J. Newman,  Proceedings of the National Academy of Sciences  103 , 8577 (2006) .
• Kosowski  et al. [2020] A. Kosowski, D. Saulpic, F. Mallmann-Trenn, and V. P. Cohen-addad, in  Advances in Neural Information Processing Systems 33 (NeurIPS’20) , edited by H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin (2020).
• Aref  et al. [2023a] S. Aref, M. Mostajabdaveh, and H. Chheda, in  Computational Science – ICCS 2023 , edited by J. Mikyška, C. de Mulatier, M. Paszynski, V. V. Krzhizhanovskaya, J. J. Dongarra, and P. M. Sloot (Springer Nature Switzerland, Cham, 2023) pp. 612–626,  https://doi.org/10.1007/978-3-031-36027-5_48 .
• Kawamoto and Kabashima [2019] T. Kawamoto and Y. Kabashima, Physical Review E  99 , 010301(R) (2019).
• Good  et al. [2010] B. H. Good, Y.-A. deMontjoye, and A. Clauset, Physical Review E  81 , 046106 (2010).
• Dinh  et al. [2015] T. N. Dinh, X. Li, and M. T. Thai, in  2015 IEEE International Conference on Data Mining  (2015) pp. 101–110, iSSN: 1550-4786.
• Newman [2016] M. E. J. Newman,  Physical Review E  94 , 052315 (2016) .
• Fortunato and Hric [2016] S. Fortunato and D. Hric,  Physics Reports  659 , 1 (2016) .
• Peixoto [2023] T. P. Peixoto, in  Elements in the Structure and Dynamics of Complex Networks  (Cambridge University Press, 2023).
• Fortunato and Barthélemy [2007] S. Fortunato and M. Barthélemy, Proceedings of the National Academy of Sciences  104 , 36 (2007).
• Rosvall and Bergstrom [2007] M. Rosvall and C. T. Bergstrom,  Proceedings of the National Academy of Sciences  104 , 7327 (2007) .
• Rosvall and Bergstrom [2008] M. Rosvall and C. T. Bergstrom,  Proceedings of the National Academy of Sciences  105 , 1118 (2008) .
• Karrer and Newman [2011] B. Karrer and M. E. J. Newman, Physical Review E  83 , 016107 (2011).
• Peixoto [2014a] T. P. Peixoto, Physical Review E  89 , 012804 (2014a).
• Zhang and Peixoto [2020] L. Zhang and T. P. Peixoto,  Physical Review Research  2 , 043271 (2020) .
• Liu  et al. [2021] X. Liu, B. Yang, H. Chen, K. Musial, H. Chen, Y. Li, and W. Zuo, ACM Transactions on Knowledge Discovery from Data (TKDD)  15 , 1 (2021).
• Serrano and Vidal [2021] B. Serrano and T. Vidal, arXiv preprint arXiv:2101.12336  (2021).
• Traag  et al. [2015] V. A. Traag, R. Aldecoa, and J.-C. Delvenne, Physical Review E  92 , 022816 (2015).
• Sato and Izunaga [2019] K. Sato and Y. Izunaga,  Computers & Operations Research  106 , 236 (2019) .
• Marchese  et al. [2022] E. Marchese, G. Caldarelli, and T. Squartini, Communications Physics  5 , 1 (2022).
• Paul and Dutta [2022] A. Paul and A. Dutta,  Expert Systems with Applications  206 , 117794 (2022) .
• Liu  et al. [2023] H. Liu, J. Wei, and T. Xu,  Expert Systems with Applications  231 , 120748 (2023) .
• Sobolevsky  et al. [2014] S. Sobolevsky, R. Campari, A. Belyi, and C. Ratti, Physical Review E  90 , 012811 (2014).
• Aloise  et al. [2010] D. Aloise, S. Cafieri, G. Caporossi, P. Hansen, S. Perron, and L. Liberti,  Physical Review E  82 , 046112 (2010) .
• Dinh and Thai [2015] T. N. Dinh and M. T. Thai, Internet Mathematics  11 , 181 (2015).
• Sobolevsky  et al. [2017] S. Sobolevsky, A. Belyi, and C. Ratti, Optimality of community structure in complex networks (2017), arXiv preprint arXiv:1712.05110.
• Brandes  et al. [2007] U. Brandes, D. Delling, M. Gaertler, R. Gorke, M. Hoefer, Z. Nikoloski, and D. Wagner, IEEE Transactions on Knowledge and Data Engineering  20 , 172 (2007).
• Zhao  et al. [2021] X. Zhao, J. Liang, and J. Wang, Information Sciences  551 , 358 (2021).
• Clauset  et al. [2004] A. Clauset, M. E. J. Newman, and C. Moore, Physical Review E  70 , 066111 (2004).
• Blondel  et al. [2008] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre,  Journal of Statistical Mechanics: Theory and Experiment  2008 , P10008 (2008) .
• Leicht and Newman [2008] E. A. Leicht and M. E. J. Newman,  Physical Review Letters  100 , 118703 (2008) .
• Zhang and Moore [2014] P. Zhang and C. Moore, Proceedings of the National Academy of Sciences  111 , 18144 (2014).
• Bonald  et al. [2018] T. Bonald, B. Charpentier, A. Galland, and A. Hollocou, in  MLG 2018 - 14th International Workshop on Mining and Learning with Graphs  (London, UK, 2018).
• Traag  et al. [2019] V. A. Traag, L. Waltman, and N. J. van Eck, Scientific Reports  9 ,  10.1038/s41598-019-41695-z (2019).
• Li  et al. [2019] P.-Z. Li, L. Huang, C.-D. Wang, and J.-H. Lai, in  Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining  (2019) pp. 479–487.
• Vinh  et al. [2010] N. X. Vinh, J. Epps, and J. Bailey,  Journal of Machine Learning Research  11 , 2837 (2010) .
• Hagberg  et al. [2008] A. A. Hagberg, D. A. Schult, and P. J. Swart, in  Proceedings of the 7th Python in Science Conference , edited by G. Varoquaux, T. Vaught, and J. Millman (Pasadena, CA USA, 2008) pp. 11 – 15.
• Peixoto [2014b] T. P. Peixoto, FigShare  10.6084/m9.figshare.1164194 (2014b),  https://doi.org/10.6084/m9.figshare.1164194 .
• Rossetti  et al. [2019] G. Rossetti, L. Milli, and R. Cazabet, Applied Network Science  4 , 1 (2019).
• Arnaudon  et al. [2023] A. Arnaudon, D. J. Schindler, R. L. Peach, A. Gosztolai, M. Hodges, M. T. Schaub, and M. Barahona, PyGenStability: Multiscale community detection with generalized Markov Stability (2023), arXiv:2303.05385.
• Peel  et al. [2017] L. Peel, D. B. Larremore, and A. Clauset, Science Advances  3 , e1602548 (2017).
• Christensen  et al. [2024] A. P. Christensen, L. E. Garrido, K. Guerra-Peña, and H. Golino, Behavior Research Methods  56 , 1485 (2024).
• Brusco  et al. [2023] M. J. Brusco, D. Steinley, and A. L. Watts, Behavior Research Methods  55 , 3549 (2023).
• Lancichinetti and Fortunato [2011] A. Lancichinetti and S. Fortunato,  Physical Review E  84 , 066122 (2011) .
• Agarwal and Kempe [2008] G. Agarwal and D. Kempe,  The European Physical Journal B  66 , 409 (2008) .
• Gurobi Optimization Inc. [2023] Gurobi Optimization Inc., Gurobi optimizer reference manual (2023), url: https://gurobi.com/documentation/10.0/refman/index.html date accessed 16 Feb 2023.
• Aref and Mostajabdaveh [2024] S. Aref and M. Mostajabdaveh,  Journal of Computational Science  78 , 102283 (2024) .
• Arenas  et al. [2007] A. Arenas, J. Duch, A. Fernández, and S. Gómez, New Journal of Physics  9 , 176 (2007).
• Lorena  et al. [2019] L. H. N. Lorena, M. G. Quiles, and L. A. N. Lorena, in  International Conference on Computational Science and Its Applications  (Springer, 2019) pp. 757–769.
• Jerdee  et al. [2023] M. Jerdee, A. Kirkley, and M. E. J. Newman, arXiv preprint arXiv:2307.01282  (2023).
• Danon  et al. [2005] L. Danon, A. Diaz-Guilera, J. Duch, and A. Arenas, Journal of Statistical Mechanics: Theory and Experiment  2005 , P09008 (2005).
• Gates  et al. [2019] A. J. Gates, I. B. Wood, W. P. Hetrick, and Y.-Y. Ahn, Scientific Reports  9 , 8574 (2019).
• Roozbahani  et al. [2023] Z. Roozbahani, J. Rezaeenour, and A. Katanforoush, Journal of Computational Science  67 , 101962 (2023).
• Singh  et al. [2022] D. K. Singh, S. Nandi, T. Chakraborty, and P. Choudhury, Journal of Computational Science  61 , 101634 (2022).
• Newman  et al. [2020] M. E. J. Newman, G. T. Cantwell, and J.-G. Young, Physical Review E  101 , 042304 (2020).
• Mahmoudi and Jemielniak [2024] A. Mahmoudi and D. Jemielniak, Scientific Reports  14 , 9021 (2024).
• Lancichinetti  et al. [2008] A. Lancichinetti, S. Fortunato, and F. Radicchi,  Physical Review E  78 , 046110 (2008) .
• Kamiński  et al. [2021] B. Kamiński, P. Prałat, and F. Théberge,  Network Science  9 , 153 (2021) .
• Miasnikof  et al. [2020] P. Miasnikof, A. Y. Shestopaloff, A. J. Bonner, Y. Lawryshyn, and P. M. Pardalos, Journal of Complex Networks  8 , 1 (2020).
• Kannan  et al. [2004] R. Kannan, S. Vempala, and A. Vetta, Journal of the ACM (JACM)  51 , 497 (2004).
• Fortunato [2010] S. Fortunato, Physics reports  486 , 75 (2010).
• Hansen and Yu [2001] M. H. Hansen and B. Yu, Journal of the american statistical association  96 , 746 (2001).
• Staudt  et al. [2017] C. L. Staudt, M. Hamann, A. Gutfraind, I. Safro, and H. Meyerhenke, Applied Network Science  2 , 1 (2017).
• Slota  et al. [2019] G. M. Slota, J. W. Berry, S. D. Hammond, S. L. Olivier, C. A. Phillips, and S. Rajamanickam, in  Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis , SC ’19 (Association for Computing Machinery, New York, NY, USA, 2019).
• Girvan and Newman [2002] M. Girvan and M. E. J. Newman,  Proceedings of the National Academy of Sciences  99 , 7821 (2002) ,  https://www.pnas.org/doi/pdf/10.1073/pnas.122653799 .
• Kernighan and Lin [1970] B. W. Kernighan and S. Lin, The Bell System Technical Journal  49 , 291 (1970).
• Biemann [2006] C. Biemann, in  Proceedings of the First Workshop on Graph Based Methods for Natural Language Processing , TextGraphs-1 (Association for Computational Linguistics, USA, 2006) pp. 73–80.
• Reichardt and Bornholdt [2006] J. Reichardt and S. Bornholdt,  Physical Review E  74 , 016110 (2006) .
• Pons and Latapy [2006] P. Pons and M. Latapy, Journal of Graph Algorithms and Applications  10 , 191 (2006).
• Ruan and Zhang [2007] J. Ruan and W. Zhang, in  Seventh IEEE international conference on data mining (ICDM 2007)  (IEEE, 2007) pp. 643–648.
• Raghavan  et al. [2007] U. N. Raghavan, R. Albert, and S. Kumara,  Physical Review E  76 , 036106 (2007) .
• Pizzuti [2008] C. Pizzuti, in  Proceedings of the 10th International Conference on Parallel Problem Solving from Nature — PPSN X - Volume 5199  (Springer-Verlag, Berlin, Heidelberg, 2008) pp. 1081–1090.
• Cordasco and Gargano [2010] G. Cordasco and L. Gargano, in  2010 IEEE international workshop on: business applications of social network analysis (BASNA)  (IEEE, 2010) pp. 1–8.
• Traag  et al. [2011] V. A. Traag, P. Van Dooren, and Y. Nesterov, Physical Review E  84 , 016114 (2011).
• Traag  et al. [2013] V. A. Traag, G. Krings, and P. Van Dooren, Scientific Reports  3 , 1 (2013).
• Prat-Pérez  et al. [2014] A. Prat-Pérez, D. Dominguez-Sal, and J.-L. Larriba-Pey, in  Proceedings of the 23rd international conference on World wide web  (2014) pp. 225–236.
• Kozdoba and Mannor [2015] M. Kozdoba and S. Mannor, Advances in Neural Information Processing Systems  28 (2015).
• Rozemberczki  et al. [2019] B. Rozemberczki, R. Davies, R. Sarkar, and C. Sutton, in  Proceedings of the 2019 IEEE/ACM international conference on advances in social networks analysis and mining  (2019) pp. 65–72.
• Friedman [1937] M. Friedman, Journal of the American Statistical Association  32 , 675 (1937).
• Li [2008] J. D. Li, Journal of Statistical Planning and Inference  138 , 1521 (2008).
• Hric  et al. [2014] D. Hric, R. K. Darst, and S. Fortunato, Physical Review E  90 , 062805 (2014).
• Yang and Leskovec [2015] J. Yang and J. Leskovec, Knowledge and Information Systems  42 , 181 (2015).
• Newman and Clauset [2016] M. E. J. Newman and A. Clauset, Nature Communications  7 , 11863 (2016).
• Kawamoto and Kabashima [2018] T. Kawamoto and Y. Kabashima, Physical Review E  97 , 022315 (2018).
• Chen  et al. [2018] S. Chen, Z.-Z. Wang, L. Tang, Y.-N. Tang, Y.-Y. Gao, H.-J. Li, J. Xiang, and Y. Zhang,  PLOS ONE  13 , e0205284 (2018) .
• Sobolevsky and Belyi [2022] S. Sobolevsky and A. Belyi, Applied Network Science  7 , 1 (2022).
• Steinhaeuser and Chawla [2010] K. Steinhaeuser and N. V. Chawla, Pattern Recognition Letters  31 , 413 (2010).
• Csardi and Nepusz [2006] G. Csardi and T. Nepusz,  InterJournal Complex Systems  1 , 1695 (2006) .
• Miltenberger [2024] M. Miltenberger, Interactive visualizations of Mittelmann benchmarks (2024),  https://mattmilten.github.io/mittelmann-plots/ date accessed: 2024-03-28.
• Miyauchi and Miyamoto [2013] A. Miyauchi and Y. Miyamoto, The European Physical Journal B  86 , 1 (2013).
• Cafieri  et al. [2014] S. Cafieri, A. Costa, and P. Hansen, Annals of Operations Research  222 , 213 (2014).
• Aref  et al. [2020] S. Aref, A. J. Mason, and M. C. Wilson, Networks  75 , 95 (2020).
• Aref and Neal [2021] S. Aref and Z. P. Neal, Scientific Reports  11 , 19939 (2021).
• Bonchi  et al. [2022] F. Bonchi, D. García-Soriano, and F. Gullo,  Correlation Clustering: Morgan & Claypool Publishers  (Morgan & Claypool Publishers, 2022).
• Belyi  et al. [2023] A. Belyi, S. Sobolevsky, A. Kurbatski, and C. Ratti, Mathematical Methods of Operations Research  98 , 269 (2023).
• Sukeda  et al. [2023] I. Sukeda, A. Miyauchi, and A. Takeda, European Journal of Operational Research  309 , 516 (2023).
• Aref  et al. [2023b] S. Aref, H. Chheda, and M. Mostajabdaveh,  Dataset of networks used in assessing the Bayan algorithm for community detection (2023b), figShare https://doi.org/10.6084/m9.figshare.22442785 .

Adaptive large neighborhood search algorithm with reinforcement search strategy for solving extended cooperative multi task assignment problem of UAVs

New citation alert added.

This alert has been successfully added and will be sent to:

You will be notified whenever a record that you have chosen has been cited.

To manage your alert preferences, click on the button below.

New Citation Alert!

Please log in to your account

Information & Contributors

Bibliometrics & citations, view options, index terms.

Applied computing

Computers in other domains

Computer systems organization

Dependable and fault-tolerant systems and networks

Embedded and cyber-physical systems

Robotic autonomy

Robotic control

Computing methodologies

Artificial intelligence

Control methods

Planning and scheduling

Planning for deterministic actions

Planning under uncertainty

Recommendations

Conflict-based search with optimal task assignment.

We consider a variant of the Multi-Agent Path-Finding problem that seeks both task assignments and collision-free paths for a set of agents navigating on a graph, while minimizing the sum of costs of all agents. Our approach extends Conflict-Based ...

Task assignment algorithms for unmanned aerial vehicle networks: A comprehensive survey

Unmanned aerial vehicles (UAVs) have significant prospects in a plethora of public and civic spheres. Recently, UAVs have focused primarily on applications where human presence is either impossible or hazardous. A swarm of small UAVs ...

Study on the Task Assignment for Multi-UCAV in Air-Combat

Considering the decision-making problem for UCAV cooperative attack on multiple aerial targets, this paper analyzed the air combat situation superiority, established the UCAV angel superiority model and speed superiority model. Taking into account the ...

Information

Published in.

Elsevier Science Inc.

United States

Publication History

Author tags.

• Task assignment
• Heterogeneous UAV
• Adaptive large neighborhood search
• Reinforcement search strategy
• Research-article

Contributors

Other metrics, bibliometrics, article metrics.

• 0 Total Citations
• 0 Total Downloads
• Downloads (Last 12 months) 0
• Downloads (Last 6 weeks) 0

View options

Login options.

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Share this publication link.

Copying failed.

Share on social media

Affiliations, export citations.

• Please download or close your previous search result export first before starting a new bulk export. Preview is not available. By clicking download, a status dialog will open to start the export process. The process may take a few minutes but once it finishes a file will be downloadable from your browser. You may continue to browse the DL while the export process is in progress. Download
• Download citation
• Copy citation

We are preparing your search results for download ...

We will inform you here when the file is ready.

Your file of search results citations is now ready.

Your search export query has expired. Please try again.

Algorithms for the Constrained Assignment Problems with Bounds and Maximum Penalty

• Conference paper
• First Online: 19 September 2024
• Cite this conference paper

• Guojun Hu 9 , 10 ,
• Pengxiang Pan 9 ,
• Junran Lichen 11 &
• Lijian Cai 12  

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 15180))

Included in the following conference series:

• International Conference on Algorithmic Aspects in Information and Management

As a result of the substantial increase in mobile data traffic that has placed a lot of pressure on cloud computing centers, it is necessary to select the network edge servers for data processing, this process is called edge computing . In order to use the network edge servers more efficiently, it is usually expected that the number of objects served by any edge server will exceed a certain number and also be controlled within a certain number.

In order to efficiently solve the aforementioned problem, motivated by the Cloud-Edge Collaborative Computing Framework, we model the task offloading problem as a constrained assignment problems with bounds and maximum penalty (CA-BMP). Specifically, given m machines and n independent jobs, the machine \(g_{i}\) receives at least \(l_i\) and at most \(u_i\) jobs to execute, and each job must be either continuously executed on some machine with its processing time, or rejected with its penalty that we must pay for. We consider the CA-BMP problem and its important variant. (1) The CA-BMP problem is to find an assignment scheme of jobs to satisfy the constraints as mentioned-above, and the objective is to minimize the total processing times of executed jobs plus maximum penalty of rejected jobs; (2) The penalized assignment problem with bounds (the PA-B problem) is to find an assignment scheme of jobs to satisfy the constraints as mentioned-above, the objective is to minimize the total processing times of executed jobs plus maximum penalty of executed jobs. As our main contributions, we design two exact combinatorial algorithms to solve the CA-BMP problem and the PA-B problem, respectively. In addition, we give numerical examples to illustrate the execution processes of the two algorithms we proposed.

This paper was supported by the Caiyun Postdoctoral Program of Yunnan Province [No. 72]. Junran Lichen was also supported by Fundamental Research Funds for the Central Universities (No. buctrc202219). Guojun Hu and Pengxiang Pan were also supported by the Project of Yunling Scholars Training of Yunnan Province.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime
• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Available as EPUB and PDF
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Bartal, Y., Leonardi, S., Marchetti-Spaccamela, A., Sgall, J., Stougie, L.: Multiprocessor scheduling with rejection. SIAM Discret. Math. 13 (1), 64–78 (2000)

Article   MathSciNet   Google Scholar  

Engels, D.W., Karger, D.R., Kolliopoulos, S.G., Sengupta, S., Uma, R.N., Wein, J.: Techniques for scheduling with rejection. J. Algorithms 49 (1), 175–191 (2003)

Gaggero, M., Paolucci, M., Ronco, R.: Exact and heuristic solution approaches for energy-efficient identical parallel machine scheduling with time-of-use costs. Eur. J. Oper. Res. 311 (3), 845–866 (2023)

Gao, Y., Yuan, J.J., Ng, C.T., Cheng, T.C.E.: Pareto-scheduling with family jobs or ND-agent on a parallel-batch machine to minimize the makespan and maximum cost. 4OR-Q. J. Oper. Res. 20 (2), 273–287 (2022)

Google Scholar  

Geng, Z.C., Zhang, Y.: Single-machine preemptive scheduling with release dates involving the total weighted late work criterion. J. Oper. Res. Soc. China 11 (3), 693–706 (2023)

Hoogeveen, H.: Multicriteria scheduling. Eur. J. Oper. Res. 167 (3), 592–623 (2005)

Ji, T.X., Wan, X.L., Guan, X.J., Zhu, A.C., Ye, F.: Towards optimal application offloading in heterogeneous edge-cloud computing. IEEE Trans. Comput. 72 (11), 3259–3272 (2023)

Article   Google Scholar  

Jin, H., Gregory, M.A., Li, S.: A review of intelligent computation offloading in multiaccess edge computing. IEEE Access 10 , 71481–71495 (2022)

Kones, I., Levin, A.: A unified framework for designing EPTAS for load balancing on parallel machines. Algorithmica 81 (7), 3025–3046 (2019)

Koulamas, C., Steiner, G.: New results for scheduling to minimize tardiness on one machine with rejection and related problems. J. Sched. 24 (1), 27–34 (2021)

Krumke, S.O., Thielen, C.: The generalized assignment problem with minimum quantities. Eur. J. Oper. Res. 228 (1), 46–55 (2013)

Kuhn, H.W.: The Hungarian method for the assignment problem. Nav. Res. Logist. Q. 2 , 83–97 (1955)

Kuo, W.H., Yang, D.L.: Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect. Eur. J. Oper. Res. 174 (2), 1184–1190 (2006)

Lazarev, A.A., Lemtyuzhnikova, D.V., Werner, F.: A metric approach for scheduling problems with minimizing the maximum penalty. Appl. Math. Model. 89 , 1163–1176 (2021)

Li, W.D., Li, J.P., Zhang, X.J., Chen, Z.B.: Penalty cost constrained identical parallel machine scheduling problem. Theor. Comput. Sci. 607 (part 2), 181–192 (2015)

Li, W.D., Ou, J.W.: Machine scheduling with restricted rejection: an application to task offloading in cloud-edge collaborative computing. Eur. J. Oper. Res. 314 (3), 912–919 (2024)

Liu, X.F., Xiao, M., Li, W.D., Zhu, Y.Y., Ma, L.: Algorithms for single machine scheduling problem with release dates and submodular penalties. J. Comb. Optim. 45 (4), 105 (2023)

Ou, J.W., Zhong, X.L., Wang, G.Q.: An improved heuristic for parallel machine scheduling with rejection. Eur. J. Oper. Res. 241 (3), 653–661 (2015)

Pentico, D.W.: Assignment problems: a golden anniversary survey. Eur. J. Oper. Res. 176 (2), 774–793 (2007)

Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer-Verlag, Berlin (2003)

Shabtay, D., Gaspar, N., Kaspi, M.: A survey on offline scheduling with rejection. J. Sched. 16 (1), 3–28 (2013)

Vakhania, N.: On preemptive scheduling on unrelated machines using linear programming. AIMS Math. 8 (3), 7061–7082 (2023)

Votaw, D.F., Orden, A.: The personnel assignment problem. In: Symposium on Linear Inequalities and Programming, SCOOP 10, US Air Force, pp. 155–163 (1952)

Zhang, L.Q., Lu, L.F.: Parallel-machine scheduling with release dates and rejection. 4OR-Q. J. Oper. Res. 14 (2), 165–172 (2016)

Zhang, X.Z., Xu, D.C., Du, D.L., Wu, C.C.: Approximation algorithms for precedence-constrained identical machine scheduling with rejection. J. Comb. Optim. 35 (1), 318–330 (2018)

Download references

Author information

Authors and affiliations.

School of Mathematics and Statistics, Yunnan University, Kunming, 650504, People’s Republic of China

Guojun Hu & Pengxiang Pan

School of Mathematics, Yunnan Normal University, Kunming, 650504, People’s Republic of China

School of Mathematics and Physics, Beijing University of Chemical Technology, Beijing, 100190, People’s Republic of China

Junran Lichen

School of Information Engineering, Lanzhou University of Finance and Economics, Lanzhou, 730020, People’s Republic of China

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Lijian Cai .

Editor information

Editors and affiliations.

Santa Clara University, Santa Clara, CA, USA

Smita Ghosh

Zhejiang Normal University, Jinhua, China

Rights and permissions

Reprints and permissions

Copyright information

© 2024 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.

About this paper

Cite this paper.

Hu, G., Pan, P., Lichen, J., Cai, L. (2024). Algorithms for the Constrained Assignment Problems with Bounds and Maximum Penalty. In: Ghosh, S., Zhang, Z. (eds) Algorithmic Aspects in Information and Management. AAIM 2024. Lecture Notes in Computer Science, vol 15180. Springer, Singapore. https://doi.org/10.1007/978-981-97-7801-0_3

Download citation

DOI : https://doi.org/10.1007/978-981-97-7801-0_3

Published : 19 September 2024

Publisher Name : Springer, Singapore

Print ISBN : 978-981-97-7800-3

Online ISBN : 978-981-97-7801-0

eBook Packages : Computer Science Computer Science (R0)

Share this paper

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Publish with us

Policies and ethics

• Find a journal
• Track your research