On the complexity of reasoning about opinion diffusion under majority dynamics
From MaRDI portal
Publication:785234
DOI10.1016/j.artint.2020.103288zbMath1454.91154OpenAlexW3019892117MaRDI QIDQ785234
Vincenzo Auletta, Diodato Ferraioli, Gianluigi Greco
Publication date: 6 August 2020
Published in: Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.artint.2020.103288
Social networks; opinion dynamics (91D30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Optimal majority dynamics for the diffusion of an opinion when multiple alternatives are available, Opinion evolution among friends and foes: the deterministic majority rule, Biased opinion dynamics: when the devil is in the details, Predicting voting outcomes in the presence of communities, echo chambers and multiple parties
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A study of monopolies in graphs
- On non-progressive spread of influence through social networks
- Combinatorial model and bounds for target set selection
- New bounds for contagious sets
- On dynamic monopolies of graphs: the average and strict majority thresholds
- Treewidth governs the complexity of target set selection
- Graph minors. III. Planar tree-width
- On the global offensive alliance number of a graph
- Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
- Periodic behaviour of generalized threshold functions
- Size bounds for dynamic monopolies
- Local majorities, coalitions and monopolies in graphs: A review
- Discovering small target sets in social networks: a fast and effective algorithm
- Stability in binary opinion diffusion
- On discrete preferences and coordination
- On time versus size for monotone dynamic monopolies in regular topologies
- Bounding the sizes of dynamic monopolies and convergent sets for threshold-based cascades
- Parameterized approximability of maximizing the spread of influence in networks
- Empathetic decision making in social networks
- Spread of influence in weighted networks under time and budget constraints
- Irreversible conversion processes with deadlines
- Local tree-width, excluded minors, and approximation algorithms
- Convergence in (Social) Influence Networks
- Reaching Consensus via non-Bayesian Asynchronous Learning in Social Networks
- ON THE CONSENSUS THRESHOLD FOR THE OPINION DYNAMICS OF KRAUSE–HEGSELMANN
- Easy problems for tree-decomposable graphs
- Minority Becomes Majority in Social Networks
- ABOUT THE POWER TO ENFORCE AND PREVENT CONSENSUS BY MANIPULATING COMMUNICATION RULES
- On the Approximability of Influence in Social Networks
- Graph minors. II. Algorithmic aspects of tree-width
- Approximation algorithms for NP-complete problems on planar graphs
- Information Retention in Heterogeneous Majority Dynamics
- Reaching a Consensus
- An Experimental Study of the Treewidth of Real-World Graph Data
- Parameterized Inapproximability of Target Set Selection and Generalizations
- Handbook of Computational Social Choice
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Term Rewriting and Applications
- Automata, Languages and Programming
