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

DOI10.1007/s00453-017-0390-5zbMath1390.05224arXiv1610.03721OpenAlexW2537739985MaRDI QIDQ1635708

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

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

algorithmssocial networksinformation diffusions

Mathematics Subject Classification ID

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

Related Items

Optimal majority dynamics for the diffusion of an opinion when multiple alternatives are available, Generalizations, formulations and subgradient based heuristic with dynamic programming procedure for target set selection problems, Immunization in the threshold model: a parameterized complexity study, Bounds and extremal graphs for degenerate subsets, dynamic monopolies, and partial incentives, Groups burning: analyzing spreading processes in community-based networks, Target set selection with maximum activation time, Active influence spreading in social networks, On the complexity of reasoning about opinion diffusion under majority dynamics

Uses Software

• SNAP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On dynamic monopolies of graphs with general thresholds
• Combinatorial model and bounds for target set selection
• Dynamics of information systems: mathematical foundations.
• Treewidth governs the complexity of target set selection
• Irreversible conversion of graphs
• Some results on the target set selection problem
• Parameterized approximability of maximizing the spread of influence in networks
• Constant thresholds can make target set selection tractable
• Influence diffusion in social networks under time window constraints
• Spread of influence in weighted networks under time and budget constraints
• Better approximation algorithms for influence maximization in online social networks
• Latency-bounded target set selection in social networks
• Evangelism in Social Networks
• On Tractable Cases of Target Set Selection
• Optimizing Spread of Influence in Social Networks via Partial Incentives
• A Fast and Effective Heuristic for Discovering Small Target Sets in Social Networks
• On the Approximability of Influence in Social Networks
• Target Set Selection Problem for Honeycomb Networks
• Brief Announcement
• Contagious Sets in Expanders
• Automata, Languages and Programming
• Variants of Spreading Messages