Egomunities, Exploring Socially Cohesive Person-based Communities

Adrien Friggeri 1 Guillaume Chelius 1 Eric Fleury 1, 2
1 DNET - Dynamic Networks
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Résumé : Ces dernières années, l'intérêt pour la détection de communautés recouvrante dans les réseaux réels s'est intensifié. Celles ci sont des groupes de nœuds possédant une forte densité interne et présentant une densité faible vers le reste du réseau. À ce jour, la majorité des méthodes utilisées pour calculer de telles communautés héritent de celles développées dans le domaine de la détection de communautés disjointes, ou bien en étendant le concept de modularité à un contexte recouvrant, ou bien en essayant de décomposer le réseau entier en plusieurs sous ensembles éventuellement recouvrant. Dans ce rapport, nous abordons la question de manière orthogonale en introduisant une mesure, la cohésion, reposant sur des considérations sociologiques. La cohésion permet de quantifier l'aspect communautaire d'un ensemble de nœuds à partir des notions de triangles -- triplets de nœuds interconnectés -- et de liens faibles, au lieu de la vision classique utilisant des arêtes. En substance, nous introduisons une caractérisation numérique des communautés: des ensembles de nœuds possédant une cohésion élevée. Nous présentons ensuite une nouvelle approche au problème des communautés recouvrantes en introduisant le concept d'ego-munauté: des communautés subjectives centrées sur un nœud donné, précisément incluses dans son voisinage. Nous utilisons la cohésion pour élaborer un algorithme heuristique construisant les ego-munautés d'un nœud en tentant de maximiser leur cohésion. Finalement, nous présentons des résultats préliminaires, sous la forme d'une description détaillé des ego-munautés d'amis Facebook d'une personne. Nous concluons en décrivant des applications prometteuses des ego-munautés, par exemple l'inférence d'information sur le sujet ou la recommandation de centre d'intérêt, et présentons une extension possible à la cohésion dans le cas de réseaux pondérés.
Type de document :
Rapport
[Research Report] RR-7535, INRIA. 2011
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00565336
Contributeur : Adrien Friggeri <>
Soumis le : samedi 19 février 2011 - 13:19:05
Dernière modification le : vendredi 20 avril 2018 - 15:44:26
Document(s) archivé(s) le : vendredi 20 mai 2011 - 02:26:13

Fichiers

RR-7535.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00565336, version 2
  • ARXIV : 1102.2623

Citation

Adrien Friggeri, Guillaume Chelius, Eric Fleury. Egomunities, Exploring Socially Cohesive Person-based Communities. [Research Report] RR-7535, INRIA. 2011. 〈inria-00565336v2〉

Partager

Métriques

Consultations de la notice

687

Téléchargements de fichiers

260