Présentation

Article

1 - TYPOLOGIE DES MÉTHODES DE DÉTECTION ET CRITÈRES DE QUALITÉ

2 - PRINCIPALES MÉTHODES DE PARTITIONNEMENT

  • 2.1 - Approche historique
  • 2.2 - Méthodes d'analyse de données
  • 2.3 - Méthodes spécifiques pour les graphes unipartis
  • 2.4 - Méthodes spécifiques pour les graphes bipartis
  • 2.5 - Méthodes unificatrices

3 - PRINCIPALES MÉTHODES DE DÉTECTION DE RECOUVREMENTS

4 - STABILITÉ DES COMMUNAUTÉS ET ÉQUILIBRE DE NASH

5 - EXPÉRIMENTATION

6 - DISCUSSION ET PROBLÈMES OUVERTS

  • 6.1 - Visualisation
  • 6.2 - Contraintes
  • 6.3 - Évolution
  • 6.4 - Conclusion

Article de référence | Réf : H7444 v1

Expérimentation
Détection de communautés

Auteur(s) : Michel CRAMPES, Michel PLANTIÉ

Date de publication : 10 mai 2014

Pour explorer cet article
Télécharger l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !

Sommaire

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’article

ABSTRACT

Detection community

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.

Cet article est réservé aux abonnés.
Il vous reste 95% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

KEYWORDS

community detection   |   overlaping communities   |   Nash equilibrium   |   sociology   |   statistics   |   data analysis   |   social networks

DOI (Digital Object Identifier)

https://doi.org/10.51257/a-v1-h7444


Cet article fait partie de l’offre

Documents numériques Gestion de contenu

(73 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

ABONNEZ-VOUS

Lecture en cours
Présentation

5. Expérimentation

Nous considérons ici quelques-unes des expérimentations menées avec la méthode d'unification présentée qui permet de considérer indifféremment des graphes unipartis, bipartis et orientés. Par ailleurs, l'application de l'algorithme de Louvain permet d'obtenir les résultats parmi les meilleurs et dans un temps très court à la fois sur des graphes binaires et pondérés. Pour certains graphes, on rajoute le recouvrement avec la fonction de légitimité. Finalement, nous étudions la stabilité de certaines communautés en prenant en compte la fonction de réaffectation et l'obtention de l'équilibre de Nash.

5.1 Graphes unipartis

Pour les graphes unipartis, de nombreux jeux de données sont disponibles allant de peu de sommets à des graphes comportant des millions de sommets. La partition de ces graphes ayant été très étudiée, seuls deux exemples sont présentés, sachant que Louvain apparaît souvent chez les auteurs comme la méthode la plus efficace et aux résultats en général les meilleurs .

Exemples

Louvain appliqué au graphe « karaté » produit quatre communautés (figure 7). Notre mesure de réaffectation ne montre aucune instabilité. C'est donc un équilibre de Nash. La modularité mesurée (0,473) est supérieure à celle de tous les autres algorithmes que nous connaissons. En particulier, elle est meilleure que celle déclarée chez les auteurs qui trouvent deux communautés (par exemple  avec l'analyse spectrale), ainsi que trois communautés ...

Cet article est réservé aux abonnés.
Il vous reste 95% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Documents numériques Gestion de contenu

(73 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

ABONNEZ-VOUS

Lecture en cours
Expérimentation
Sommaire
Sommaire

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)...

Cet article est réservé aux abonnés.
Il vous reste 94% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Documents numériques Gestion de contenu

(73 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

ABONNEZ-VOUS