Coefficient de Clustering d'intérêt : une nouvelle métrique pour les graphes dirigés comme Twitter - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2020

Coefficient de Clustering d'intérêt : une nouvelle métrique pour les graphes dirigés comme Twitter

Résumé

Nous étudions dans ce papier le coefficient de clustering de graphes sociaux dirigés. Le coefficient de clustering a eté introduit pour capturer le phénomène social selon lequel les amis de mes amis sont mes amis, et a été largement étudié depuis, se montrant d'un grand intérêt pour décrire les caractéristiques sociales d'un graphe. Cependant, ce paramètre est adapté pour un graphe dans lequel les liens ne sont pas orientés, comme les liens d'amitiés (Facebook) ou les liens professionnels (LinkedIn), mais devient inadapté pour un graphe dans lequel les liens sont dirigés d'une source d'informations vers un consommateur d'informations. Nous montrons que les études précédentes ont manqué une grande partie des informations contenues dans la partie dirigée de ces graphes. Dans ce papier, nous introduisons une nouvelle métrique pour mesurer le clustering d'un graphe social orienté avec des liens d'intérêt, que l'on nomme le coefficient de clustering d'intérêt. Nous calculons sa valeur, exactement et à l'aide de méthodes d'échantillonnage, sur un graphe de Twitter comprenant 505 millions de nœuds et 23 milliards d'arêtes. Nous mesurons en outre les valeurs des coefficients de clustering dirigés et non dirigés précédemment introduits dans la littérature, une première sur un si grand graphe. Nous montrons que le coefficient de clustering d'intérêt est plus grand que les coefficients de clustering dirigés classiques. Cela montre la pertinence de cette nouvelle métrique pour capturer l'aspect informatif des graphes dirigés.
Fichier principal
Vignette du fichier
Coefficient_de_Clustering_d_Interet.pdf (114.96 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02872779 , version 1 (17-06-2020)

Identifiants

  • HAL Id : hal-02872779 , version 1

Citer

Thibaud Trolliet, Nathann Cohen, Frédéric Giroire, Luc Hogie, Stéphane Pérennes. Coefficient de Clustering d'intérêt : une nouvelle métrique pour les graphes dirigés comme Twitter. ALGOTEL 2020 – 22èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Sep 2020, Lyon, France. ⟨hal-02872779⟩
131 Consultations
304 Téléchargements

Partager

Gmail Facebook X LinkedIn More