MATI: An efficient algorithm for influence maximization in social networks

Abstract : Influence maximization has attracted a lot of attention due to its numerous applications, including diffusion of social movements, the spread of news, viral marketing and outbreak of diseases. The objective is to discover a group of users that are able to maximize the spread of influence across a network. The greedy algorithm gives a solution to the Influence Maxi-mization problem while having a good approximation ratio. Nevertheless it does not scale well for large scale datasets. In this paper, we propose Matrix Influence, MATI, an efficient algorithm that can be used under both the Linear Threshold and Independent Cascade diffusion models. MATI is based on the precalculation of the influence by taking advantage of the simple paths in the node's neighborhood. An extensive empirical analysis has been performed on multiple real-world datasets showing that MATI has competitive performance when compared to other well-known algorithms with regards to running time and expected influence spread.
Type de document :
Article dans une revue
PLoS ONE, Public Library of Science, 2018
Liste complète des métadonnées

https://hal-centralesupelec.archives-ouvertes.fr/hal-01950273
Contributeur : Fragkiskos Malliaros <>
Soumis le : lundi 10 décembre 2018 - 16:26:02
Dernière modification le : jeudi 7 février 2019 - 15:37:56

Fichier

MATI_Plos_One_2018.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01950273, version 1

Citation

Maria Evgenia G. Rossi, Bowen Shi, Nikolaos Tziortziotis, Fragkiskos Malliaros, Christos Giatsidis, et al.. MATI: An efficient algorithm for influence maximization in social networks. PLoS ONE, Public Library of Science, 2018. 〈hal-01950273〉

Partager

Métriques

Consultations de la notice

48

Téléchargements de fichiers

24