Principales méthodes de partitionnement
Détection de communautés

Du village au club de football, de la famille aux associations d'anciens d'une école, du lieu de travail aux regroupements d'individus qui partagent une même passion, les hommes et les femmes ont de nombreuses occasions de tisser des liens plus ou moins forts, occasionnels ou pérennes. Ces liens peuvent être territorialisés quand ils se construisent à l'occasion d'évènements ayant une réalité physique et temporelle (naissance, scolarité, travail, salons, etc.). Ils peuvent aussi être dématérialisés quand ils relèvent de cultures ou de pratiques sociales partagées. Internet a ouvert de nouvelles formes de liens sociaux dématérialisés. Les réseaux sociaux sont devenus un nouveau champ d'investigation très courtisé tant par la recherche que par l'industrie. Leur traduction formelle peut être retrouvée dans les graphes.

Cependant, les liens sociaux fonctionnent en général à partir de l'émergence de groupes. Par exemple, un mariage donne l'occasion de rassembler un groupe familial, souvent aussi un groupe d'amis. En pratique, les liens sociaux conduisent à des liens communautaires. Plus qu'un être social, qui s'insère dans un tissu, l'homme est un être communautaire dans la mesure où son appartenance à une communauté l'enrichit des traits partagés par les membres de cette communauté et en même temps, l'amène à enrichir les traits communs aux membres de la communauté.

Une dynamique heureuse ou malheureuse résulte de cette appartenance, qu'elle soit explicite ou implicite. Les conflits armés, les guerres de religion ou même les batailles entre tribus de banlieues rivales en sont une malheureuse illustration. À l'inverse, les communautés, qui sont le résultat de liens sociaux, créent à leur tour des liens sociaux, et favorisent les échanges. La création et la vie des communautés est à la fois un fait social, culturel et économique. Leur étude et l'assistance à leur construction ouvrent un nouveau champ de recherches particulièrement riche sur le plan scientifique et sur le plan industriel.

La détection de communautés a d'abord été un domaine de recherche initié par les sociologues. L'analyse des enjeux est un exercice difficile étant donnés leur nombre et les formes extrêmement variées qu'ils présentent, certaines de ces formes étant parfois politiquement sensibles. À un extrême, la constitution d'équipes sportives, par exemple de rugby, ne fait pas problème quant au nombre d'équipes (la création d'une équipe relève de la décision politique d'une ville ou d'un sponsor) au nombre de joueurs (15 dans une équipe pour le rugby à 15, 9 coureurs cyclistes pour le tour de France). Par contre, elle fait toujours problème quant à la composition des équipes, sujet que nous aborderons à l'issue de cet article. On trouve aussi d'innombrables cas de sociétés pour lesquels les enjeux sont délicats. Par exemple, la justification de l'appartenance des citoyens à une localité, à une région, ou d'une région à un pays est un cas très évocateur.

C'est ainsi que le simple critère de la fréquence des échanges téléphoniques  montre le clivage des cultures Wallonnes et Flamandes. Dans la sphère politique, les partis jouent le jeu du partitionnement (un électeur, un vote), mais les électeurs qui hésitent au moment du vote entre plusieurs partis expriment un recouvrement de tendances relevé par les sondages. D'autres enjeux peuvent être cités comme le nombre, la taille et la fréquentation des maternités dans une région, les départements dans une entreprises, les salles de classes dans une commune, etc.

De nouveaux lieux d'investigation et de nouveaux enjeux sociaux, politiques et économiques sont apparus avec le poids grandissant pris par Internet et certaines applications telles que Google, Facebook, ou Tweeter. C'est ainsi que la détection de communautés à partir d'observations d'échanges entre individus ou d'informations sur les individus peut permettre de relever des tendances, de proposer des recommandations, d'offrir de nouveaux services, ou de faciliter la communication dans un environnement numérique pléthorique. La constitution de listes de diffusion « pertinentes » pour les messages ou les photos, et en général pour tous les documents numériques, est un exemple particulièrement intéressant que nous traitons dans cet article.

Mais les enjeux ne se limitent pas à la sphère sociale. En effet, nous montrons plus loin que la détection de communautés, en particulier dans le cas des communautés partitionnées, peut être vue comme un problème de « clustering » dans le domaine de l'analyse des données. Nous montrons qu'en retour elle apporte de nouvelles méthodes à cette discipline. Or, le clustering est essentiel dans beaucoup de domaines scientifiques comme la biologie (classification des protéines ou des gènes), la neurologie dont nous présentons un exemple, pour comprendre et développer de nouvelles connaissances. La détection de communautés peut dépasser son champ d'application traditionnel des réseaux sociaux pour passer à la maturité d'une discipline porteuse de nouvelles méthodes et découvertes.