On dynamic monopolies of graphs with general thresholds

DOI10.1016/J.DISC.2011.11.038zbMATH Open1238.05262arXiv1103.1112OpenAlexW1677630274MaRDI QIDQ409449FDOQ409449

Manouchehr Zaker

Publication date: 13 April 2012

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

Abstract: Let $G$ be a graph and $mathcalau:V(G)ightarrowBbbN$ be an assignment of thresholds to the vertices of $G$. A subset of vertices $D$ is said to be dynamic monopoly (or simply dynamo) if the vertices of $G$ can be partitioned into subsets $D_0,D_1,\mathrm{...},D_k$ such that $D_0=D$ and for any $i=1,\mathrm{...},k-1$ each vertex $v$ in $D_{i+1}$ has at least $t(v)$ neighbors in $D_{0}cup\mathrm{...}cup{D}_i$. Dynamic monopolies are in fact modeling the irreversible spread of influence such as disease or belief in social networks. We denote the smallest size of any dynamic monopoly of $G$, with a given threshold assignment, by $dyn(G)$. In this paper we first define the concept of a resistant subgraph and show its relationship with dynamic monopolies. Then we obtain some lower and upper bounds for the smallest size of dynamic monopolies in graphs with different types of thresholds. Next we introduce dynamo-unbounded families of graphs and prove some related results. We also define the concept of a homogenious society that is a graph with probabilistic thresholds satisfying some conditions and obtain a bound for the smallest size of its dynamos. Finally we consider dynamic monopoly of line graphs and obtain some bounds for their sizes and determine the exact values in some special cases.

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

Recommendations

• On dynamic monopolies of graphs with probabilistic thresholds
• On dynamic monopolies of graphs: the average and strict majority thresholds
• Dynamic monopolies in directed graphs: the spread of unilateral influence in social networks
• Weak dynamic monopolies in social graphs
• On the Largest Dynamic Monopolies of Graphs with a Given Average Threshold

zbMATH Keywords

spread of influencedynamic monopolies

Mathematics Subject Classification ID

Applications of graph theory (05C90) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Cites Work

• Graph theory
• Probabilistic methods for algorithmic discrete mathematics
• Local majorities, coalitions and monopolies in graphs: A review
• On time versus size for monotone dynamic monopolies in regular topologies
• On the approximability of influence in social networks
• On dynamic monopolies of graphs: the average and strict majority thresholds
• Title not available (Why is that?)
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Size bounds for dynamic monopolies
• Spreading messages
• Dynamic monopolies in tori.
• Dynamic monopolies of constant size
• Optimal irreversible dynamos in chordal rings
• Degree-Constrained Subgraph Problems: Hardness and Approximation Results
• Subgraphs of minimal degree \(k\)

Cited In (30)

• The k-conversion number of regular graphs
• Exact solutions for latency-bounded target set selection problem on some special families of graphs
• On dynamic monopolies of graphs: the average and strict majority thresholds
• Spread of influence in weighted networks under time and budget constraints
• Spread of influence with incentives in edge-weighted graphs with emphasis on some families of graphs
• Modeling the spread of fault in majority-based network systems: dynamic monopolies in triangular grids
• Whom to befriend to influence people
• Dynamic monopolies in directed graphs: the spread of unilateral influence in social networks
• The \(t\)-latency bounded strong target set selection problem in some kinds of special family of graphs
• ON DYNAMIC MONOPOLIES OF GRAPHS WITH PROBABILISTIC THRESHOLDS
• Influence diffusion in social networks under time window constraints
• Bounds and extremal graphs for degenerate subsets, dynamic monopolies, and partial incentives
• Facets of the dynamic monopoly polytope: linear ordering formulation
• Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs
• Influence Diffusion in Social Networks under Time Window Constraints
• Dynamic monopolies and feedback vertex sets in hexagonal grids
• Optimizing Spread of Influence in Social Networks via Partial Incentives
• A Fast and Effective Heuristic for Discovering Small Target Sets in Social Networks
• Generalized threshold processes on graphs
• Bounding the open \(k\)-monopoly number of strong product graphs
• Triggering cascades on strongly connected directed graphs
• On the Largest Dynamic Monopolies of Graphs with a Given Average Threshold
• A polyhedral study of dynamic monopolies
• A study of monopolies in graphs
• Target set selection with maximum activation time
• Target set selection on generalized pancake graphs
• Discovering small target sets in social networks: a fast and effective algorithm
• Integer programming approach to static monopolies in graphs
• Latency-bounded target set selection in social networks
• Dynamic monopolies and feedback vertex sets in cycle permutation graphs, generalized Petersen graphs and torus cordalis

This page was built for publication: On dynamic monopolies of graphs with general thresholds

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