Algorithme décentralisé pour déterminer les nœuds influents dans les réseaux sociaux

13

Dans cet article de Kempe-Kleinberg-Tardos, les auteurs proposent des algorithmes gourmands basés sur des fonctions sous-modulaires pour déterminer les nœuds les plus influents d'un graphe, avec des applications aux réseaux sociaux.k

Fondamentalement, l'algorithme se présente comme suit:

  1. S=empty set
  2. choisissez le nœud avec l'influence individuelle la plus élevée, appelez-le ; S = S v 1v1S=Sv1
  3. supprimer et tous les bords connectant v 1 au reste du réseauv1v1
  4. répéter jusqu'à ce que ait k sommetsSk

J'ai deux questions sur les nœuds influents des réseaux sociaux.
a) Existe-t-il un algorithme pour trouver la solution, ou une approximation de celle-ci de manière décentralisée?
b) Quelqu'un a-t-il appliqué d'autres algorithmes, tels que Page-Rank et similaires, pour résoudre le même problème?

Bob
la source
Comment définissez-vous un nœud "influent"?
Timothy Sun, le
2
selon l'article, chaque lien est défini avec une probabilité de transmettre avec succès un message d'un nœud à un autre. L'objectif est de trouver le sous-ensemble de nœuds qui délivrera un message au plus grand nombre de nœuds, sur attente.
Bob
kk=1
Je comprends que. Ma préoccupation était de savoir s'il existe, au moins, un algorithme sous-optimal pour approximer la solution optimale.
Bob

Réponses: