Discovering small target sets in social networks: a fast and effective algorithm

DOI10.1007/S00453-017-0390-5MaRDI QIDQ1635708zbMATH OpenOpenAlexFDO

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

Publication date 1 June 2018

Published in Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

algorithmsinformation diffusionssocial networks

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Approximation methods and heuristics in mathematical programming (90C59) Social networks; opinion dynamics (91D30)

Abstract: Given a network represented by a graph $G=(V,E)$, we consider a dynamical process of influence diffusion in $G$ that evolves as follows: Initially only the nodes of a given $SsubseteqV$ are influenced; subsequently, at each round, the set of influenced nodes is augmented by all the nodes in the network that have a sufficiently large number of already influenced neighbors. The question is to determine a small subset of nodes $S$ (emph{a target set}) that can influence the whole network. This is a widely studied problem that abstracts many phenomena in the social, economic, biological, and physical sciences. It is known that the above optimization problem is hard to approximate within a factor of $2^{lo{g}^{1-epsilon}|V|}$, for any $epsilon>0$. In this paper, we present a fast and surprisingly simple algorithm that exhibits the following features: 1) when applied to trees, cycles, or complete graphs, it always produces an optimal solution (i.e, a minimum size target set); 2) when applied to arbitrary networks, it always produces a solution of cardinality which improves on the previously known upper bound; 3) when applied to real-life networks, it always produces solutions that substantially outperform the ones obtained by previously published algorithms (for which no proof of optimality or performance guarantee is known in any class of graphs).

Recommendations

• A fast and effective heuristic for discovering small target sets in social networks
• Fast and frugal targeting with incentives
• On the approximability of influence in social networks
• Maximizing social influence in nearly optimal time
• scientific article; zbMATH DE number 6474901

Cites work

• A fast and effective heuristic for discovering small target sets in social networks
• Automata, Languages and Programming
• Better approximation algorithms for influence maximization in online social networks
• Brief Announcement
• Combinatorial model and bounds for target set selection
• Constant thresholds can make target set selection tractable
• Contagious sets in expanders
• Dynamics of information systems: mathematical foundations.
• Evangelism in social networks
• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• scientific article; zbMATH DE number 1168330 (Why is no real title available?)
• Influence diffusion in social networks under time window constraints
• Irreversible conversion of graphs
• Latency-bounded target set selection in social networks
• Networks, crowds and markets. Reasoning about a highly connected world.
• On dynamic monopolies of graphs with general thresholds
• On the approximability of influence in social networks
• On tractable cases of target set selection
• Optimizing spread of influence in social networks via partial incentives
• Parameterized approximability of maximizing the spread of influence in networks
• Some results on the target set selection problem
• Spread of influence in weighted networks under time and budget constraints
• Target set selection problem for honeycomb networks
• Treewidth governs the complexity of target set selection
• Variants of spreading messages

Cited in

(17)

• Active influence spreading in social networks
• Deprecation based greedy strategy for target set selection in large scale social networks
• Optimizing node discovery on networks: problem definitions, fast algorithms, and observations
• Fast and frugal targeting with incentives
• Bounds and extremal graphs for degenerate subsets, dynamic monopolies, and partial incentives
• Latency-bounded target set selection in social networks
• A global optimization algorithm for target set selection problems
• Generalizations, formulations and subgradient based heuristic with dynamic programming procedure for target set selection problems
• A fast and effective heuristic for discovering small target sets in social networks
• Immunization in the threshold model: a parameterized complexity study
• Groups burning: analyzing spreading processes in community-based networks
• Target set selection with maximum activation time
• Graph burning in community-based networks
• More algorithmic results for problems of spread of influence in edge-weighted graphs with and without incentives more algorithmic results for problems of spread of influence
• Parameterized complexity of (d, r)-domination via modular decomposition
• On the complexity of reasoning about opinion diffusion under majority dynamics
• Optimal majority dynamics for the diffusion of an opinion when multiple alternatives are available

Describes a project that uses

Uses Software

• SNAP

This page was built for publication: Discovering small target sets in social networks: a fast and effective algorithm

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