Loading...
Reload document 
Open in new tab Triangles to Capture Social Cohesion
Adrien Friggeri, Guillaume Chelius, Eric Fleury
To cite this version:
Adrien Friggeri, Guillaume Chelius, Eric Fleury. Triangles to Capture Social Cohesion.
Report] RR-7686, INRIA. 2011. _xFFFF_inria-00608889_xFFFF_
[Research
HAL Id: inria-00608889
https://hal.inria.fr/inria-00608889
Submitted on 15 Jul 2011
HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.
L’archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d’enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
INSTITUT NATIONAL DE RECHERCHE EN INFORMATIQUE ET EN AUTOMATIQUE
Triangles to Capture Social Cohesion
Adrien Friggeri — Guillaume Chelius — Eric Fleury
N° 7686
8 July 2011
a p p o r t (cid:13)
(cid:13)d e r e c h e r c h e (cid:13)
G
N
E
+
R
F
–
–
6
8
6
7
–
–
/
R
R
A
R
N
I
I
N
R
S
I
9
9
3
6
–
9
4
2
0
N
S
S
I
Triangles to Capture Social Cohesion
Adrien Friggeri , Guillaume Chelius , Eric Fleury
Th`eme : R´eseaux et t´el´ecommunications
´Equipe-Projet DNET
Rapport de recherche n° 7686 — 8 July 2011 — 16 pages
Abstract: Although community detection has drawn tremendous amount of
attention across the sciences in the past decades, no formal consensus has been
reached on the very nature of what qualifies a community as such. In this arti-
cle we take an orthogonal approach by introducing a novel point of view to the
problem of overlapping communities. Instead of quantifying the quality of a set
of communities, we choose to focus on the intrinsic community-ness of one given
set of nodes. To do so, we propose a general metric on graphs, the cohesion,
based on counting triangles and inspired by well established sociological consid-
erations. The model has been validated through a large-scale online experiment
called Fellows in which users were able to compute their social groups on Face-
book and rate the quality of the obtained groups. By observing those ratings
in relation to the cohesion we assess that the cohesion is a strong indicator of
users subjective perception of the community-ness of a set of people.
Key-words: No keywords
Centre de recherche INRIA Grenoble – Rhône-Alpes
655, avenue de l’Europe, 38334 Montbonnot Saint Ismier
Téléphone : +33 4 76 61 52 00 — Télécopie +33 4 76 61 52 52
Des Triangles pour Capturer la Coh´esion Sociale
R´esum´e : Bien que la probl´ematique de d´etection de communaut´es dans les
r´eseaux sociaux ait attir´e une attention grandissante `a travers les sciences ces
derni`eres ann´ees, aucun consensus formel n’a ´et´e atteint sur la nature de ce qui
d´efinit une communaut´e. Nous introduisons ici un point de vue novateur au
probl`eme de communaut´es recouvrantes. Au lieu de quantifier la qualit´e d’un
ensemble de communaut´es, nous nous concentrons sur l’aspect intrins`equement
communautaire d’un ensemble donn´e de nuds. Pour ce faire, nous proposons
une m´etrique g´en´erique sur les graphes, la coh´esion, se fondant sur la notion
de triangles et inspir´ee par des r´esultats ´etablis en sociologie. Ce mod`ele a
´et´e valid´e `a travers Fellows, une exp´erience `a large ´echelle sur Facebook dans
laquelle les utilisateurs avaient la possibilit´e de calculer de mani`ere automatique
leurs groupes d’amis puis de noter la qualit´e de ceux ci. En observant ces notes
et la coh´esion des groupes obtenus, nous concluons que la coh´esion est une bonne
´evaluation de la perception subjective de l’aspect communautaire d’un ensemble
de nœuds par un utilisateur.
Mots-cl´es :
communaut´es, communaut´es recouvrantes, data mining, mod´elisation
r´eseaux sociaux, r´eseaux complexes, graphes r´eels, d´etection de