Gach, Olivier
[Author]
;
Le Mans
[Contributor];
Py, Dominique
[Contributor];
Hao, Jin-Kao
[Contributor]
Algorithmes mémétiques de détection de communautés dans les réseaux complexes : techniques palliatives de la limite de résolution ; Memetic algorithm for community detection in Complex Network : mitigation techniques to the resolution limit, the main weakness of modularity
You can manage bookmarks using lists, please log in to your user account for this.
Media type:
Text;
Electronic Thesis;
E-Book
Title:
Algorithmes mémétiques de détection de communautés dans les réseaux complexes : techniques palliatives de la limite de résolution ; Memetic algorithm for community detection in Complex Network : mitigation techniques to the resolution limit, the main weakness of modularity
Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
Les réseaux complexes, issus de relevés de terrain d’origines trèsvariées, en biologie, science de l’information ou sociologie,présentent une caractéristique remarquable dénommée structurecommunautaire. Des groupes, ou communautés, à l’intérieur duréseau, ont une cohésion interne forte et des liens entre eux plusfaibles. Sans connaissance a priori du nombre de communautés, ladifficulté réside dans la caractérisation d’un bon partitionnement encommunautés. La modularité est une mesure globale de qualité departitionnement très utilisée qui capture les contraintes de cohésioninterne forte et de liens externes faibles. Elle transforme le problèmede détection de communautés en problème d’optimisationNP-difficile. Elle souffre d’un défaut, la limite de résolution, qui tendà rendre indétectables les très petites communautés d’autant plusque le réseau est grand. L’algorithme le plus efficace pour optimiserla modularité, dit de Louvain, procède par fusion de communautés.Cette thèse s’attache à modifier cet algorithme pour qu’il réalisemajoritairement des fusions pertinentes, qui n’aggravent pas lalimite de résolution, en utilisant une condition de fusion. De plus, enl’associant à un algorithme mémétique, les partitions proposéessont très proches des partitions attendues pour des graphesgénérés par un modèle qui reproduit les caractéristiques desréseaux complexes. Enfin, cet algorithme mémétique réduitfortement l’inconsistance de solution, défaut de la modularité selonlequel deux partitions trouvées à partir d’un examen des noeudsdans un ordre aléatoire, pour le même graphe, peuvent êtrestructurellement très différentes, rendant leur interprétation délicate. ; From various applications, in sociology or biology for instance,complex networks exhib the remarquable property of communitystructure. Groups, sometimes called communities, has a stronginternal cohesion and poor links between them. Whithout priorknowledge of the number of communities, the difficulty lies in thecharacterization of a good clustering. Modularity is an ...