WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

 > 

Agrégats de mots sémantiquement cohérents issus d'un grand graphe de terrain


par Christian Belbèze
Université Toulouse 1 Capitole - Doctorat en informatique 2012
  

précédent sommaire suivant

Chapitre 2.

Les algorithmes de création de

communautés

2.1 Introduction

Un réseau ou un graphe est souvent constitué, dans le monde des grands graphes de terrain, d'une seule composante connexe ou d'une composante représentant plus de 90% du graphe. Son unité, sa taille et des zones de forte densité de liens suggèrent de le décomposer en ensembles de plus petites tailles. Les méthodes permettant de créer des sous-ensembles de noeuds à l'intérieur d'un graphe sont de plus en plus nombreuses.

Ces méthodes ont deux objectifs possibles: soit créer des ensembles disjoints soit, créer des ensembles avec recouvrements. Les approches purement mathématiques ont le plus souvent comme objet la création de communautés sans recouvrement. Au contraire, les approches davantage orientées « terrain » introduisent des méthodes plus souples.

Les communautés avec recouvrement font infiniment moins couler d'encre que celles qui n'en ont pas. Nommées parfois « overlapping communities » ou « fuzzy clusters », elles peuvent être regardées avec un certain dédain. Schaeffer déclare : « Fuzzy clustering has not been established as a widely accepted approach for graph clustering ... » [Schaffer-2007]. La raison tient peut-être à la difficulté d'en définir les règles de création et de validation, position compréhensible eu égard à l'oxymore que suggère l'idée de communauté avec recouvrements (cf. 1.5.1). En effet, on peut tout à fait considérer que le cluster - ou la communauté de noeuds génériques - existe bien d'un point de vue mathématique. Il suffit pour cela de définir mathématiquement la notion de cluster ou de communauté. Par contre, dans le monde réel, le noeud perd son caractère mathématique. Le groupe de noeuds devient famille, groupe d'amis, troupeau, espace sémantique etc. L'étude des grands graphes de terrain appelle donc une autre approche et une autre terminologie. Les règles ne peuvent plus être générales. Elles doivent être adaptées aux caractéristiques du groupe à former. Par exemple, un ordinateur est en général dans un seul Lan, mais un individu appartient à plusieurs groupes d'amis. De plus, la définition de la communauté est le plus souvent implicite. Il est alors impossible de modéliser de manière générique un regroupement dont les caractéristiques dépendent de la nature des objets manipulés.

2.2. Les partitions ou communautés sans recouvrement 50

Chapitre 2. Les algorithmes de création de communautés

Pourtant, dans le monde réel, il est souvent impossible de placer des limites entre des communautés. Il est évident qu'un usager n'appartient pas qu'à une seule communauté d'usage de téléphones portables ou d'échange de méls. Il en est de même pour les pathologies humaines ou les catégories socioprofessionnelles. Un article ou un livre peut évoquer plusieurs sujets. Un sportif peut posséder plusieurs licences dans plusieurs clubs de sports différents. Un paysan peut travailler sur plusieurs fermes. Et enfin, un mot peut appartenir à plusieurs espaces sémantiques : il peut avoir plusieurs sens dans une même langue, mais aussi des sens différents dans des langues différentes. Le mot « car » est, par exemple, une conjonction de coordination en français et signifie « automobile » en langue anglaise. Notre travail portant sur le regroupement des mots, c'est donc bien sûr sur ces dernières méthodes permettant le recouvrement que notre attention va se porter en priorité.

Dans ce chapitre, nous nous questionnerons aussi sur les méthodes de validation des communautés avec recouvrement et sur l'opportunité d'une classification qualitative des méthodes selon le niveau de complexité de leur algorithme.

précédent sommaire suivant







Rassembler les contraires c est creer l harmonie