On non-progressive spread of influence through social networks

DOI10.1016/j.tcs.2014.07.009zbMath1360.91120OpenAlexW2086228055MaRDI QIDQ401306

Pooya Jalaly, Jafar Habibi, Mohammad Ghodsi, Sina Sadeghian, Mohammad Amin Fazli, Vahab S. Mirrokni

Publication date: 26 August 2014

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.07.009

zbMATH Keywords

approximation algorithmsNP-hardnessMinPTS problemnon-progressivespread of influence

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (4)

Dynamic monopolies in two-way bootstrap percolation ⋮ Majority rule cellular automata ⋮ Color War: Cellular Automata with Majority-Rule ⋮ On the complexity of reasoning about opinion diffusion under majority dynamics

Uses Software

• plfit

Cites Work

• Unnamed Item
• Unnamed Item
• Combinatorial model and bounds for target set selection
• On domination and independent domination numbers of a graph
• Spreading messages
• Periodic behaviour of generalized threshold functions
• Size bounds for dynamic monopolies
• The statistical mechanics of strategic interaction
• Dynamic monopolies in tori.
• Local majorities, coalitions and monopolies in graphs: A review
• On time versus size for monotone dynamic monopolies in regular topologies
• Dynamic monopolies of constant size
• On reversible cascades in scale-free and Erdős-Rényi random graphs
• Learning, Local Interaction, and Coordination
• A random graph model for massive graphs
• Power-Law Distributions in Empirical Data
• Probability Inequalities for Sums of Bounded Random Variables
• Decycling Cartesian Products of Two Cycles
• Optimal irreversible dynamos in chordal rings

This page was built for publication: On non-progressive spread of influence through social networks