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

DOI10.1016/J.DISOPT.2012.02.001zbMATH Open1246.91115arXiv1202.1146OpenAlexW2962901628MaRDI QIDQ448965FDOQ448965

Hossein Soltani, Manouchehr Zaker, Kaveh Khoshkhah

Publication date: 11 September 2012

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

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.

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

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

zbMATH Keywords

dynamic monopoliesirreversible spread of influence

Mathematics Subject Classification ID

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

Cites Work

• Graph theory
• On time versus size for monotone dynamic monopolies in regular topologies
• On the Approximability of Influence in Social Networks
• On dynamic monopolies of graphs with general thresholds
• Combinatorial model and bounds for target set selection
• 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
• A study of monopolies in graphs
• Spreading messages
• Dynamic monopolies in tori.
• Dynamic monopolies of constant size
• Optimal irreversible dynamos in chordal rings
• Irreversible \(k\)-threshold and majority conversion processes on complete multipartite graphs and graph products
• Dynamic monopolies with randomized starting configuration

Cited In (18)

• Exact solutions for latency-bounded target set selection problem on some special families of graphs
• On dynamic monopolies of graphs with general thresholds
• Spread of influence with incentives in edge-weighted graphs with emphasis on some families of graphs
• Dynamic monopolies in directed graphs: the spread of unilateral influence in social networks
• Remarks on dynamic monopolies with given average thresholds
• On irreversible spread of influence in edge-weighted graphs
• 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
• 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
• On the complexity of reasoning about opinion diffusion under majority dynamics
• 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
• Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees
• Integer programming approach to static monopolies in graphs

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)