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.
| 
