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 overallmeasure of clustering quality widely used to capture the doubleconstraint, internal and external, of well formed communities. Theproblem became a NP-hard optimization problem. The main weakof modularity is the resolution limit, which tends to makeundetectable very small communities especially as the network islarge. The algorithm of Louvain, one of the most efficient one tooptimize modularity, proceeds by merging communities. This thesisattempts to modify the algorithm so that it mainly produces relevantmerges that do not make worse the effects of resolution limit, usinga merge condition. In addition, by combining it with a memeticalgorithm, proposed clusterings are very close to the expected onesfor graphs generated by a model that reproduces the characteristicsof complex networks. Finally, the memetic algorithm greatly reducesthe inconsistency of solution, another weakness of modularity suchthat, for the same graph, two partitions found from an exploration ofnodes in a random order can be structurally very different, makingthem difficult to interpret.
| Identifer | oai:union.ndltd.org:theses.fr/2013LEMA1031 |
| Date | 03 December 2013 |
| Creators | Gach, Olivier |
| Contributors | Le Mans, Py, Dominique, Hao, Jin-Kao |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | French |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0023 seconds