Latency-bounded target set selection in social networks

DOI10.1016/j.tcs.2014.02.027zbMath1358.05272arXiv1303.6785OpenAlexW1794474033MaRDI QIDQ2447759

Martin Milanič, Luisa Gargano, Ferdinando Cicalese, Gennaro Cordasco, Ugo Vaccaro

Publication date: 29 April 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

target set selectionmonotone irreversible dynamic monopolies

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Social networks; opinion dynamics (91D30) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (21)

Discovering small target sets in social networks: a fast and effective algorithm ⋮ Target Set Selection in Dense Graph Classes ⋮ Optimizing Spread of Influence in Social Networks via Partial Incentives ⋮ A Fast and Effective Heuristic for Discovering Small Target Sets in Social Networks ⋮ Generalized threshold processes on graphs ⋮ Establishing herd immunity is hard even in simple geometric networks ⋮ Groups burning: analyzing spreading processes in community-based networks ⋮ Graph classes with and without powers of bounded clique-width ⋮ Target set selection with maximum activation time ⋮ Domination and convexity problems in the target set selection model ⋮ Multi-level dynamo and opinion spreading ⋮ Active influence spreading in social networks ⋮ Subexponential fixed-parameter algorithms for partial vector domination ⋮ Approximation algorithms for highly connected multi-dominating sets in unit disk graphs ⋮ The \(t\)-latency bounded strong target set selection problem in some kinds of special family of graphs ⋮ Vector domination in split-indifference graphs ⋮ Whom to befriend to influence people ⋮ Evangelism in Social Networks ⋮ Target set selection parameterized by vertex cover and more ⋮ New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs ⋮ Spread of influence in weighted networks under time and budget constraints

Cites Work

• Unnamed Item
• Unnamed Item
• On dynamic monopolies of graphs with general thresholds
• Combinatorial model and bounds for target set selection
• Treewidth governs the complexity of target set selection
• Irreversible conversion of graphs
• On bounded-degree vertex deletion parameterized by treewidth
• Local majorities, coalitions and monopolies in graphs: A review
• On time versus size for monotone dynamic monopolies in regular topologies
• Edge dominating set and colorings on graphs with fixed clique-width
• Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
• On the approximability and exact algorithms for vector domination and related problems in graphs
• Some results on the target set selection problem
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Counting truth assignments of formulas of bounded tree-width or clique-width
• Approximating clique-width and branch-width
• Influence Diffusion in Social Networks under Time Window Constraints
• Exact Algorithms for a Loading Problem with Bounded Clique Width
• Intractability of Clique-Width Parameterizations
• On the Approximability of Influence in Social Networks
• Constant Thresholds Can Make Target Set Selection Tractable
• Parameterized Approximability of Maximizing the Spread of Influence in Networks
• Minimum Weight Dynamo and Fast Opinion Spreading
• Target Set Selection Problem for Honeycomb Networks
• On the Relationship Between Clique-Width and Treewidth
• Contagious Sets in Expanders
• Computing the Tutte Polynomial on Graphs of Bounded Clique‐Width
• Automata, Languages and Programming
• Variants of Spreading Messages
• Finding Branch-Decompositions and Rank-Decompositions

This page was built for publication: Latency-bounded target set selection in social networks