Description
Date depot: 1 janvier 1900
Titre: Détection des communautés dans les réseaux sociaux et dynamiques : une approche multi-agents
Directrice de thèse:
Zahia GUESSOUM (CReSTIC)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
De nos jours, les grands réseaux sont partout dans la science ; la société ; le transport (lignes aériennes, routes) ; les communications (internet, web, ́changes de fichiers ou de courriers) ;
la vie sociale (collaborations, amitié, échanges économiques) ; sciences du vivant (interactions entre protéines et gènes, dépendances entre espèces) ; l’analyse des langages (synonymie, concurrences de mots) ; etc. [1, 2]. L’omniprésence de ces réseaux rend indispensable leur analyse.
D’un point de vue abstrait, ces réeaux peuvent être d ́finis comme ́tant un ensemble d’entités reliées (ou en interactions). Ainsi, ils peuvent être modélisés par des graphes (ensemble de nœuds et de liens entre eux) appel ́s graphes de terrain (complex networks en anglais). En effet, il devint possible par exemple d’étudier la propagation d’information dans ces réseaux (rumeurs, virus) et de détecter les acteurs d’influence [1, 3, 5].
Un axe de recherche qui a reçu beaucoup d’intérêt dans l’analyse des réseaux sociaux est la détection des communautés où l’on d ́finit une communauté comme étant un ensemble d’entités ayant beaucoup d’interactions entre elles et peu d’interactions avec l’extérieur. Ce problème, qui consiste ` d ́couper le graphe modélisant le réseau social, est NP-difficile [2]. D’autres difficultés viennent s’ajouter à cette complexité intrinsèque du problème et qui sont la définition exacte de la notion de communauté et la grande taille de ces réseaux. De nombreuses approches ont été proposées en littérature dans le cas des réseaux sociaux statiques [1, 3].
Cependant très peu de travaux [5] se sont intéressés aux r ́seaux sociaux dynamiques dont la structure (acteurs et liens) évolue au cours du temps. Par exemple, on peut avoir de nouveaux contacts dans les réseaux de contacts ; de nouvelles machines ou nouvelles connections entre machines dans les réseaux d’ordinateurs, etc.
La détection des communautés dans les réseaux sociaux dynamiques pose plusieurs difficultés. La première difficulté est due à la définition de la notion de communautés dynamiques.
Une approche simple est de les définir comme une succession de communautés statiques ; mais il est aussi plus réaliste de les modéliser comme ́tant une communauté qui évolue au cours du temps. La deuxième difficulté est liée à la modélisation du r ́seau social lui-même. Doit-on le considérer comme une succession de graphes pris ` des instants successifs ou comme étant un seul graphe avec une certaine dynamique qu’il faudra modéliser.
Dans cette thèse, et dans l’objectif d’apporter des éléments de réponses à toutes ces difficultés, on va proposer une approche multi-agents dans laquelle chaque nœud du graphe est représenté par un agent ayant une certaine autonomie. Par la suite, on va proposer des mécanismes d’auto-organisation pour l’évolution du r ́seau social qui vont nous permettre de faire émerger les communautés sans calcul prohibitif. Ainsi, l’idée centrale serait de doter le graphe modélisant le réseau social de proactivité permettant aux nœuds de mettre à jour leur propre état ; de détecter les communautés qui émergent et les exploiter et cela sans l’intervention d’un observateur externe. Ainsi, nous serons capables d’analyser la stabilité de ces communautés : les communautés évoluent, apparaissent, disparaissent, ` quel rythme ? On peut se demander ce que l’on peut conclure sur le graphe initial ` partir des modifications des communautés. Si une communauté disparaît est-ce que ses membres disparaîtraient, est-ce qu’ils ont tissé de nouveaux liens qui pourraient entraîner la fusion de leur communauté avec la communauté voisine ou est-ce qu’elle s’est juste séparée ?
Références
[1] A. Clauset, M.E.J. Newman, and C. Moore. Finding community structure in very large networks. Physical review E, 70(6) :066111, 2004.
[2] Chris H. Q. Ding, Xiaofeng He, Hongyuan Zha, Ming Gu, and Horst D. Simon. A min-max cut algorithm for graph partitioning and data clustering. In Nick Cercone, Tsau Young Lin, and Xindong Wu, editors, ICDM, pages 107–114. IEEE Computer Society, 2001.
[3] Santo Fortunato. Community detection in graphs. Physics Reports, 486(3-5) :75 – 174,
2010.
[4] GNT. Taille Réseau Facebook. http://www.generation-nt.com/ facebook-france-nombre-utilisateurs-15-mil%lions-actualite-941111.htm, Novembre 2011 (dernier accès).
[5] Lei Tang, Huan Liu, and Jianping Zhang. Identifying evolving groups in dynamic mul- timode networks. IEEE Transactions on Knowledge and Data Engineering, 24 :72–85, 2012.
Doctorant.e: Zardi Hedia