Bi-objective modeling and optimization by greedy stochastic algorithm / Hayet Dahmri  

Public ISBD Titre : Bi-objective modeling and optimization by greedy stochastic algorithm Type de document : document électronique Auteurs : Hayet Dahmri, Auteur ; Bouamama, Salim, Directeur de thèse Editeur : Sétif:UFA1 Année de publication : 2024 Importance : 1 vol (119 f.) Format : 29 cm Langues : Anglais (eng) Catégories : Thèses & Mémoires:Informatique Mots-clés : Multi-objective combinatorial optimization Stochastic algorithms Greedy heuristic Minimum weight minimum connected dominating set problem Index. décimale : 004 - Informatique Résumé : Multi-objective optimization problems (MOPs) involve the simultaneous optimization of multiple, often conflicting objectives, and have wide-ranging applications in fields such as engineering, business, economics, and logistics. Most MOPs are classified as NP-Hard, meaning that finding an exact optimal solution is computationally expensive and impractical for large instances. In such cases, stochastic methods are preferred, as they offer near-optimal solutions within a reasonable time, as opposed to exact methods, which guarantee optimal solutions but require exponentially longer runtimes. This thesis addresses a bi-objective optimization problem known as the Minimum Weight Minimum Connected Dominating Set (MWMCDS) problem. The objective is to minimize both the number of nodes (cardinality) and the total weight of the connected dominating set (CDS) in a given graph, a well-known challenge in graph theory. To tackle this problem, three greedy stochastic algorithms are proposed. The first, Greedy Simulated Annealing (GSA), applies the simulated annealing technique with an aggregated objective function to guide the search process. The second, Improved NSGA-II (I-NSGA-II), is an enhanced version of the widely used NSGA-II algorithm, specifically adapted for multi-objective optimization. The third algorithm, Multi-objective Greedy Simulated Annealing (MGSA), introduces a new multi-objective adaptation of simulated annealing based on Pareto optimization. In all three approaches, tailored greedy heuristics are integrated to boost the efficiency of the solution process. Experimental results, based on several performance metrics, demonstrate that the proposed algorithms outperform existing state-of-the-art methods, achieving superior results in terms of both solution quality and computational efficiency. Note de contenu : Côte titre : DI/0083 En ligne : http://dspace.univ-setif.dz:8888/jspui/handle/123456789/5013 Bi-objective modeling and optimization by greedy stochastic algorithm [document électronique] / Hayet Dahmri, Auteur ; Bouamama, Salim, Directeur de thèse . - [S.l.] : Sétif:UFA1, 2024 . - 1 vol (119 f.) ; 29 cm. Langues : Anglais (eng) Catégories : Thèses & Mémoires:Informatique Mots-clés : Multi-objective combinatorial optimization Stochastic algorithms Greedy heuristic Minimum weight minimum connected dominating set problem Index. décimale : 004 - Informatique Résumé : Multi-objective optimization problems (MOPs) involve the simultaneous optimization of multiple, often conflicting objectives, and have wide-ranging applications in fields such as engineering, business, economics, and logistics. Most MOPs are classified as NP-Hard, meaning that finding an exact optimal solution is computationally expensive and impractical for large instances. In such cases, stochastic methods are preferred, as they offer near-optimal solutions within a reasonable time, as opposed to exact methods, which guarantee optimal solutions but require exponentially longer runtimes. This thesis addresses a bi-objective optimization problem known as the Minimum Weight Minimum Connected Dominating Set (MWMCDS) problem. The objective is to minimize both the number of nodes (cardinality) and the total weight of the connected dominating set (CDS) in a given graph, a well-known challenge in graph theory. To tackle this problem, three greedy stochastic algorithms are proposed. The first, Greedy Simulated Annealing (GSA), applies the simulated annealing technique with an aggregated objective function to guide the search process. The second, Improved NSGA-II (I-NSGA-II), is an enhanced version of the widely used NSGA-II algorithm, specifically adapted for multi-objective optimization. The third algorithm, Multi-objective Greedy Simulated Annealing (MGSA), introduces a new multi-objective adaptation of simulated annealing based on Pareto optimization. In all three approaches, tailored greedy heuristics are integrated to boost the efficiency of the solution process. Experimental results, based on several performance metrics, demonstrate that the proposed algorithms outperform existing state-of-the-art methods, achieving superior results in terms of both solution quality and computational efficiency. Note de contenu : Côte titre : DI/0083 En ligne : http://dspace.univ-setif.dz:8888/jspui/handle/123456789/5013

