Méthode de classification organisée pour la recherche de communautés dans les réseaux sociaux - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2009

Méthode de classification organisée pour la recherche de communautés dans les réseaux sociaux

Résumé

Les graphes sont l'outil mathématique privilégié pour modéliser des systèmes dans lesquels les individus sont décrits par leurs interactions deux à deux. On les retrouve de manière naturelle dans l'étude des réseaux sociaux, des réseaux d'interactions biologiques, de l'internet. . . Ces graphes peuvent atteindre des tailles importantes et, au-delà d'une centaine de sommets, il devient difficile de comprendre leurs structures et de les visualiser de manière lisible. La recherche de groupes de sommets fortement liés dans un grand graphe et l'étude des relations existant entre ces groupes permet de donner une représentation simplifiée de la structure de grands graphes : une telle représentation est importante pour l'utilisateur final, sociologue, biologiste, historien ..., car elle permet de pouvoir appréhender de manière très intuitive le réseau social ou biologique modélisé. Une solution classique consiste à s'appuyer sur une méthode de classification des sommets d'un graphe. Les classes, que l'on peut voir comme un graphe simplifié, sont ensuite représentées par des méthodes classiques de visualisation de graphes. Ici, nous nous proposons de présenter des approches plus directes. La première est un algorithme de cartes auto-organisatrices adapté à des données non vectorielles par le biais de noyaux. Cette approche, qui n'est pas spécifique à la classification de sommets de graphe, utilise un plongement implicite du graphe dans un espace de Hilbert à noyau reproduisant Plus récemment, nous avons proposé une approche plus spécifique à l'organisation de sommets d'un graphe. Cette autre approche permet également de projeter les sommets du graphe sur une structure de type carte auto-organisatrice mais elle est basée sur l'extension d'un critère de qualité spécifique à la classification de sommets de graphes : la modularité. Nous proposons d'optimiser directement une version "organisée" de la modularité par un algorithme de recuit déterministe. Enfin, nous présenterons des exemples de l'utilisation de ces méthodes d'organisation de sommets d'un graphe, exemples issus de réseaux sociaux .
Fichier principal
Vignette du fichier
p240.pdf (210.17 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00386797 , version 1 (22-05-2009)

Identifiants

  • HAL Id : inria-00386797 , version 1

Citer

Nathalie Villa, Fabrice Rossi. Méthode de classification organisée pour la recherche de communautés dans les réseaux sociaux. 41èmes Journées de Statistique, SFdS, Bordeaux, 2009, Bordeaux, France, France. ⟨inria-00386797⟩
262 Consultations
136 Téléchargements

Partager

Gmail Facebook X LinkedIn More