Une approche basée sur la valeur de Shapley pour découvrir des nœuds influents dans les réseaux sociaux

Notre étude concerne un problème actuel important, celui de la diffusion de l'information dans les réseaux sociaux. Ce problème a reçu une attention significative de la part de la communauté de recherche Internet ces derniers temps, driven par de nombreuses applications potentielles telles que le marketing viral et les promotions de vente. Dans cet article, nous nous concentrons sur le problème de sélection d'un ensemble cible, qui implique de découvrir un petit sous-ensemble de joueurs influents dans un réseau social donné, pour effectuer une certaine tâche de diffusion d'information. Le problème de sélection de l'ensemble cible se manifeste sous deux formes : 1) le problème des nœuds top-k et 2) le problème de couverture λ. Dans le problème des nœuds top-k, nous devons trouver un ensemble de k nœuds clés qui maximisera le nombre de nœuds influencés dans le réseau. Le problème de couverture λ concerne la recherche d'un ensemble de nœuds clés de taille minimale pouvant influencer un pourcentage donné λ des nœuds dans l'ensemble du réseau. Nous proposons une nouvelle manière de résoudre ces problèmes en utilisant le concept de valeur de Shapley, qui est un concept de solution bien connu en théorie des jeux coopératifs. Notre approche mène à des algorithmes que nous appelons les algorithmes de Nœuds influents basés sur la valeur de Shapley (SPINs) pour résoudre le problème des nœuds top-k et le problème de couverture λ. Nous comparons la performance des algorithmes SPIN proposés avec des algorithmes bien connus dans la littérature. À travers une expérimentation extensive sur quatre graphes aléatoires générés de manière synthétique et six ensembles de données réelles (Celegans, Jazz, ensemble de données de co-auteurs NIPS, ensemble de données Netscience, ensemble de données en physique des hautes énergies, et ensemble de données de livres politiques), nous montrons que l'approche SPIN proposée est plus puissante et économiquement efficace.