2.2 Les partitions ou communautés sans
recouvrement
Face à un ensemble complexe de taille importante, il
n'existe finalement que deux attitudes : soit l'ignorer, soit, chercher
à l'ordonner en le décomposant en entités plus
réduites. La création de communautés ou de sous-parties
distinctes dans un graphe tient à un besoin d'ordre. Que ce soit pour
effectuer des taxinomies ou simplement obtenir des sous-ensembles plus clairs,
plus maniables ou plus faciles à étudier, nous voulons en premier
lieu classer. Les méthodes sans recouvrement, sans « flou »,
sont aptes à accompagner ce désir d'ordre.
Il existe un grand nombre d'approches permettant de
créer des communautés sans recouvrement. Ces différentes
approches pour développer des communautés distinctes doivent
être aussi considérées comme des bases pour
développer de nouvelles méthodes permettant, elles, de
créer des communautés avec recouvrement. Les communautés
sans recouvrement peuvent aussi être utilisées en tant
qu'éléments dans des processus plus complexes. Par exemple, en
ajoutant à des communautés disjointes des espaces qui,
potentiellement, sont partagées entre plusieurs communautés.
Ces méthodes n'étant pas au centre de notre
travail, nous ne présentons ici que succinctement les méthodes
les plus utilisées ou présentant une base potentielle pour
autoriser le recouvrement. Les algorithmes des méthodes sont
regroupés en trois grands types :
? Les algorithmes séparatistes ;
? Les algorithmes de scission ;
? Les algorithmes de recherche de zones de forte
modularité.
2.2. Les partitions ou communautés sans recouvrement 51
| 
