Hardness Results for Seeding Complex Contagion with Neighborhoods

DOI10.1007/978-3-030-93413-2_18MaRDI QIDQ5050309zbMATH OpenOpenAlexFDO

Authors Meher Chaitanya, Ulrik Brandes

Publication date 15 November 2022

Published in Complex Networks & Their Applications X (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-93413-2_18

zbMATH Keywords

complex contagioncomputational complexitysocial influence

Mathematics Subject Classification ID

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

Recommendations

• Containing viral spread on sparse random graphs: bounds, algorithms, and experiments
• Contagion spreading on complex networks with local deterministic dynamics
• Finding the probability of infection in an SIR network is NP-hard
• Contagion in simplicial complexes
• Complex contagions on configuration model graphs with a power-law degree distribution
• Contagions in random networks with overlapping communities

Cites work

• An analysis of approximations for maximizing submodular set functions—I
• Automata, Languages and Programming
• Constant thresholds can make target set selection tractable
• Hardness results and approximation algorithms of \(k\)-tuple domination in graphs
• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• scientific article; zbMATH DE number 5764908 (Why is no real title available?)
• scientific article; zbMATH DE number 1954391 (Why is no real title available?)
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Local majorities, coalitions and monopolies in graphs: A review
• New bounds for contagious sets
• On approximating target set selection
• On the possibility of faster \textsc{SAT} algorithms
• Social influence network theory. A sociological examination of small group dynamics.

Cited in

(1)

• Sticky seeding in discrete-time reversible-threshold networks

This page was built for publication: Hardness Results for Seeding Complex Contagion with Neighborhoods

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