On irreversible spread of influence in edge-weighted graphs

  • Manouchehr Zaker Institute for Advanced Studies in Basic Sciences


Various kinds of spread of influence occur in real world social and virtual networks. These phenomena are formulated by activation processes and irreversible dynamic monopolies in combinatorial graphs representing the topology of the networks. In most cases, the nature of influence is weighted and the spread of influence depends on the weight of edges. The ordinary formulation and results for dynamic monopolies do not work for such models. In this paper we present a graph theoretical analysis for spread of weighted influence and mention a real world example realizing the activation model with weighted influence. Then we obtain some extremal bounds and algorithmic results for activation process and dynamic monopolies in directed and undirected graphs with weighted edges.


E. Ackerman, O. Ben-Zwi, G. Wolfovitz, {it Combinatorial Model and Bounds for Target Set Selection}, Theoret. Comput. Sci. {bf 411} (2010), 4017--4022.

H. Amini, {it Bootstrap percolation in living neural networks}, J. Statistical Physics {bf 141} (2010), 459--475.

O. Ben-Zwi, D.Hermelin, D.Lokshtanov, I. Newman, {it Treewidth governs the

complexity of target set selection}, Discrete Optim. {bf 8} (2011), 87--96.

C.C. Centeno, M.C. Dourado, L.D. Penso, D. Rautenbach , J.L. Szwarcfiter, {bf Irreversible conversion of graphs}, Theoret. Comput. Sci. {bf 412} (2011), 3693--3700.

C-L. Chang, Y-D. Lyuu, {it On irreversible dynamic monopolies in general graphs}, arXiv:0904.2306v3, 2010.

N. Chen, {it On the approximability of influence in social networks},

SIAM J. Discrete Math. {bf 23} (2009), 1400--1415.

R. Cont, A. Moussa, E. Santos, {it Network structure and systemic risk in banking systems}, In Handbook of Systemic Risk, edited by J.P.

Fouque and J. Langsam, 2012 (Cambridge University Press).

R. Diestel, {it Graph theory}, Heidelberg: Springer, 2005.

P.A. Dreyer, F.S. Roberts, {it Irreversible $k$-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion}, Disc. Appl. Math. {bf 157} (2009), 1615--1627.

P. Flocchini, R. Kralovic, A. Roncato, P. Ruzicka, N. Santoro,

{it On time versus size for monotone dynamic monopolies in regular topologies}, J. Discrete Algorithms {bf 1} (2003), 129--150.

D. Kempe, J. Kleinberg, E. Tardos, {it Maximizing the spread of influence through a social network}, In Proc. 9th ACM SIGKDD International Conference on Knowledge

Discovery and Data Mining, pages 137--146, 2003.

K. Khoshkhah, H. Soltani, M. Zaker, {it On dynamic monopolies of graphs:

the average and strict majority thresholds}, Discrete Optim. {bf 9} (2012), 77--83.

K. Khoshkhah, H. Soltani, M. Zaker, {it Dynamic monopolies in directed graphs: the spread of unilateral influence in social networks}, Disc. Appl. Math. {bf 171} (2014), 81--89.

A. Nichterlein, R. Niedermeier, J. Uhlmann, M. Weller, {it On tractable cases of target set selection}, Lecture Notes in Comput. Sci., 6506, Springer, Berlin, 2010.

M. Zaker, {it On dynamic monopolies of graphs with general thresholds}, Discrete Math. {bf 312} (2012), 1136--1143.

M. Zaker, {it Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs}, Disc. Appl. Math. {bf 161} (2013), 2716--2723.