Utilisation de Firefly pour la détection de communautés / Chouarfa, Touba  

Public ISBD Titre : Utilisation de Firefly pour la détection de communautés Type de document : texte imprimé Auteurs : Chouarfa, Touba, Auteur ; KAMEL, N, Directeur de thèse Editeur : Setif:UFA Année de publication : 2017 Importance : 1 vol (41f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Ingénierie des Données Technologie Web firefly détection de communautés Index. décimale : 004 - Informatique Résumé : Abstract Empirical analysis of network data has been widely conducted for understanding and predicting the structure and function of real systems and identifying interesting patterns and anomalies. One of the most widely studied structural properties of networks is their community structure. These structures become complex when communities overlap every time. Many algorithms have been developed to detect such structures. In our dissertation, we use firefly algorithm to discover community structures. Firefly algorithm is a metaheuristic, based on the light behavior of fireflies. The algorithms we propose generate a division of the network into groups that contains adjacent elements, and optimize an objective function that identify the brightest firefly in which the density of these elements is higher. The space search is explored thanks to the dynamicity of fireflies, where the less bright firefly move towards the brighter one. The experimentations on real world networks show that the communities discovered by our approach have a good quality Note de contenu : Contents Abstract............................................................................................................................ i Acknowledgements ........................................................................................................ ii Contents......................................................................................................................... iii List of figures................................................................................................................ vii General introduction ..................................................................................................... 1 1 Community detection................................................................................................ 3 1.1 Introduction..................................................................................................... 3 1.2 Elements of graph theory ................................................................................ 3 1.2.1 Basics definitions..................................................................................... 3 1.2.2 Graph matrices......................................................................................... 4 1.2.3 Real world graphs .................................................................................... 4 1.2.3.1 Social networks................................................................................. 5 1.2.3.2 Biological networks .......................................................................... 6 1.3 Elements of Community Detection................................................................. 6 1.3.1 Definitions of communities...................................................................... 6 1.3.1.1 Local definitions ............................................................................... 7 1.3.1.2 Global definitions.............................................................................. 7 1.3.1.3 Definitions based on vertex similarity .............................................. 7 1.3.2 Community structure................................................................................ 8 1.3.2.1 Basics................................................................................................ 8 1.3.2.2 Modularity......................................................................................... 8 1.3.4 Applications........................................................................................... 10 1.4 Approaches of Community Detection........................................................... 10 1.4.1 Approaches for non-overlapping community detection......................... 11 1.4.1.1 Graph partitioning ........................................................................... 11 1.4.1.2 Hierarchical clustering .................................................................... 11 1.4.1.3 Modularity optimization ................................................................. 12 1.4.2 Approaches for overlapping community detection ................................ 12 1.4.2.1 Link partitioning algorithm............................................................. 12 1.4.2.2 Clique based algorithms.................................................................. 13 1.4.2.3 Fuzzy algorithms............................................................................. 14 1.4.2.4 Local Expansion and Optimization Algorithms.............................. 15 1.4.2.5 Agent-based and dynamic algorithms............................................. 15 1.5 Conclusion .................................................................................................... 16 2 Meta-heuristics for Community detection............................................................ 17 2.1 Introduction................................................................................................... 17 2.2 Meta-heuristics.............................................................................................. 17 2.2.1 Meta-heuristics based unique solution................................................... 17 2.2.1.1 Simulated Annealing....................................................................... 17 2.2.1.2 Tabu search ..................................................................................... 18 2.2.2 Meta-heuristics based population of solutions....................................... 20 2.2.2.1 Evolutionary methods ..................................................................... 20 2.2.2.2 Swarm intelligence methods........................................................... 21 2.3 Firefly algorithm ........................................................................................... 25 2.3.1 Natural behaviors of fireflies ................................................................. 25 2.3.2 Firefly algorithm .................................................................................... 25 2.3.3 Light intensity and attractiveness........................................................... 26 2.4 Metaheuristics for community detection: The state of art ............................ 28 2.5 Conclusion .................................................................................................... 29 3 Proposed algorithms ............................................................................................... 30 3.1 Introduction................................................................................................... 30 3.2 Node-based algorithm................................................................................... 30 3.2.1 Generation of initial population ............................................................. 31 3.2.1.1 Representation of fireflies............................................................... 32 3.2.1.2 Initialization of fireflies population ................................................ 32 3.2.1.3 Extract community structures ......................................................... 32 3.2.2 Objective function.................................................................................. 33 3.2.3 Behavior of fireflies ................................................................................. 34 3.2.3.1 Light intensity and attractiveness.................................................... 34 3.2.3.2 Distance between two fireflies........................................................ 34 3.2.3.3 Movement strategy.......................................................................... 34 3.3 Link-based algorithm .................................................................................... 35 3.3.1 Phase 1: Link communities.................................................................... 36 3.3.1.1 Generation of an initial population ................................................. 36 3.3.1.2 Objective function........................................................................... 38 3.3.2 Phase 2: Nodes communities ................................................................. 39 3.4 Discussion ..................................................................................................... 40 3.5 Implementation ............................................................................................. 40 3.6 Conclusion .................................................................................................... 40 4 Experimentations and results ................................................................................ 42 4.1 Introduction................................................................................................... 42 4.2 Benchmarks................................................................................................... 42 4.2.1 Karate ..................................................................................................... 42 4.2.2 Dolphins................................................................................................. 43 4.2.3 Polbooks................................................................................................. 43 4.2.4 Football .................................................................................................. 43 4.3 Experimental results...................................................................................... 43 4.3.1 Node-based algorithm............................................................................ 43 4.3.2 Link-based algorithm ............................................................................. 45 4.4 Conclusion .................................................................................................... 45 General conclusion....................................................................................................... 46 Bibliography................................................................................................................. 48 En ligne : https://drive.google.com/file/d/1rB18zShDjae3vvyJoYI2GtgyKjY7rw1G/view?usp=shari [...] Format de la ressource électronique : pdf Utilisation de Firefly pour la détection de communautés [texte imprimé] / Chouarfa, Touba, Auteur ; KAMEL, N, Directeur de thèse . - [S.l.] : Setif:UFA, 2017 . - 1 vol (41f.) ; 29 cm. Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Ingénierie des Données Technologie Web firefly détection de communautés Index. décimale : 004 - Informatique Résumé : Abstract Empirical analysis of network data has been widely conducted for understanding and predicting the structure and function of real systems and identifying interesting patterns and anomalies. One of the most widely studied structural properties of networks is their community structure. These structures become complex when communities overlap every time. Many algorithms have been developed to detect such structures. In our dissertation, we use firefly algorithm to discover community structures. Firefly algorithm is a metaheuristic, based on the light behavior of fireflies. The algorithms we propose generate a division of the network into groups that contains adjacent elements, and optimize an objective function that identify the brightest firefly in which the density of these elements is higher. The space search is explored thanks to the dynamicity of fireflies, where the less bright firefly move towards the brighter one. The experimentations on real world networks show that the communities discovered by our approach have a good quality Note de contenu : Contents Abstract............................................................................................................................ i Acknowledgements ........................................................................................................ ii Contents......................................................................................................................... iii List of figures................................................................................................................ vii General introduction ..................................................................................................... 1 1 Community detection................................................................................................ 3 1.1 Introduction..................................................................................................... 3 1.2 Elements of graph theory ................................................................................ 3 1.2.1 Basics definitions..................................................................................... 3 1.2.2 Graph matrices......................................................................................... 4 1.2.3 Real world graphs .................................................................................... 4 1.2.3.1 Social networks................................................................................. 5 1.2.3.2 Biological networks .......................................................................... 6 1.3 Elements of Community Detection................................................................. 6 1.3.1 Definitions of communities...................................................................... 6 1.3.1.1 Local definitions ............................................................................... 7 1.3.1.2 Global definitions.............................................................................. 7 1.3.1.3 Definitions based on vertex similarity .............................................. 7 1.3.2 Community structure................................................................................ 8 1.3.2.1 Basics................................................................................................ 8 1.3.2.2 Modularity......................................................................................... 8 1.3.4 Applications........................................................................................... 10 1.4 Approaches of Community Detection........................................................... 10 1.4.1 Approaches for non-overlapping community detection......................... 11 1.4.1.1 Graph partitioning ........................................................................... 11 1.4.1.2 Hierarchical clustering .................................................................... 11 1.4.1.3 Modularity optimization ................................................................. 12 1.4.2 Approaches for overlapping community detection ................................ 12 1.4.2.1 Link partitioning algorithm............................................................. 12 1.4.2.2 Clique based algorithms.................................................................. 13 1.4.2.3 Fuzzy algorithms............................................................................. 14 1.4.2.4 Local Expansion and Optimization Algorithms.............................. 15 1.4.2.5 Agent-based and dynamic algorithms............................................. 15 1.5 Conclusion .................................................................................................... 16 2 Meta-heuristics for Community detection............................................................ 17 2.1 Introduction................................................................................................... 17 2.2 Meta-heuristics.............................................................................................. 17 2.2.1 Meta-heuristics based unique solution................................................... 17 2.2.1.1 Simulated Annealing....................................................................... 17 2.2.1.2 Tabu search ..................................................................................... 18 2.2.2 Meta-heuristics based population of solutions....................................... 20 2.2.2.1 Evolutionary methods ..................................................................... 20 2.2.2.2 Swarm intelligence methods........................................................... 21 2.3 Firefly algorithm ........................................................................................... 25 2.3.1 Natural behaviors of fireflies ................................................................. 25 2.3.2 Firefly algorithm .................................................................................... 25 2.3.3 Light intensity and attractiveness........................................................... 26 2.4 Metaheuristics for community detection: The state of art ............................ 28 2.5 Conclusion .................................................................................................... 29 3 Proposed algorithms ............................................................................................... 30 3.1 Introduction................................................................................................... 30 3.2 Node-based algorithm................................................................................... 30 3.2.1 Generation of initial population ............................................................. 31 3.2.1.1 Representation of fireflies............................................................... 32 3.2.1.2 Initialization of fireflies population ................................................ 32 3.2.1.3 Extract community structures ......................................................... 32 3.2.2 Objective function.................................................................................. 33 3.2.3 Behavior of fireflies ................................................................................. 34 3.2.3.1 Light intensity and attractiveness.................................................... 34 3.2.3.2 Distance between two fireflies........................................................ 34 3.2.3.3 Movement strategy.......................................................................... 34 3.3 Link-based algorithm .................................................................................... 35 3.3.1 Phase 1: Link communities.................................................................... 36 3.3.1.1 Generation of an initial population ................................................. 36 3.3.1.2 Objective function........................................................................... 38 3.3.2 Phase 2: Nodes communities ................................................................. 39 3.4 Discussion ..................................................................................................... 40 3.5 Implementation ............................................................................................. 40 3.6 Conclusion .................................................................................................... 40 4 Experimentations and results ................................................................................ 42 4.1 Introduction................................................................................................... 42 4.2 Benchmarks................................................................................................... 42 4.2.1 Karate ..................................................................................................... 42 4.2.2 Dolphins................................................................................................. 43 4.2.3 Polbooks................................................................................................. 43 4.2.4 Football .................................................................................................. 43 4.3 Experimental results...................................................................................... 43 4.3.1 Node-based algorithm............................................................................ 43 4.3.2 Link-based algorithm ............................................................................. 45 4.4 Conclusion .................................................................................................... 45 General conclusion....................................................................................................... 46 Bibliography................................................................................................................. 48 En ligne : https://drive.google.com/file/d/1rB18zShDjae3vvyJoYI2GtgyKjY7rw1G/view?usp=shari [...] Format de la ressource électronique : pdf

Exemplaires (1)

Code-barres	Cote	Support	Localisation	Section	Disponibilité
MAI/0209	MAI/0209	Mémoire	Bibliothéque des sciences	Français	Disponible Disponible

---

1 (1 - 1 / 1)