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

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

2.3 Les différentes méthodes de recherche de

communautés avec recouvrement

On peut considérer que les premières études théoriques et fondatrices de ces méthodes ont été faites en 1965 par Lotfi Zadeh [Zadeh-1965]. Ce mathématicien a posé les bases d'un système de classification où les objets peuvent appartenir à plusieurs ensembles qu'il nomme « ensembles flous » ou « fuzzy sets ». Chaque élément possède un tableau d'appartenance où le degré d'appartenance à chaque ensemble flou est indiqué par une valeur entre 0 et 1. D'après ce scientifique : « Un contrôleur électromécanique doté d'un raisonnement humain serait plus performant qu'un contrôleur classique ».

Bien que ces travaux ne portent pas explicitement sur des graphes et l'appartenance de noeuds à des communautés, ils abordent la problématique de la complexité d'une multi-appartenance pondérée d'objets et marquent aussi la volonté de rechercher une modélisation du monde réel.

Ensembles bivalents pour caractériser la température d'une pièce.						« Fuzzy Sets » ou ensembles flous qui représentent la température d'une pièce.

Figure 2.3 : comparaison d'ensembles bivalents et de « Fuzzy Sets » (ensembles flous) source : http://www3.imperial.ac.uk/computing/.

Ces deux préoccupations sont identiques à celles qui nous animent, créant ainsi, semble-t-il, un lien entre ces travaux et nos recherches. La capacité de certains objets à appartenir à plusieurs communautés distinctes est indéniable. La complexité qu'apporte cette caractéristique dans le repérage de communautés au sein d'un graphe est importante. Les algorithmes qui le permettent seront plus complexes. Les techniques de validation devront aussi tenir compte de cette caractéristique.

Les méthodes sont regroupées en trois types principaux :

? Les méthodes de recherche de formes ; ? Les méthodes en plusieurs phases ;

? Les méthodes issues des méthodes sans recouvrement, modifiées pour permettre le recouvrement.

2.3. Les différentes méthodes de recherche de communautés avec recouvrement 56