Exemplaires (1)

Code-barres	Cote	Support	Localisation	Section	Disponibilité
DI/0083	DI/0083	Thèse	Bibliothèque des sciences	Anglais	Disponible Disponible

Design of a learning methode for automatic data extraction / Bouamama, Salim  

Public ISBD Titre : Design of a learning methode for automatic data extraction Type de document : texte imprimé Auteurs : Bouamama, Salim, Acteur ; Abdellah BOUKERRAM, Directeur de thèse ; Christian BLUM Editeur : Setif:UFA Année de publication : 2013 Importance : 1 vol (128 f .) Format : 29 cm Catégories : Informatique Mots-clés : Données de grande dimension Regroupement spectral Apprentissage en utilisant lesgraphes Régularisation sur graphes Marches aléatoires sur graphes Diffusion maps Analyse vidéo du comportement humain Segmentation hiérarchique des flux vidéo Moments de Zernike spatio-temporels Points SIFT Index. décimale : 004 Informatique Résumé : Optimization is a scientific discipline that is concerned with the extraction of optimalsolutions for a problem, among alternatives. Many challenging applications inbusiness, economics,and engineering can be formulated as optimization problems.However, they are often complexand difficult to solve by an exact method within areasonable amount of time.In this thesis we propose a novel approach called population based iterated greedy algorithm in order to efficiently explore and exploit the search space of one of the NP-hard combinatorial optimizationproblems namely the minimumn weigh vertex cover problem. It isa fundamental graph problem with many important real-life applicationssuchas, for example, in wireless communication, circuit design and network flows.An extensive experimental evaluation on a commonly used set of benchmarkinstances shows that our algorithm outperforms current state-of-the-art methods notonly in solution quality but also in computation time. Côte titre : DI/0010 En ligne : http://dspace.univ-setif.dz:8888/jspui/handle/123456789/35 Design of a learning methode for automatic data extraction [texte imprimé] / Bouamama, Salim, Acteur ; Abdellah BOUKERRAM, Directeur de thèse ; Christian BLUM . - [S.l.] : Setif:UFA, 2013 . - 1 vol (128 f .) ; 29 cm. Catégories : Informatique Mots-clés : Données de grande dimension Regroupement spectral Apprentissage en utilisant lesgraphes Régularisation sur graphes Marches aléatoires sur graphes Diffusion maps Analyse vidéo du comportement humain Segmentation hiérarchique des flux vidéo Moments de Zernike spatio-temporels Points SIFT Index. décimale : 004 Informatique Résumé : Optimization is a scientific discipline that is concerned with the extraction of optimalsolutions for a problem, among alternatives. Many challenging applications inbusiness, economics,and engineering can be formulated as optimization problems.However, they are often complexand difficult to solve by an exact method within areasonable amount of time.In this thesis we propose a novel approach called population based iterated greedy algorithm in order to efficiently explore and exploit the search space of one of the NP-hard combinatorial optimizationproblems namely the minimumn weigh vertex cover problem. It isa fundamental graph problem with many important real-life applicationssuchas, for example, in wireless communication, circuit design and network flows.An extensive experimental evaluation on a commonly used set of benchmarkinstances shows that our algorithm outperforms current state-of-the-art methods notonly in solution quality but also in computation time. Côte titre : DI/0010 En ligne : http://dspace.univ-setif.dz:8888/jspui/handle/123456789/35

Exemplaires (2)

Code-barres	Cote	Support	Localisation	Section	Disponibilité
DI/0010	DI/0010-0011	Thèse	Bibliothèque des sciences	Anglais	Disponible Disponible
DI/0011	DI/0010-0011	Thèse	Bibliothèque des sciences	Anglais	Disponible Disponible

Hybrid metaheuristic approach for community detection in complex networks. / Salah Eddine Taibi

Public ISBD 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 maximization Index. 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 117 Cô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 maximization Index. 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 117 Côte titre : DI/0096

Exemplaires

Code-barres	Cote	Support	Localisation	Section	Disponibilité
aucun exemplaire

Hybrid metaheuristic approach for community detection in complex networks. / Salah Eddine Taibi

Public ISBD 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 maximization Index. 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 117 Cô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 maximization Index. 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 117 Cô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

---

1 (1 - 4 / 4)