Irreversible $k$-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion

DOI10.1016/j.dam.2008.09.012zbMath1163.92035OpenAlexW2008080404MaRDI QIDQ1028139

Fred S. Roberts, Paul A. jun. Dreyer

Publication date: 30 June 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.09.012

zbMATH Keywords

social network threshold models spread of disease firefighter problem spread of opinion

Mathematics Subject Classification ID

Epidemiology (92D30) Social networks; opinion dynamics (91D30) Applications of graph theory (05C90) Graph algorithms (graph-theoretic aspects) (05C85) Computational methods for problems pertaining to biology (92-08)

Related Items

A polynomial time algorithm for geodetic hull number for complementary prisms ⋮ Complexity aspects of the triangle path convexity ⋮ The maximum infection time of the $P_3$ convexity in graphs with bounded maximum degree ⋮ Unnamed Item ⋮ Hardness Results for Seeding Complex Contagion with Neighborhoods ⋮ On the $P_3$-hull number of some products of graphs ⋮ Max-linear models in random environment ⋮ Vaccinate your trees! ⋮ Target Set Selection in Dense Graph Classes ⋮ Complexity of determining the maximum infection time in the geodetic convexity ⋮ Diffusion in large networks ⋮ On the harmless set problem parameterized by treewidth ⋮ Sharp thresholds for contagious sets in random graphs ⋮ Least cost influence propagation in (social) networks ⋮ The time of bootstrap percolation with dense initial sets for all thresholds ⋮ Multi-color forcing in graphs ⋮ Algorithmic and structural aspects of the $P_3$-Radon number ⋮ Generalized threshold processes on graphs ⋮ Harmless sets in sparse classes ⋮ ON DYNAMIC MONOPOLIES OF GRAPHS WITH PROBABILISTIC THRESHOLDS ⋮ A study of monopolies in graphs ⋮ Generalizations, formulations and subgradient based heuristic with dynamic programming procedure for target set selection problems ⋮ The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results ⋮ Extremal $k$-forcing sets in oriented graphs ⋮ Dynamic monopolies in two-way bootstrap percolation ⋮ Irreversible $k$-threshold conversion number of circulant graphs ⋮ The maximum time of 2-neighbor bootstrap percolation: complexity results ⋮ Non-monotone target sets for threshold values restricted to $0$, $1$, and the vertex degree ⋮ Establishing herd immunity is hard even in simple geometric networks ⋮ New computational approaches for the power dominating set problem: Set covering and the neighborhoods of zero forcing forts ⋮ On dynamic monopolies of graphs with general thresholds ⋮ On the running time of hypergraph bootstrap percolation ⋮ Target set selection with maximum activation time ⋮ Convex Independence in Permutation Graphs ⋮ The maximum infection time in the geodesic and monophonic convexities ⋮ Complexity analysis of $P_3$-convexity problems on bounded-degree and planar graphs ⋮ Solving target set selection with bounded thresholds faster than $2^n$ ⋮ Efficient presolving methods for the influence maximization problem ⋮ Hierarchical cycle-tree packing model for optimal $K$-core attack ⋮ Target set selection on generalized pancake graphs ⋮ Approximability of the firefighter problem. Computing cuts over time ⋮ Dynamic monopolies and feedback vertex sets in hexagonal grids ⋮ Triggering cascades on undirected connected graphs ⋮ Bootstrap percolation in random geometric graphs ⋮ Irreversible k-threshold conversion number of some graphs ⋮ UNCERTAINTY VISUALIZATION FOR CHARACTERIZING HETEROGENEOUS HUMAN BEHAVIORS IN DISCRETE DYNAMICAL SYSTEM MODELS ⋮ Modeling the spread of fault in majority-based network systems: dynamic monopolies in triangular grids ⋮ On reversible cascades in scale-free and Erdős-Rényi random graphs ⋮ The firefighter problem with more than one firefighter on trees ⋮ The P3 infection time is W[1-hard parameterized by the treewidth] ⋮ Computing the hull number in $\Delta $-convexity ⋮ On $\alpha $-domination in graphs ⋮ An upper bound on the $P_3$-Radon number ⋮ Inhibiting diffusion of complex contagions in social networks: theoretical and experimental results ⋮ Some results on the target set selection problem ⋮ On dynamic monopolies of graphs: the average and strict majority thresholds ⋮ Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs ⋮ Irreversible conversion processes with deadlines ⋮ On the geodetic number of complementary prisms ⋮ Dynamic monopolies in directed graphs: the spread of unilateral influence in social networks ⋮ Computing the $\mathcal{P}_3$-hull number of a graph, a polyhedral approach ⋮ Zero forcing in iterated line digraphs ⋮ Upper bounds on the $k$-forcing number of a graph ⋮ The sharp threshold for bootstrap percolation in all dimensions ⋮ The zero forcing polynomial of a graph ⋮ Target set selection for conservative populations ⋮ Dynamic monopolies for interval graphs with bounded thresholds ⋮ Triggering cascades on strongly connected directed graphs ⋮ Solving Target Set Selection with Bounded Thresholds Faster than 2^n ⋮ Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees ⋮ A computational study of $f$-reversible processes on graphs ⋮ Parameterized approximability of maximizing the spread of influence in networks ⋮ Reversible iterative graph processes ⋮ Constant thresholds can make target set selection tractable ⋮ On some tractable and hard instances for partial incentives and target set selection ⋮ Irreversible conversion of graphs ⋮ Complexity and computation of connected zero forcing ⋮ Large-scale influence maximization via maximal covering location ⋮ Vector domination in split-indifference graphs ⋮ A lower bound on the $k$-conversion number of graphs of maximum degree $k+1$ ⋮ Dynamic monopolies and feedback vertex sets in cycle permutation graphs, generalized Petersen graphs and torus cordalis ⋮ The k-conversion number of regular graphs ⋮ Whom to befriend to influence people ⋮ Partial immunization of trees ⋮ The Maximum Time of 2-neighbour Bootstrap Percolation in Grid Graphs and Parametrized Results ⋮ Strict Majority Bootstrap Percolation on Augmented Tori and Random Regular Graphs: Experimental Results ⋮ On the complexity of reasoning about opinion diffusion under majority dynamics ⋮ The complexity of finding harmless individuals in social networks ⋮ Remarks on k-Clique, k-Independent Set and 2-Contamination in Complementary Prisms ⋮ The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects ⋮ Spread of influence in weighted networks under time and budget constraints ⋮ On irreversible spread of influence in edge-weighted graphs ⋮ Minimal contagious sets in random regular graphs ⋮ On reconfigurability of target sets

Cites Work

Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion