Gain and Pain in Graph Partitioning: Finding Accurate Communities in Complex Networks

This paper presents an approach to community detection in complex networks by simultaneously incorporating a connectivity-based metric and Max-Min Modularity. By leveraging the connectivity-based metric and employing a heuristic algorithm, we develop a novel complementary graph for the Max-Min Modul...

Full description

Saved in:
Bibliographic Details
Published in:Algorithms 2024-06, Vol.17 (6), p.226
Main Authors: Ferdowsi, Arman, Dehghan Chenary, Maryam
Format: Article
Language:English
Subjects:
Accuracy
Algorithms
Analysis
approximation algorithm
community detection
complex network analysis
Connectivity
Efficiency
graph partitioning
Heuristic
Heuristic methods
Integer programming
Mathematical programming
Methods
Modularity
Networks
Optimization
Optimization algorithms
Optimization techniques
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper presents an approach to community detection in complex networks by simultaneously incorporating a connectivity-based metric and Max-Min Modularity. By leveraging the connectivity-based metric and employing a heuristic algorithm, we develop a novel complementary graph for the Max-Min Modularity that enhances its effectiveness. We formulate community detection as an integer programming problem of an equivalent yet more compact counterpart model of the revised Max-Min Modularity maximization problem. Using a row generation technique alongside the heuristic approach, we then provide a hybrid procedure for near-optimally solving the model and discovering high-quality communities. Through a series of experiments, we demonstrate the success of our algorithm, showcasing its efficiency in detecting communities, particularly in extensive networks.
ISSN:1999-4893
1999-4893
DOI:10.3390/a17060226