Dynamic monopolies with randomized starting configuration

DOI10.1016/J.TCS.2011.08.004zbMATH Open1233.68165arXiv1007.4154OpenAlexW1670249695MaRDI QIDQ653331FDOQ653331

Authors: Tomáš Kulich 

Publication date: 9 January 2012

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

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.

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

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

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)

Cites Work

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

Cited In (8)

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

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)