On dynamic monopolies of graphs: the average and strict majority thresholds

DOI10.1016/J.DISOPT.2012.02.001MaRDI QIDQ448965zbMATH OpenOpenAlexFDO

Authors Kaveh Khoshkhah, Hossein Soltani, Manouchehr Zaker

Publication date 11 September 2012

Published in Discrete Optimization (Search for Journal in Brave)

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

zbMATH Keywords

dynamic monopoliesirreversible spread of influence

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Social networks; opinion dynamics (91D30)

Abstract: Let $G$ be a graph and $mathcalau:V(G)ightarrowBbbNcup0$ be an assignment of thresholds to the vertices of $G$. A subset of vertices $D$ is said to be a dynamic monopoly corresponding to $(G,au)$ 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 $iin0,\mathrm{...},k-1$, each vertex $v$ in $D_{i+1}$ has at least $au(v)$ neighbors in $D_{0}cup\mathrm{...}cup{D}_i$. Dynamic monopolies are in fact modeling the irreversible spread of influence in social networks. In this paper we first obtain a lower bound for the smallest size of any dynamic monopoly in terms of the average threshold and the order of graph. Also we obtain an upper bound in terms of the minimum vertex cover of graphs. Then we derive the upper bound $|G|/2$ for the smallest size of any dynamic monopoly when the graph $G$ contains at least one odd vertex, where the threshold of any vertex $v$ is set as $lceil(deg(v)+1)/2ceil$ (i.e. strict majority threshold). This bound improves the best known bound for strict majority threshold. We show that the latter bound can be achieved by a polynomial time algorithm. We also show that $alph{a}^{\prime }(G)+1$ is an upper bound for the size of strict majority dynamic monopoly, where $alph{a}^{\prime }(G)$ stands for the matching number of $G$. Finally, we obtain a basic upper bound for the smallest size of any dynamic monopoly, in terms of the average threshold and vertex degrees. Using this bound we derive some other upper bounds.

Recommendations

• Dynamic monopolies in directed graphs: the spread of unilateral influence in social networks
• On dynamic monopolies of graphs with general thresholds
• On dynamic monopolies of graphs with probabilistic thresholds
• On the Largest Dynamic Monopolies of Graphs with a Given Average Threshold
• Remarks on dynamic monopolies with given average thresholds

Cites work

• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• A study of monopolies in graphs
• Combinatorial model and bounds for target set selection
• Dynamic monopolies in tori.
• Dynamic monopolies of constant size
• Dynamic monopolies with randomized starting configuration
• Graph theory
• Irreversible \(k\)-threshold and majority conversion processes on complete multipartite graphs and graph products
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• On dynamic monopolies of graphs with general 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
• Size bounds for dynamic monopolies
• Spreading messages

Cited in

(30)

• Partial immunization of trees
• 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
• On irreversible spread of influence in edge-weighted graphs
• Dynamic monopolies with randomized starting configuration
• On the maximum size of resistant subgraphs in graphs with given average threshold
• On the complexity of reasoning about opinion diffusion under majority dynamics
• 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
• 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
• Dynamic monopolies in directed graphs: the spread of unilateral influence in social networks
• Integer programming approach to static monopolies in graphs
• On the spread of influence in graphs
• Some results on non-progressive spread of influence in graphs
• Triggering cascades on strongly connected directed graphs
• Bounding the sizes of dynamic monopolies and convergent sets for threshold-based cascades
• 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
• Partial vertex covers and the complexity of some problems concerning static and dynamic monopolies
• Remarks on dynamic monopolies with given average thresholds
• On the Largest Dynamic Monopolies of Graphs with a Given Average Threshold
• On dynamic monopolies of graphs with general thresholds
• Tight bounds on the minimum size of a dynamic monopoly

This page was built for publication: On dynamic monopolies of graphs: the average and strict majority thresholds

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