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

1.5 Les communautés

1.5.1 Définition et choix de la terminologie : clusters, communautés ou agrégats ?

Le terme « communauté » provient d'une analogie avec les réseaux sociaux, un des champs d'étude au coeur duquel les graphes sont très présents.

La communauté au sein d'un graphe est définie par Santo Fortunato [Fortunato-2010] comme un « ensemble autonome ». Ceci est l'expression d'un nombre de noeuds connectés et regroupés (en communauté) de telle sorte que le nombre de liens intracommunautaires soit le plus élevé possible et le nombre de liens extracommunautaires soit le plus faible possible.

La définition de la communauté induite devient alors : « Une communauté forte est telle que le degré de chaque noeud interne est supérieur à son degré externe ». La représentation de la figure 1.17 illustre cette définition.

1.5. Les communautés 44

Chapitre 1. État de l'art, notions, définitions et vocabulaire sur les graphes

Figure 1.17 : Exemple de graphe où l'on peut intuitivement détecter trois communautés telles que définies par Santo Fortunato.

Pourtant, il n'existe pas de définition couramment admise de ces ensembles. Le regroupement intuitif des noeuds selon leurs connectivités, bien qu'ayant un grand succès, n'a pas démontré son universalité. Fortunato lui-même, déclare que « le premier problème dans la clusterisation de graphe est la recherche d'une définition des caractéristiques quantitatives d'une communauté » [Fortunato-2010].

Dans ce contexte, le terme même de « communauté » peut sans doute être considéré comme abusif. En effet, hérité des réseaux sociaux, il sous-tend un lien sémantique d'appartenance à une unité et le partage d'éléments identitaires communs. Par exemple, parlerions-nous facilement de communautés d'ordinateurs pour nommer un ensemble de postes de travail sur un LAN au sein d'un WAN ?

La terminologie anglaise parfois utilisée, qui est celle de « Cluster », possède, elle, des définitions précises et contextuelles. Cependant, elle se réfère autant à la structure inter-sommets, qu'aux sommets eux-mêmes. Considérer l'ensemble à étudier (le cluster) comme un ensemble de sommets participant d'une entité ayant sa propre identité, nous semble abusif. C'est, pour utiliser une métaphore courante, comme si pour définir un être humain on nommait un ensemble d'organes liés par un réseau sanguin par le nom de ce réseau sanguin. De plus, dans les réseaux sociaux, une fois la communauté découverte, la structure porteuse n'a plus d'« usage ». Ainsi, un groupe d'amis est indépendant de la relation ayant servi à les repérer (SMS, emails, connexions téléphoniques ou autres).

De plus, si la définition des clusters ou des communautés retient comme caractéristique majeure la proximité la plus importante possible en interne et la plus faible possible en inter-communautés, l'appartenance d'objets à plusieurs communautés devient alors une source naturelle de baisse de la qualité. La communauté devant, par définition, être le moins en interaction avec l'extérieur, la dénomination « communauté avec recouvrements » devient un oxymore.

Il en est de même pour la terminologie de « super-communauté ». Cette terminologie, utilisée pour signifier des communautés de taille importante, associe alors le préfixe « super » à un objet dont la qualité peut être à priori jugé faible. La taille très importante d'une

1.5. Les communautés 45

Chapitre 1. État de l'art, notions, définitions et vocabulaire sur les graphes

communauté est le plus souvent l'expression d'une incapacité à déterminer des ensembles plus pertinents.

On peut aussi aisément concevoir que pour nommer les ensembles de mots destinés à servir de moteurs à des communautés dynamiques d'utilisateurs, le choix du terme « communauté » ne soit pas judicieux. Il convient d'utiliser un lexique différent pour nommer d'une part, les communautés sociales, de l'autre, les ensembles de mots.

On peut enfin remarquer que Gregory Palla, au fil de ses articles, a remplacé le mot « community » [Palla&al-2005] par « module » [Palla&al-2007]. Le terme de « module » ayant déjà en mathématiques (module de nombre complexe, vecteur) et en informatique (bloc de code) des définitions précises et différentes, il ne semble pas approprié.

