Perturb and Combine to Identify Influential Spreaders in Real-World Networks - CentraleSupélec Accéder directement au contenu
Communication Dans Un Congrès Année : 2019

Perturb and Combine to Identify Influential Spreaders in Real-World Networks

Résumé

Graph degeneracy algorithms were recently shown to be very effective at detecting the influential spreaders in a network. However, degeneracy-based decompositions of a graph are unstable to small perturbations of the network structure. At the same time, it is well-known in Machine Learning that the performance of unstable algorithms can be greatly improved by using Perturb and Combine (P&C) strategies. Motivated by these observations, we propose a P&C procedure for networks that (1) creates many perturbed versions of a given graph, (2) applies the same algorithm separately to each graph, and (3) combines the results. Experiments conducted on benchmark datasets of real-world networks reveal that our strategy improves the performance of all algorithms tested. Moreover, this performance boost can be obtained at almost no extra cost through parallelization. We finally provide insights as to why our strategy is effective from a theoretical perspective. To the best of our knowledge, this work is the first application of P&C to networks.
Fichier principal
Vignette du fichier
P&C_Manuscript.pdf (310.49 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01958973 , version 1 (18-12-2018)

Identifiants

  • HAL Id : hal-01958973 , version 1

Citer

Antoine Jean-Pierre Tixier, Maria Evgenia G. Rossi, Fragkiskos Malliaros, Jesse Read, Michalis Vazirgiannis. Perturb and Combine to Identify Influential Spreaders in Real-World Networks. ASONAM 2019 - IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, Aug 2019, Vancouver, Canada. ⟨hal-01958973⟩
124 Consultations
111 Téléchargements

Partager

Gmail Facebook X LinkedIn More