Présentation
RÉSUMÉ
L'importance prise récemment par les réseaux sociaux sur Internet met en avant les recherches dans le domaine de la détection de communautés. L'objectif est de regrouper les individus en fonction de critères qui les rapprochent tout en différenciant au mieux les groupes ainsi formés. Les méthodes les plus connues sont présentées ici en insistant sur celles qui optimisent un critère propre aux réseaux analysés, comme la modularité. La nécessité de calculer dans des temps raisonnables conduit ces méthodes à produire des résultats approchés. Ils peuvent être améliorés pour obtenir des communautés stables révélées par un équilibre de Nash.
Lire cet article issu d'une ressource documentaire complète, actualisée et validée par des comités scientifiques.
Lire l’articleABSTRACT
The growing interest on social networks on the Internet highlights the problem of community detection. The objective is to gather together individuals according to criteria which make them look similar whilst distinguishing the resulting groups as much as possible. The most frequent methods are presented, with more details on those which use intrinsic properties of the analyzed networks, such as modularity. To compute in reasonable time these methods produce only approximated results. These results can be improved to obtain stable communities according to a Nash Equilibrium.
Auteur(s)
-
Michel CRAMPES : Laboratoire LGI2P - École des Mines d'Alès, site de Nîmes
-
Michel PLANTIÉ : Laboratoire LGI2P - École des Mines d'Alès, site de Nîmes
INTRODUCTION
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.
MOTS-CLÉS
détection de communauté recouvrement de communautés équilibre de Nash sociologie statistiques analyse de données réseaux sociaux
KEYWORDS
community detection | overlaping communities | Nash equilibrium | sociology | statistics | data analysis | social networks
DOI (Digital Object Identifier)
Cet article fait partie de l’offre
Documents numériques Gestion de contenu
(75 articles en ce moment)
Cette offre vous donne accès à :
Une base complète d’articles
Actualisée et enrichie d’articles validés par nos comités scientifiques
Des services
Un ensemble d'outils exclusifs en complément des ressources
Un Parcours Pratique
Opérationnel et didactique, pour garantir l'acquisition des compétences transverses
Doc & Quiz
Des articles interactifs avec des quiz, pour une lecture constructive
Présentation
3. Principales méthodes de détection de recouvrements
3.1 Graphes unipartis
Les stratégies de détection de communautés recouvrantes à partir de graphes unipartis éventuellement pondérés étendent bien souvent les méthodes de partitionnement. Par exemple, elles utilisent le système de percolation de k-cliques , ou elles font appel à la marche aléatoire dans un graphe . Gregory utilise les algorithmes de propagation de labels. D'autres auteurs cherchent les recouvrements entre communautés partitionnées ou combinent le modèle d'interaction de spins de Pott et le recuit simulé ...
Cet article fait partie de l’offre
Documents numériques Gestion de contenu
(75 articles en ce moment)
Cette offre vous donne accès à :
Une base complète d’articles
Actualisée et enrichie d’articles validés par nos comités scientifiques
Des services
Un ensemble d'outils exclusifs en complément des ressources
Un Parcours Pratique
Opérationnel et didactique, pour garantir l'acquisition des compétences transverses
Doc & Quiz
Des articles interactifs avec des quiz, pour une lecture constructive
Principales méthodes de détection de recouvrements
BIBLIOGRAPHIE
-
(1) - BARBER (M.) - Modularity and community detection in bipartite networks. - Physical Review E, 76(6), p. 1-9 (2007).
-
(2) - BERGE (C.) - Hypergraphes, combinatoires des ensembles finis. - Gauthier-Villars (1987).
-
(3) - BLONDEL (V.D.), GUILLAUME (J.-L.), LAMBIOTTE (R.), LEFEBVRE (E.) - Fast unfolding of communities in large networks. - Journal of Statistical Mechanics : Theory and Experiment, 10, p. 10008, oct. 2008.
-
(4) - CATANI (M.), THIEBAUT DE SCHOTTEN (M.) - Atlas of human brain connections. - Oxford University Press (2012).
-
(5) - CHEN (W.), LIU (Z.), SUN (X.), WANG (Y.) - Community detection in social networks through community formation games. - In Proceedings of the Twenty-Second international joint conference on Artificial Intelligence, IJCAI'11, AAAI Press, vol. 3, p. 2576-2581 (2011).
-
(6)...
ANNEXES
http://www.social-networks.mines-ales.fr
Démonstrateur http://www.communities.mines-ales.fr
Analyse sociale en ligne d'un profil Facebook par le logiciel Mathematica http://www.wolframalpha.com/facebook
Site sur la méthode de Louvain http://www.perso.uclouvain.be/vincent.blondel/research/louvain.html
Référence wikipedia http://www.en.wikipedia.org/wiki.Community_structure
PubMed http://www.ncbi.nlm.nih.gov/pubmed
HAUT DE PAGECet article fait partie de l’offre
Documents numériques Gestion de contenu
(75 articles en ce moment)
Cette offre vous donne accès à :
Une base complète d’articles
Actualisée et enrichie d’articles validés par nos comités scientifiques
Des services
Un ensemble d'outils exclusifs en complément des ressources
Un Parcours Pratique
Opérationnel et didactique, pour garantir l'acquisition des compétences transverses
Doc & Quiz
Des articles interactifs avec des quiz, pour une lecture constructive