Toutes ces raisons nous encouragent à l'utilisation d'un autre terme : celui d'agrégat. Bien qu'il soit rarement utilisé [Botafogo&al-1991] [Cucala-2009], ce terme semble pourtant le plus adapté.

Un agrégat est défini comme une « réunion d'éléments matériels juxtaposés, généralement hétérogènes, présentant entre eux une certaine cohésion et formant un tout » (Larousse 2001). Tant que la nature du « tout » n'est pas caractérisée comme ayant une identité propre, il ne nous semble pas judicieux d'employer d'autres termes pour nommer ce regroupement. Ainsi, tout travail de regroupement va-t-il créer un agrégat qui est éventuellement une communauté. Un agrégat est défini par Bayaly et Cunny, comme « un ensemble de noeuds liés logiquement dans un graphe » [Bailey&al-1986].

Pour conclure cette tentative de définition, je citerai Filippo Radicchi et al [Radicchi&al-2004] : « Cependant, pour analyser un réseau, il est nécessaire de préciser quantitativement et sans ambiguïté ce qu'est une communauté. ... Une communauté peut être vue comme un ensemble d'éléments qui répondent à certaines règles ». Ainsi, par exemple, la communauté des sommets présentant les degrés les plus élevés devient possible. De telles communautés seraient alors à l'opposé des définitions données par Santo Fortunato [Fortunato-2010].

Il nous faudra définir les règles de la communauté. Une fois l'agrégat validé comme respectant les règles caractérisant « notre définition » d'une communauté, il pourra être éventuellement nommé troupeau, ban, équipe, club, sous-réseau ou même communauté en fonction de sa nature et de la nature des objets regroupés. Cependant, pour respecter les terminologies habituelles et la cohérence avec certains travaux, nous continuerons à nommer « communautés » un ensemble de noeuds identifié comme groupe constitué dans l'état de l'art de ce travail. Nous réserverons le terme d'agrégat à la deuxième partie de ce travail.

La création de communautés dans des graphes est un sujet qui est de plus en plus abordé. Selon notre étude et notre approche, identifier les communautés dans les grands graphes revient à partitionner les grands graphes en sous-graphes et à se poser la question suivante : recouvrement ou non recouvrement ?

1.5. Les communautés 46

Chapitre 1. État de l'art, notions, définitions et vocabulaire sur les graphes

1. Les communautés sans recouvrement

Dans les communautés, les noeuds appartiennent au plus à une seule communauté. Ce sont celles-ci qui sont majoritairement étudiées. La figure 1.17

présente un exemple de découpage en communautés sans recouvrement.

Dans la liste des travaux présentés au paragraphe 3.4.3, les travaux Hagen et al. sont parmi les plus concrets [Hagen&al-1992]. Ils utilisent des algorithmes de partitionnement de graphes de façon à optimiser le regroupement des liaisons entre composants sur une même couche du circuit imprimé, afin de limiter le nombre de liaisons inter-couches, liaisons qui sont à la fois chères et sources de défaillance.

2. Les communautés avec recouvrement

Dans les communautés avec recouvrement, les noeuds peuvent appartenir à un nombre indéterminé de communautés. Bien que représentant souvent des découpages plus proches de la vie réelle, elles sont peu étudiées (cf. figure 1.18). Une des raisons en est la difficulté de validation et le caractère flou que peut présenter l'affectation d'un noeud à plusieurs communautés si celle-ci est pondérée ou relative.

Dans la liste des travaux présentés au paragraphe 3.4.3, ceux de Palla et al. sont les plus célèbres. Ils portent sur la création de communautés dans le domaine de la biologie mais aussi dans celui des réseaux sociaux [Palla&al-2005].

Figure 1.18 : Un exemple de graphe où l'on peut observer six communautés avec recouvrement.

précédent sommaire suivant







Rassembler les contraires c est creer l harmonie