On dynamic monopolies of graphs with general thresholds

DOI10.1016/J.DISC.2011.11.038MaRDI QIDQ409449zbMATH OpenOpenAlexFDO

Authors Manouchehr Zaker

Publication date 13 April 2012

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

spread of influencedynamic monopolies

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(37)

• Weak dynamic monopolies in social graphs
• On monopoly and dynamic monopoly of Cartesian product of graphs with constant thresholds.
• On dynamic monopolies of graphs with probabilistic thresholds
• Facets of the dynamic monopoly polytope: linear ordering formulation
• Vaccinate your trees!
• Modeling the spread of fault in majority-based network systems: dynamic monopolies in triangular grids
• On the maximum size of resistant subgraphs in graphs with given average threshold
• Bounding the open \(k\)-monopoly number of strong product graphs
• On dynamic monopolies of graphs: the average and strict majority thresholds
• Target set selection on generalized pancake graphs
• Spread of influence in weighted networks under time and budget constraints
• Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs
• Bounds and extremal graphs for degenerate subsets, dynamic monopolies, and partial incentives
• A polyhedral study of dynamic monopolies
• Influence Diffusion in Social Networks under Time Window Constraints
• A study of monopolies in graphs
• Spread of influence with incentives in edge-weighted graphs with emphasis on some families of graphs
• Dynamic monopolies and feedback vertex sets in hexagonal grids
• The \(t\)-latency bounded strong target set selection problem in some kinds of special family of graphs
• Discovering small target sets in social networks: a fast and effective algorithm
• The k-conversion number of regular graphs
• Dynamic monopolies in directed graphs: the spread of unilateral influence in social networks
• Integer programming approach to static monopolies in graphs
• Optimizing spread of influence in social networks via partial incentives
• On the spread of influence in graphs
• Target set selection with maximum activation time
• A fast and effective heuristic for discovering small target sets in social networks
• Generalized threshold processes on graphs
• Latency-bounded target set selection in social networks
• Triggering cascades on strongly connected directed graphs
• Exact solutions for latency-bounded target set selection problem on some special families of graphs
• Dynamic monopolies for interval graphs with bounded thresholds
• Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees
• Influence diffusion in social networks under time window constraints
• Dynamic monopolies and feedback vertex sets in cycle permutation graphs, generalized Petersen graphs and torus cordalis
• Remarks on dynamic monopolies with given average thresholds
• On the Largest Dynamic Monopolies of Graphs with a Given Average Threshold

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)