How to Network in Online Social Networks

Résumé : Dans ce papier, on évalue comment maximiser l'influence des utilisateurs dans les réseaux sociaux. En particulier, on étudie comment les liens sociaux modifient l'influence dans les réseaux sociaux dirigés (comme Twitter) et non dirigés (comme Facebook). Cette étude introduit trois différences par rapport au problème classique de maximisation introduit dans [5], où K utilisateurs influents sont sélectionnés. Premièrement, si un utilisateur suit ou propose une relation d'amitié à l'utilisateur le plus influent, il n'y a aucune garantie que l'utilisateur le plus influent accepte la relation, c'est-à-dire qu'il y ait réciprocité. Deuxièmement, créer une relation de suivi ou d'amitié est peu coûteux dans les réseaux sociaux, par conséquent, les utilisateurs peuvent facilement changer leurs relations. Troisièmement, on quantifie l'influence non seulement par le nombre d'utilisateurs qui peuvent répliquer une information, mais aussi par le nombre d'utilisateurs qui reçoivent cette information. On montre qu'en dépit de ces trois différences, les algorithmes gloutons conduisent aux mêmes résultats théoriques que dans le problème standard de maximisation de l'influence, c'est-à-dire qu'ils atteignent un facteur d'approximation (1 − 1/e). Ces algorithmes gloutons ont besoin de la connaissance de toute la topologie et sont coûteux à cause de l'évaluation de l'effet d'une cascade. On montre avec des simulations sur le graphe social complet de Twitter que des heuristiques simples ont une efficacité proche d'un algorithme glouton. Par exemple, en connaissant simplement le degré di et la probabilité de réciprocité ri de chaque nœud i, la stratégie qui choisit les nœuds avec le plus grand produit ridi est seulement au plus 2% moins efficace qu'un algorithme glouton. De plus, la stratégie qui consiste à simplement choisir les nœuds au hasard obtient des performances similaires quand la probabilité de réplication de l'information pour le processus de cascade est de 1%.
Type de document :
Rapport
[Research Report] RR-8423, INRIA. 2013
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00917974
Contributeur : Maksym Gabielkov <>
Soumis le : vendredi 17 janvier 2014 - 11:23:41
Dernière modification le : jeudi 11 janvier 2018 - 16:58:52
Document(s) archivé(s) le : vendredi 18 avril 2014 - 11:27:31

Fichier

HowToNetworkInOnlineSocialNetw...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00917974, version 2

Collections

Citation

Giovanni Neglia, Xiuhui Ye, Maksym Gabielkov, Arnaud Legout. How to Network in Online Social Networks. [Research Report] RR-8423, INRIA. 2013. 〈hal-00917974v2〉

Partager

Métriques

Consultations de la notice

500

Téléchargements de fichiers

203