Dynamic monopolies in directed graphs: the spread of unilateral influence in social networks. (English) Zbl 1288.05117
Summary: Irreversible dynamic monopolies arise from the formulation of the irreversible spread of influence such as disease, opinion, adaptation of a new product, etc., in social networks. In some applications, the influence in the underlying network is unilateral or one-sided. In order to study the latter models we need to introduce the concept of dynamic monopolies in directed graphs. Let \(G\) be a directed graph such that the in-degree of any vertex of \(G\) is at least one. Let also \(\tau:V(G)\to \mathbb N\) be an assignment of thresholds to the vertices of \(G\). A subset \(M\) of vertices of \(G\) is called a dynamic monopoly for \((G,\tau)\) if the vertex set of \(G\) can be partitioned into \(D_0\cup\cdots\cup D_t\) such that \(D_0=M\) and for any \(i\geq 1\) and any \(v\in D_i\), the number of edges from \(D_0 \cup\cdots\cup D_{i-1}\) to \(v\) is at least \(\tau(v)\).
One of the most applicable and widely studied threshold assignments in directed graphs is strict majority threshold assignment in which for any vertex \(v\), \(\tau(v)=\lceil(\deg^{-}(v)+1)/2\rceil\), where \(\deg^{-}(v\)) stands for the in-degree of \(v\).
In this paper we first discuss some basic upper and lower bounds for the size of dynamic monopolies with general threshold assignments and then obtain some hardness results concerning the smallest size of dynamic monopolies in directed graphs. We prove that any strongly connected directed graph \(G\) admits a strict majority dynamic monopoly with at most \(\lceil |G|/2\rceil\) vertices. Next we show that any simple directed graph on \(n\) vertices and with positive minimum in-degree admits a strict majority dynamic monopoly with at most \(n/2\) vertices, where by a simple directed graph we mean any directed graph \(G=(V,E)\) such that \((u,v)\in E\) implies \((v,u)\notin E\) for all \(u, v\in V\). We show that this bound is achieved by a polynomial time algorithm. This upper bound improves greatly the previous best known result. The final note of the paper deals with the possibility of the improvement of the latter \(n/2\) bound.
One of the most applicable and widely studied threshold assignments in directed graphs is strict majority threshold assignment in which for any vertex \(v\), \(\tau(v)=\lceil(\deg^{-}(v)+1)/2\rceil\), where \(\deg^{-}(v\)) stands for the in-degree of \(v\).
In this paper we first discuss some basic upper and lower bounds for the size of dynamic monopolies with general threshold assignments and then obtain some hardness results concerning the smallest size of dynamic monopolies in directed graphs. We prove that any strongly connected directed graph \(G\) admits a strict majority dynamic monopoly with at most \(\lceil |G|/2\rceil\) vertices. Next we show that any simple directed graph on \(n\) vertices and with positive minimum in-degree admits a strict majority dynamic monopoly with at most \(n/2\) vertices, where by a simple directed graph we mean any directed graph \(G=(V,E)\) such that \((u,v)\in E\) implies \((v,u)\notin E\) for all \(u, v\in V\). We show that this bound is achieved by a polynomial time algorithm. This upper bound improves greatly the previous best known result. The final note of the paper deals with the possibility of the improvement of the latter \(n/2\) bound.
References:
| [1] | Ackerman, E.; Ben-Zwi, O.; Wolfovitz, G., Combinatorial model and bounds for target set selection, Theoret. Comput. Sci., 411, 4017-4022 (2010) · Zbl 1235.90168 |
| [2] | Adams, S. S.; Booth, P.; Troxell, D. S.; Zinnen, S. L., Modeling the spread of fault in majority-based network systems: dynamic monopolies in triangular grids, Discrete Appl. Math., 160, 1624-1633 (2012) · Zbl 1244.68060 |
| [3] | Balogh, J.; Bollobas, B., Bootstrap percolation on the hypercube, Probab. Theory Related Fields, 134, 624-648 (2006) · Zbl 1087.60068 |
| [4] | Ben-Zwi, O.; Hermelin, D.; Lokshtanov, D.; Newman, I., Treewidth governs the complexity of target set selection, Discrete Optim., 8, 87-96 (2011) · Zbl 1248.90068 |
| [5] | Centeno, C. C.; Dourado, M. C.; Penso, L. D.; Rautenbach, D.; Szwarcfiter, J. L., Irreversible conversion of graphs, Theoret. Comput. Sci., 412, 3693-3700 (2011) · Zbl 1220.05109 |
| [6] | Chang, C-L.; Lyuu, Y-D., Spreading messages, Theoret. Comput. Sci., 410, 2714-2724 (2009) · Zbl 1172.68003 |
| [9] | Chen, N., On the approximability of influence in social networks, SIAM J. Discrete Math., 23, 1400-1415 (2009) · Zbl 1203.68314 |
| [11] | Dreyer, P. A.; Roberts, F. S., Irreversible \(k\)-threshold processes: graph-theoretical threshold models of the spread of disease and of opinion, Discrete Appl. Math., 157, 1615-1627 (2009) · Zbl 1163.92035 |
| [12] | Flocchini, P.; Kralovic, R.; Roncato, A.; Ruzicka, P.; Santoro, N., On time versus size for monotone dynamic monopolies in regular topologies, J. Discrete Algorithms, 1, 129-150 (2003) · Zbl 1074.68045 |
| [13] | Khoshkhah, K.; Soltani, H.; Zaker, M., On dynamic monopolies of graphs: the average and strict majority thresholds, Discrete Optim., 9, 77-83 (2012) · Zbl 1246.91115 |
| [14] | Kulich, T., Dynamic monopolies with randomized starting configuration, Theoret. Comput. Sci., 412, 6371-6381 (2011) · Zbl 1233.68165 |
| [15] | Nichterlein, A.; Niedermeier, R.; Uhlmann, J.; Weller, M., On tractable cases of target set selection, (Algorithms and Computation. Part I. Algorithms and Computation. Part I, Lecture Notes in Comput. Sci., vol. 6506 (2010), Springer: Springer Berlin), 378-389 · Zbl 1310.68115 |
| [16] | West, D. B., Introduction to Graph Theory (2001), Prentice Hall |
| [17] | Zaker, M., On dynamic monopolies of graphs with general thresholds, Discrete Math., 312, 1136-1143 (2012) · Zbl 1238.05262 |
| [18] | Zaker, M., Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs, Discrete Appl. Math., 161, 2716-2723 (2013) · Zbl 1285.05131 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
