Show simple item record

dc.contributor.authorBecker, Ruben
dc.contributor.authorD'Angelo, Gianlorenzo
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorGilbert, Hugo
dc.subjectGraph algorithmsen
dc.subjectSocial networksen
dc.titleInfluence Maximization With Co-Existing Seedsen
dc.typeCommunication / Conférence
dc.description.abstractenIn the classical influence maximization problem we aim to select a set of nodes, called seeds, to start an efficient information diffusion process. More precisely, the goal is to select seeds such that the expected number of nodes reached by the diffusion process is maximized. In this work we study a variant of this problem where an unknown (up to a probability distribution) set of nodes, referred to as co-existing seeds, joins in starting the diffusion process even if not selected. This setting allows to model that, in certain situations, some nodes are willing to act as "voluntary seeds'' even if not chosen by the campaign organizer. This may for example be due to the positive nature of the information campaign (e.g., public health awareness programs, HIV prevention, financial aid programs), or due to external social driving effects (e.g., nodes are friends of selected seeds in real life or in other social media).In this setting, we study two types of optimization problems. While the first one aims to maximize the expected number of reached nodes, the second one endeavors to maximize the expected increment in the number of reached nodes in comparison to a non-intervention strategy. The problems (particularly the second one) are motivated by cooperative game theory. For various probability distributions on co-existing seeds, we obtain several algorithms with approximation guarantees as well as hardness and hardness of approximation results. We conclude with experiments that demonstrate the usefulness of our approach when co-existing seeds exist.en
dc.relation.ispartoftitleCIKM '21: The 30th ACM International Conference on Information and Knowledge Managementen
dc.relation.ispartofpublnameACM - Association for Computing Machineryen
dc.relation.ispartofpublcityNew York, NYen
dc.subject.ddclabelMéthodes informatiques spécialesen
dc.relation.conftitleCIKM '21: The 30th ACM International Conference on Information and Knowledge Managementen

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record