On the spread of influence in graphs

DOI10.1016/J.IC.2021.104808MaRDI QIDQ2051833zbMATH OpenOpenAlexFDO

Authors Ahad N. Zehmakan

Publication date 25 November 2021

Published in Information and Computation (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.ic.2021.104808

zbMATH Keywords

opinion dynamicstarget set selectionbootstrap percolationthreshold modeldynamic monopolypercolating set

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• On dynamic monopolies of graphs with probabilistic thresholds
• On dynamic monopolies of graphs with general thresholds
• On dynamic monopolies of graphs: the average and strict majority thresholds
• Tight bounds on the minimum size of a dynamic monopoly
• Weak dynamic monopolies in social graphs

Cites work

• A proof of alon's second eigenvalue conjecture
• Bootstrap percolation in power-law random graphs
• Bootstrap percolation on the random graph \(G_{n,p}\)
• Concentration and regularization of random graphs
• Concentration of Measure for the Analysis of Randomized Algorithms
• Contagious sets in a degree-proportional bootstrap percolation process
• Contagious sets in expanders
• Contagious sets in random graphs
• Dynamic monopolies in two-way bootstrap percolation
• Dynamic monopolies of constant size
• Expander graphs and their applications
• Extremal bounds for bootstrap percolation in the hypercube
• Immunity against local influence
• Largest minimal percolating sets in hypercubes under 2-bootstrap percolation
• Majority dynamics on trees and the dynamic cavity method
• Majority model on random regular graphs
• Minimal contagious sets in random regular graphs
• Minimum degree conditions for small percolating sets in bootstrap percolation
• New bounds for contagious sets
• On the behavior of some cellular automata related to bootstrap percolation
• Opinion forming in Erdős-Rényi random graph and expanders
• Periodic behaviour of generalized threshold functions
• Pulse vaccination strategy in the SIR epidemic model
• Random disease on the square grid
• Random majority percolation
• Size bounds for dynamic monopolies
• Threshold behavior of bootstrap percolation
• Tight bounds for rumor spreading in graphs of a given conductance
• Transient length in sequential iteration of threshold functions
• Triggering cascades on undirected connected graphs

Cited in

(10)

• Tight bounds on the minimum size of a dynamic monopoly
• Some results on non-progressive spread of influence in graphs
• Modeling the spread of fault in majority-based network systems: dynamic monopolies in triangular grids
• Immunity against local influence
• On irreversible spread of influence in edge-weighted graphs
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Contagious sets in expanders
• Target set in threshold models
• Weak dynamic monopolies in social graphs
• A note on maximizing the spread of influence in social networks

This page was built for publication: On the spread of influence in graphs

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