Dynamic monopolies with randomized starting configuration

DOI10.1016/J.TCS.2011.08.004MaRDI QIDQ653331zbMATH OpenOpenAlexFDO

Authors Tomáš Kulich

Publication date 9 January 2012

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

Full work available at URL https://arxiv.org/abs/1007.4154

zbMATH Keywords

gridmajority votingrandom graphcellular automatagame of lifemajoriy-based system

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: Properties of systems with majority voting rules have been exhaustingly studied. In this work we focus on the randomized case - where the system is initialized by randomized initial set of seeds. Our main aim is to give an asymptotic estimate for sampling probability, such that the initial set of seeds is (is not) a dynamic monopoly almost surely. After presenting some trivial examples, we present exhaustive results for toroidal mesh and random 4-regular graph under simple majority scenario.

Recommendations

• Size bounds for dynamic monopolies
• Dynamic monopolies in tori.
• Majority model on random regular graphs
• Dynamic monopolies of constant size
• On dynamic monopolies of graphs: the average and strict majority thresholds

Cites work

• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• A simple model of global cascades on random networks
• Bounding the number of tolerable faults in majority-based systems
• Combinatorial model and bounds for target set selection
• Contamination and decontamination in majority-based systems
• Dynamic monopolies in tori.
• Functionals of critical multitype branching processes
• Local majorities, coalitions and monopolies in graphs: A review
• Optimal irreversible dynamos in chordal rings
• Spreading messages
• Spreading of messages in random graphs
• The asymptotic connectivity of labelled regular graphs
• The asymptotic distribution of short cycles in random regular graphs
• The asymptotic number of labeled graphs with given degree sequences

Cited in

(8)

• On dynamic monopolies of graphs with probabilistic thresholds
• On dynamic monopolies of graphs: the average and strict majority thresholds
• Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs
• Dynamic monopoly with relational incentives
• Dynamic monopolies in directed graphs: the spread of unilateral influence in social networks
• Randomization and the limit points of monopolistic competition
• Multi-level dynamo and opinion spreading
• Dynamic monopolies of constant size

This page was built for publication: Dynamic monopolies with randomized starting configuration

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