University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Salah Eddine Taibi |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la recherche
Titre : Hybrid metaheuristic approach for community detection in complex networks. Type de document : document électronique Auteurs : Salah Eddine Taibi, Auteur ; Bouamama, Salim, Directeur de thèse Editeur : Sétif:UFA1 Année de publication : 2025 Importance : 1 vol (133 f.) Format : 29 cm Langues : Anglais (eng) Catégories : Thèses & Mémoires:Informatique Mots-clés : Hybrid metaheuristic
Social network analysis
Community discovery
Modularity maximizationIndex. décimale : 004 - Informatique Résumé :
Optimization is a scientific field dedicated to identifying optimal solutions from a set of feasible
alternatives. Numerous critical problems in business, economics, and engineering can be formulated
as optimization tasks. However, most such problems are classified as NP-Hard, meaning
that finding an exact optimal solution is computationally infeasible for large-scale instances. In
such cases, stochastic meta-heuristic methods are preferred as they provide near-optimal solutions
within a reasonable timeframe. This stands in contrast to exact methods, which guarantee
optimality but at the cost of exponentially longer runtimes. Consequently, the hybridization of
optimization methods has garnered significant research interest in recent years as a strategy to
reduce computational time while enhancing solution quality, i.e., both effectiveness and accuracy.
This thesis addresses a specific NP-Hard optimization problem: community detection in
complex networks, where the objective is to maximize the modularity metric. To tackle this
challenge, we propose two novel hybrid meta-heuristics:
• The Clustering Coefficient Discrete Bat Algorithm (CC-DBAT): This approach utilizes the
clustering coefficient to generate an intelligent initial population. It is further enhanced
by hybridizing it with the Fast Local Move heuristic and a random neighbors technique to
improve its search capability.
• The Fast Local Move Iterated Greedy (FLMIG) Algorithm: This method hybridizes the
Iterated Greedy (IG) framework with the Fast Local Move heuristic. A novel reconstruction
procedure is incorporated to ensure the connectivity of the detected communities.
Experimental results, evaluated using multiple performance metrics, demonstrate that the
proposed algorithms outperform existing state-of-the-art methods, achieving superior performance
in both solution quality and computational efficiency.Note de contenu :
Sommaire
List of Figures xii
1 Introduction 1
1.1 Overview: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Our contributions: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Thesis organization: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Academic Publications Produced: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Background 7
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Complex networks topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.1 Undirected Networks: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.2 Directed Networks: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.3 Weighted Networks: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.4 Signed Networks: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.5 Attributed network: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.6 Multiplex Networks: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.7 Dynamic Networks: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Optimization problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4 Taxonomy of optimization problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.5 Computational complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.5.1 Definitions and basic concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.5.2 Complexity classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.6 Local Versus Global Optima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.7 Optimization methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.7.1 Exact Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.7.2 Approximate Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3 Evolution of Optimization-Based Community Detection 27
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Problem formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.1 Problem Statement: Community Discovery Problem . . . . . . . . . . . . . . 27
3.2.2 Problem Statement: Overlapping Community Discovery . . . . . . . . . . . 28
3.2.3 Problem Statement: Multiplex Community Discovery . . . . . . . . . . . . . 28
3.2.4 Problem Statement: Dynamic Community Discovery . . . . . . . . . . . . . 29
3.2.5 The instability of detected community partitions in dynamic networks and
the temporal smoothness: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.6 Community detection as optimization problem: . . . . . . . . . . . . . . . . . 32
3.3 Evaluation Metrics: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3.1 External approaches based on the ground truth . . . . . . . . . . . . . . . . 33
3.3.2 External approaches based on the quality function: . . . . . . . . . . . . . . 35
3.3.3 Evaluation of community score function . . . . . . . . . . . . . . . . . . . . . 41
3.3.4 Internal approaches based on quantitative evaluation: . . . . . . . . . . . . 41
3.4 Benchmarking and datasets: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.4.1 Real-world dataset: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.4.2 Synthetic Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.5 Taxonomy of Community Detection Methods . . . . . . . . . . . . . . . . . . . . . . . 47
3.5.1 Foundational Classifications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.5.2 Existing Taxonomies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.5.3 The novel taxonomy for community detection based optimization: . . . . . 48
3.6 Community detection based optimization methods . . . . . . . . . . . . . . . . . . . 56
3.6.1 Static community detection algorithms . . . . . . . . . . . . . . . . . . . . . . 56
3.6.2 Dynamic community detection algorithms: . . . . . . . . . . . . . . . . . . . 63
3.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4 An Enhanced Bat Algorithm Using Clustering Coefficient for Community
Detection in Complex Networks 70
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.2 Bat algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.2.1 Binary bat algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.3 The proposed algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.3.1 Problem definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.3.2 Generate initial population . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.3.3 Update velocity and position . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.3.4 Fast Local Move Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.3.5 Random neighbor community . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.4 Experimental Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.4.1 Problem instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.4.2 Evaluation criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.4.3 Results and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5 Complex Network Community Discovery Using Fast Local Move Iterated
Greedy Algorithm 84
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.2 Iterated Greedy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.2.1 Greedy Construction Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.2.2 Iterated Greedy Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.3 Proposed approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.3.1 Generate_Initial_Solution procedure . . . . . . . . . . . . . . . . . . . . . . . 87
5.3.2 Fast_Local_Move procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.3.3 Destruction_Solution procedure . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.3.4 Reconstruction_Heuristic procedure . . . . . . . . . . . . . . . . . . . . . . . . 89
5.3.5 Select_Next_Solution procedure . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.3.6 Time Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.4 Experimental Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.4.1 Preview of implementation and tuning of algorithms . . . . . . . . . . . . . 92
5.4.2 Problem instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.4.3 Algorithm tuning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.5 Results and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.5.1 Performance on real-world networks . . . . . . . . . . . . . . . . . . . . . . . 94
5.5.2 Performance on synthetic networks problems . . . . . . . . . . . . . . . . . . 100
5.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
6 Conclusion and future work 115
6.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
6.2 Future works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
Bibliography 117Côte titre : DI/0096 Hybrid metaheuristic approach for community detection in complex networks. [document électronique] / Salah Eddine Taibi, Auteur ; Bouamama, Salim, Directeur de thèse . - [S.l.] : Sétif:UFA1, 2025 . - 1 vol (133 f.) ; 29 cm.
Langues : Anglais (eng)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Hybrid metaheuristic
Social network analysis
Community discovery
Modularity maximizationIndex. décimale : 004 - Informatique Résumé :
Optimization is a scientific field dedicated to identifying optimal solutions from a set of feasible
alternatives. Numerous critical problems in business, economics, and engineering can be formulated
as optimization tasks. However, most such problems are classified as NP-Hard, meaning
that finding an exact optimal solution is computationally infeasible for large-scale instances. In
such cases, stochastic meta-heuristic methods are preferred as they provide near-optimal solutions
within a reasonable timeframe. This stands in contrast to exact methods, which guarantee
optimality but at the cost of exponentially longer runtimes. Consequently, the hybridization of
optimization methods has garnered significant research interest in recent years as a strategy to
reduce computational time while enhancing solution quality, i.e., both effectiveness and accuracy.
This thesis addresses a specific NP-Hard optimization problem: community detection in
complex networks, where the objective is to maximize the modularity metric. To tackle this
challenge, we propose two novel hybrid meta-heuristics:
• The Clustering Coefficient Discrete Bat Algorithm (CC-DBAT): This approach utilizes the
clustering coefficient to generate an intelligent initial population. It is further enhanced
by hybridizing it with the Fast Local Move heuristic and a random neighbors technique to
improve its search capability.
• The Fast Local Move Iterated Greedy (FLMIG) Algorithm: This method hybridizes the
Iterated Greedy (IG) framework with the Fast Local Move heuristic. A novel reconstruction
procedure is incorporated to ensure the connectivity of the detected communities.
Experimental results, evaluated using multiple performance metrics, demonstrate that the
proposed algorithms outperform existing state-of-the-art methods, achieving superior performance
in both solution quality and computational efficiency.Note de contenu :
Sommaire
List of Figures xii
1 Introduction 1
1.1 Overview: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Our contributions: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Thesis organization: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Academic Publications Produced: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Background 7
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Complex networks topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.1 Undirected Networks: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.2 Directed Networks: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.3 Weighted Networks: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.4 Signed Networks: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.5 Attributed network: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.6 Multiplex Networks: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.7 Dynamic Networks: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Optimization problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4 Taxonomy of optimization problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.5 Computational complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.5.1 Definitions and basic concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.5.2 Complexity classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.6 Local Versus Global Optima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.7 Optimization methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.7.1 Exact Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.7.2 Approximate Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3 Evolution of Optimization-Based Community Detection 27
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Problem formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.1 Problem Statement: Community Discovery Problem . . . . . . . . . . . . . . 27
3.2.2 Problem Statement: Overlapping Community Discovery . . . . . . . . . . . 28
3.2.3 Problem Statement: Multiplex Community Discovery . . . . . . . . . . . . . 28
3.2.4 Problem Statement: Dynamic Community Discovery . . . . . . . . . . . . . 29
3.2.5 The instability of detected community partitions in dynamic networks and
the temporal smoothness: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.6 Community detection as optimization problem: . . . . . . . . . . . . . . . . . 32
3.3 Evaluation Metrics: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3.1 External approaches based on the ground truth . . . . . . . . . . . . . . . . 33
3.3.2 External approaches based on the quality function: . . . . . . . . . . . . . . 35
3.3.3 Evaluation of community score function . . . . . . . . . . . . . . . . . . . . . 41
3.3.4 Internal approaches based on quantitative evaluation: . . . . . . . . . . . . 41
3.4 Benchmarking and datasets: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.4.1 Real-world dataset: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.4.2 Synthetic Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.5 Taxonomy of Community Detection Methods . . . . . . . . . . . . . . . . . . . . . . . 47
3.5.1 Foundational Classifications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.5.2 Existing Taxonomies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.5.3 The novel taxonomy for community detection based optimization: . . . . . 48
3.6 Community detection based optimization methods . . . . . . . . . . . . . . . . . . . 56
3.6.1 Static community detection algorithms . . . . . . . . . . . . . . . . . . . . . . 56
3.6.2 Dynamic community detection algorithms: . . . . . . . . . . . . . . . . . . . 63
3.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4 An Enhanced Bat Algorithm Using Clustering Coefficient for Community
Detection in Complex Networks 70
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.2 Bat algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.2.1 Binary bat algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.3 The proposed algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.3.1 Problem definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.3.2 Generate initial population . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.3.3 Update velocity and position . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.3.4 Fast Local Move Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.3.5 Random neighbor community . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.4 Experimental Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.4.1 Problem instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.4.2 Evaluation criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.4.3 Results and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5 Complex Network Community Discovery Using Fast Local Move Iterated
Greedy Algorithm 84
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.2 Iterated Greedy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.2.1 Greedy Construction Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.2.2 Iterated Greedy Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.3 Proposed approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.3.1 Generate_Initial_Solution procedure . . . . . . . . . . . . . . . . . . . . . . . 87
5.3.2 Fast_Local_Move procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.3.3 Destruction_Solution procedure . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.3.4 Reconstruction_Heuristic procedure . . . . . . . . . . . . . . . . . . . . . . . . 89
5.3.5 Select_Next_Solution procedure . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.3.6 Time Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.4 Experimental Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.4.1 Preview of implementation and tuning of algorithms . . . . . . . . . . . . . 92
5.4.2 Problem instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.4.3 Algorithm tuning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.5 Results and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.5.1 Performance on real-world networks . . . . . . . . . . . . . . . . . . . . . . . 94
5.5.2 Performance on synthetic networks problems . . . . . . . . . . . . . . . . . . 100
5.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
6 Conclusion and future work 115
6.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
6.2 Future works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
Bibliography 117Côte titre : DI/0096 Exemplaires
Code-barres Cote Support Localisation Section Disponibilité aucun exemplaire
Titre : Hybrid metaheuristic approach for community detection in complex networks. Type de document : document électronique Auteurs : Salah Eddine Taibi, Auteur ; Bouamama, Salim, Directeur de thèse Editeur : Sétif:UFA1 Année de publication : 2025 Importance : 1 vol (133 f.) Format : 29 cm Langues : Anglais (eng) Catégories : Thèses & Mémoires:Informatique Mots-clés : Hybrid metaheuristic
Social network analysis
Community discovery
Modularity maximizationIndex. décimale : 004 - Informatique Résumé :
Optimization is a scientific field dedicated to identifying optimal solutions from a set of feasible
alternatives. Numerous critical problems in business, economics, and engineering can be formulated
as optimization tasks. However, most such problems are classified as NP-Hard, meaning
that finding an exact optimal solution is computationally infeasible for large-scale instances. In
such cases, stochastic meta-heuristic methods are preferred as they provide near-optimal solutions
within a reasonable timeframe. This stands in contrast to exact methods, which guarantee
optimality but at the cost of exponentially longer runtimes. Consequently, the hybridization of
optimization methods has garnered significant research interest in recent years as a strategy to
reduce computational time while enhancing solution quality, i.e., both effectiveness and accuracy.
This thesis addresses a specific NP-Hard optimization problem: community detection in
complex networks, where the objective is to maximize the modularity metric. To tackle this
challenge, we propose two novel hybrid meta-heuristics:
• The Clustering Coefficient Discrete Bat Algorithm (CC-DBAT): This approach utilizes the
clustering coefficient to generate an intelligent initial population. It is further enhanced
by hybridizing it with the Fast Local Move heuristic and a random neighbors technique to
improve its search capability.
• The Fast Local Move Iterated Greedy (FLMIG) Algorithm: This method hybridizes the
Iterated Greedy (IG) framework with the Fast Local Move heuristic. A novel reconstruction
procedure is incorporated to ensure the connectivity of the detected communities.
Experimental results, evaluated using multiple performance metrics, demonstrate that the
proposed algorithms outperform existing state-of-the-art methods, achieving superior performance
in both solution quality and computational efficiency.Note de contenu :
Sommaire
List of Figures xii
1 Introduction 1
1.1 Overview: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Our contributions: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Thesis organization: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Academic Publications Produced: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Background 7
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Complex networks topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.1 Undirected Networks: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.2 Directed Networks: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.3 Weighted Networks: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.4 Signed Networks: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.5 Attributed network: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.6 Multiplex Networks: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.7 Dynamic Networks: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Optimization problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4 Taxonomy of optimization problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.5 Computational complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.5.1 Definitions and basic concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.5.2 Complexity classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.6 Local Versus Global Optima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.7 Optimization methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.7.1 Exact Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.7.2 Approximate Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3 Evolution of Optimization-Based Community Detection 27
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Problem formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.1 Problem Statement: Community Discovery Problem . . . . . . . . . . . . . . 27
3.2.2 Problem Statement: Overlapping Community Discovery . . . . . . . . . . . 28
3.2.3 Problem Statement: Multiplex Community Discovery . . . . . . . . . . . . . 28
3.2.4 Problem Statement: Dynamic Community Discovery . . . . . . . . . . . . . 29
3.2.5 The instability of detected community partitions in dynamic networks and
the temporal smoothness: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.6 Community detection as optimization problem: . . . . . . . . . . . . . . . . . 32
3.3 Evaluation Metrics: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3.1 External approaches based on the ground truth . . . . . . . . . . . . . . . . 33
3.3.2 External approaches based on the quality function: . . . . . . . . . . . . . . 35
3.3.3 Evaluation of community score function . . . . . . . . . . . . . . . . . . . . . 41
3.3.4 Internal approaches based on quantitative evaluation: . . . . . . . . . . . . 41
3.4 Benchmarking and datasets: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.4.1 Real-world dataset: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.4.2 Synthetic Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.5 Taxonomy of Community Detection Methods . . . . . . . . . . . . . . . . . . . . . . . 47
3.5.1 Foundational Classifications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.5.2 Existing Taxonomies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.5.3 The novel taxonomy for community detection based optimization: . . . . . 48
3.6 Community detection based optimization methods . . . . . . . . . . . . . . . . . . . 56
3.6.1 Static community detection algorithms . . . . . . . . . . . . . . . . . . . . . . 56
3.6.2 Dynamic community detection algorithms: . . . . . . . . . . . . . . . . . . . 63
3.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4 An Enhanced Bat Algorithm Using Clustering Coefficient for Community
Detection in Complex Networks 70
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.2 Bat algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.2.1 Binary bat algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.3 The proposed algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.3.1 Problem definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.3.2 Generate initial population . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.3.3 Update velocity and position . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.3.4 Fast Local Move Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.3.5 Random neighbor community . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.4 Experimental Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.4.1 Problem instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.4.2 Evaluation criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.4.3 Results and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5 Complex Network Community Discovery Using Fast Local Move Iterated
Greedy Algorithm 84
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.2 Iterated Greedy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.2.1 Greedy Construction Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.2.2 Iterated Greedy Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.3 Proposed approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.3.1 Generate_Initial_Solution procedure . . . . . . . . . . . . . . . . . . . . . . . 87
5.3.2 Fast_Local_Move procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.3.3 Destruction_Solution procedure . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.3.4 Reconstruction_Heuristic procedure . . . . . . . . . . . . . . . . . . . . . . . . 89
5.3.5 Select_Next_Solution procedure . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.3.6 Time Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.4 Experimental Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.4.1 Preview of implementation and tuning of algorithms . . . . . . . . . . . . . 92
5.4.2 Problem instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.4.3 Algorithm tuning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.5 Results and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.5.1 Performance on real-world networks . . . . . . . . . . . . . . . . . . . . . . . 94
5.5.2 Performance on synthetic networks problems . . . . . . . . . . . . . . . . . . 100
5.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
6 Conclusion and future work 115
6.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
6.2 Future works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
Bibliography 117Côte titre : DI/0096 Hybrid metaheuristic approach for community detection in complex networks. [document électronique] / Salah Eddine Taibi, Auteur ; Bouamama, Salim, Directeur de thèse . - [S.l.] : Sétif:UFA1, 2025 . - 1 vol (133 f.) ; 29 cm.
Langues : Anglais (eng)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Hybrid metaheuristic
Social network analysis
Community discovery
Modularity maximizationIndex. décimale : 004 - Informatique Résumé :
Optimization is a scientific field dedicated to identifying optimal solutions from a set of feasible
alternatives. Numerous critical problems in business, economics, and engineering can be formulated
as optimization tasks. However, most such problems are classified as NP-Hard, meaning
that finding an exact optimal solution is computationally infeasible for large-scale instances. In
such cases, stochastic meta-heuristic methods are preferred as they provide near-optimal solutions
within a reasonable timeframe. This stands in contrast to exact methods, which guarantee
optimality but at the cost of exponentially longer runtimes. Consequently, the hybridization of
optimization methods has garnered significant research interest in recent years as a strategy to
reduce computational time while enhancing solution quality, i.e., both effectiveness and accuracy.
This thesis addresses a specific NP-Hard optimization problem: community detection in
complex networks, where the objective is to maximize the modularity metric. To tackle this
challenge, we propose two novel hybrid meta-heuristics:
• The Clustering Coefficient Discrete Bat Algorithm (CC-DBAT): This approach utilizes the
clustering coefficient to generate an intelligent initial population. It is further enhanced
by hybridizing it with the Fast Local Move heuristic and a random neighbors technique to
improve its search capability.
• The Fast Local Move Iterated Greedy (FLMIG) Algorithm: This method hybridizes the
Iterated Greedy (IG) framework with the Fast Local Move heuristic. A novel reconstruction
procedure is incorporated to ensure the connectivity of the detected communities.
Experimental results, evaluated using multiple performance metrics, demonstrate that the
proposed algorithms outperform existing state-of-the-art methods, achieving superior performance
in both solution quality and computational efficiency.Note de contenu :
Sommaire
List of Figures xii
1 Introduction 1
1.1 Overview: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Our contributions: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Thesis organization: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Academic Publications Produced: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Background 7
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Complex networks topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.1 Undirected Networks: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.2 Directed Networks: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.3 Weighted Networks: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.4 Signed Networks: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.5 Attributed network: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.6 Multiplex Networks: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.7 Dynamic Networks: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Optimization problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4 Taxonomy of optimization problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.5 Computational complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.5.1 Definitions and basic concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.5.2 Complexity classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.6 Local Versus Global Optima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.7 Optimization methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.7.1 Exact Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.7.2 Approximate Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3 Evolution of Optimization-Based Community Detection 27
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Problem formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.1 Problem Statement: Community Discovery Problem . . . . . . . . . . . . . . 27
3.2.2 Problem Statement: Overlapping Community Discovery . . . . . . . . . . . 28
3.2.3 Problem Statement: Multiplex Community Discovery . . . . . . . . . . . . . 28
3.2.4 Problem Statement: Dynamic Community Discovery . . . . . . . . . . . . . 29
3.2.5 The instability of detected community partitions in dynamic networks and
the temporal smoothness: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.6 Community detection as optimization problem: . . . . . . . . . . . . . . . . . 32
3.3 Evaluation Metrics: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3.1 External approaches based on the ground truth . . . . . . . . . . . . . . . . 33
3.3.2 External approaches based on the quality function: . . . . . . . . . . . . . . 35
3.3.3 Evaluation of community score function . . . . . . . . . . . . . . . . . . . . . 41
3.3.4 Internal approaches based on quantitative evaluation: . . . . . . . . . . . . 41
3.4 Benchmarking and datasets: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.4.1 Real-world dataset: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.4.2 Synthetic Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.5 Taxonomy of Community Detection Methods . . . . . . . . . . . . . . . . . . . . . . . 47
3.5.1 Foundational Classifications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.5.2 Existing Taxonomies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.5.3 The novel taxonomy for community detection based optimization: . . . . . 48
3.6 Community detection based optimization methods . . . . . . . . . . . . . . . . . . . 56
3.6.1 Static community detection algorithms . . . . . . . . . . . . . . . . . . . . . . 56
3.6.2 Dynamic community detection algorithms: . . . . . . . . . . . . . . . . . . . 63
3.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4 An Enhanced Bat Algorithm Using Clustering Coefficient for Community
Detection in Complex Networks 70
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.2 Bat algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.2.1 Binary bat algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.3 The proposed algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.3.1 Problem definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.3.2 Generate initial population . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.3.3 Update velocity and position . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.3.4 Fast Local Move Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.3.5 Random neighbor community . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.4 Experimental Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.4.1 Problem instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.4.2 Evaluation criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.4.3 Results and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5 Complex Network Community Discovery Using Fast Local Move Iterated
Greedy Algorithm 84
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.2 Iterated Greedy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.2.1 Greedy Construction Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.2.2 Iterated Greedy Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.3 Proposed approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.3.1 Generate_Initial_Solution procedure . . . . . . . . . . . . . . . . . . . . . . . 87
5.3.2 Fast_Local_Move procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.3.3 Destruction_Solution procedure . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.3.4 Reconstruction_Heuristic procedure . . . . . . . . . . . . . . . . . . . . . . . . 89
5.3.5 Select_Next_Solution procedure . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.3.6 Time Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.4 Experimental Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.4.1 Preview of implementation and tuning of algorithms . . . . . . . . . . . . . 92
5.4.2 Problem instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.4.3 Algorithm tuning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.5 Results and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.5.1 Performance on real-world networks . . . . . . . . . . . . . . . . . . . . . . . 94
5.5.2 Performance on synthetic networks problems . . . . . . . . . . . . . . . . . . 100
5.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
6 Conclusion and future work 115
6.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
6.2 Future works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
Bibliography 117Côte titre : DI/0096 Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité DI/0096 DI/0096 Thèse Bibliothèque des sciences Anglais Disponible
Disponible
