Show simple item record

Influence Maximization With Co-Existing Seeds

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.date.accessioned2022-02-22T11:23:45Z
dc.date.available2022-02-22T11:23:45Z
dc.date.issued2021
dc.identifier.urihttps://basepub.dauphine.psl.eu/handle/123456789/22700
dc.language.isoenen
dc.subjectGraph algorithmsen
dc.subjectSocial networksen
dc.subject.ddc006en
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.identifier.citationpages100–109en
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.identifier.urlsitehttps://hal.archives-ouvertes.fr/hal-03501078en
dc.subject.ddclabelMéthodes informatiques spécialesen
dc.relation.ispartofisbn978-1-4503-8446-9en
dc.relation.conftitleCIKM '21: The 30th ACM International Conference on Information and Knowledge Managementen
dc.relation.confdate2021-11
dc.relation.confcityQueenslanden
dc.relation.confcountryAustraliaen
dc.relation.forthcomingnonen
dc.identifier.doi10.1145/3459637.3482439en
dc.description.ssrncandidatenon
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2022-02-22T11:22:09Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record