Evangelism in social networks: algorithms and complexity

DOI10.1002/NET.21756zbMATH Open1396.91606arXiv1610.09486OpenAlexW2543981410MaRDI QIDQ4584867FDOQ4584867

Authors: Gennaro Cordasco, Adele A. Rescigno, Luisa Gargano, Ugo Vaccaro 

Publication date: 4 September 2018

Published in: Networks (Search for Journal in Brave)

Abstract: We consider a population of interconnected individuals that, with respect to a piece of information, at each time instant can be subdivided into three (time-dependent) categories: agnostics, influenced, and evangelists. A dynamical process of information diffusion evolves among the individuals of the population according to the following rules. Initially, all individuals are agnostic. Then, a set of people is chosen from the outside and convinced to start evangelizing, i.e., to start spreading the information. When a number of evangelists, greater than a given threshold, communicate with a node v, the node v becomes influenced, whereas, as soon as the individual v is contacted by a sufficiently much larger number of evangelists, it is itself converted into an evangelist and consequently it starts spreading the information. The question is: How to choose a bounded cardinality initial set of evangelists so as to maximize the final number of influenced individuals? We prove that the problem is hard to solve, even in an approximate sense. On the positive side, we present exact polynomial time algorithms for trees and complete graphs. For general graphs, we derive exact parameterized algorithms. We also investigate the problem when the objective is to select a minimum number of evangelists capable of influencing the whole network. Our motivations to study these problems come from the areas of Viral Marketing and the analysis of quantitative models of spreading of influence in social networks.

Full work available at URL: https://arxiv.org/abs/1610.09486

Recommendations

• Evangelism in social networks
• scientific article; zbMATH DE number 6474901
• On the approximability of influence in social networks
• Fast and frugal targeting with incentives
• A note on maximizing the spread of influence in social networks

zbMATH Keywords

social networkviral marketingparametrized complexityinfluence maximizationspread of influence

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30) Software, source code, etc. for problems pertaining to game theory, economics, and finance (91-04) Marketing, advertising (90B60)

Cited In (14)

• Pervasive domination
• Spanning trees with few branch vertices in graphs of bounded neighborhood diversity
• Spreading messages
• Active influence spreading in social networks
• Getting linear time in graphs of bounded neighborhood diversity
• Dual domination problems in graphs
• Evangelism in social networks
• Spreading Messages
• Parameterized complexity of immunization in the threshold model
• Immunization in the threshold model: a parameterized complexity study
• Graph burning in community-based networks
• Iterated Type Partitions
• Groups burning: analyzing spreading processes in community-based networks
• Parameterized complexity for iterated type partitions and modular-width

This page was built for publication: Evangelism in social networks: algorithms and complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4584867)