Abstract
The spread of influence in social networks is studied in two main categories: the progressive model and the non-progressive model (see e.g. the seminal work of Kempe, Kleinberg, and Tardos in KDD 2003). While the progressive models are suitable for modeling the spread of influence in monopolistic settings, non-progressive are more appropriate for modeling non-monopolistic settings, e.g., modeling diffusion of two competing technologies over a social network. Despite the extensive work on the progressive model, non-progressive models have not been studied well. In this paper, we study the spread of influence in the nonprogressive model under the strict majority threshold: given a graph G with a set of initially infected nodes, each node gets infected at time τ iff a majority of its neighbors are infected at time τ – 1. Our goal in the MinPTS problem is to find a minimum-cardinality initial set of infected nodes that would eventually converge to a steady state where all nodes of G are infected.
We prove that while the MinPTS is NP-hard for a restricted family of graphs, it admits an improved constant-factor approximation algorithm for power-law graphs. We do so by proving lower and upper bounds in terms of the minimum and maximum degree of nodes in the graph. The upper bound is achieved in turn by applying a natural greedy algorithm. Our experimental evaluation of the greedy algorithm also shows its superior performance compared to other algorithms for a set of realworld graphs as well as the random power-law graphs. Finally, we study the convergence properties of these algorithms and show that the nonprogressive model converges in at most O(|E(G)|) steps.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ackerman, E., Ben-Zwi, O., Wolfovitz, G.: Combinatorial Model and Bounds for Target Set Selection. Theoretical Computer Science (2010)
Allan, R., Laskar, R.: On domination and independent domination numbers of a graph. Discrete Mathematics 23(2), 73–76 (1978)
Ben-Zwi, O., Hermelin, D., Lokshtanov, D., Newman, I.: An exact almost optimal algorithm for target set selection in social networks. In: Proceedings of the Tenth ACM Conference on Electronic Commerce, pp. 355–362. ACM (2009)
Blume, L.: The statistical mechanics of strategic interaction. Games and Economic Behavior 5, 387–424 (1993)
Brown, J., Reingen, P.: Social ties and word-of-mouth referral behavior. The Journal of Consumer Research 14(3), 350–362 (1987)
Chang, C.: On reversible cascades in scale-free and Erdos Renyi random graphs. Arxiv preprint arXiv:1011.0653 (2010)
Chang, C., Lyuu, Y.: On irreversible dynamic monopolies in general graphs. Arxiv preprint arXiv:0904.2306 (2009)
Chang, C., Lyuu, Y.: Spreading messages. Theoretical Computer Science 410(27-29), 2714–2724 (2009)
Chen, N.: On the approximability of influence in social networks. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1029–1037. Society for Industrial and Applied Mathematics (2008)
Chen, W., Wang, Y., Yang, S.: Efficient influence maximization in social networks. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 199–208. ACM (2009)
Clauset, A., Shalizi, C., Newman, M.: Power-law distributions in empirical data. SIAM Review 51(4), 661–703 (2009)
Dezső, Z., Barabási, A.: Halting viruses in scale-free networks. Physical Review E 65(5), 55103 (2002)
Domingos, P., Richardson, M.: Mining the network value of customers. In: KDD 2001: Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 26-29, p. 57. Assn. for Computing Machinery, San Francisco (2001)
Ellison, G.: Learning, local interaction, and coordination. Econometrica 61, 1047–1071 (1993)
Flocchini, P., Geurts, F., Santoro, N.: Optimal irreversible dynamos in chordal rings. Discrete Applied Mathematics 113(1), 23–42 (2001)
Flocchini, P., Královi, R., Ruika, P., Roncato, A., Santoro, N.: On time versus size for monotone dynamic monopolies in regular topologies. Journal of Discrete Algorithms 1(2), 129–150 (2003)
Flocchini, P., Lodi, E., Luccio, F., Pagli, L., Santoro, N.: Dynamic monopolies in tori. Discrete Applied Mathematics 137(2), 197–212 (2004)
Freeman, L.: The development of social network analysis. Empirical Press, Vancouver (2004)
Goyal, A., Bonchi, F., Lakshmanan, L., Balcan, M., Harvey, N., Lapus, R., Simon, F., Tittmann, P., Ben-Shimon, S., Ferber, A., et al.: Approximation Analysis of Influence Spread in Social Networks. Arxiv preprint arXiv:1008.2005 (2010)
Immorlica, N., Kleinberg, J., Mahdian, M., Wexler, T.: The role of compatibility in the diffusion of technologies through social networks. In: Proceedings of the 8th ACM Conference on Electronic Commerce, EC 2007, pp. 75–83. ACM, New York (2007)
Ivic, A.: Riemann zeta-function. John Wiley & Sons, Inc., One Wiley Drive, Somerset, NJ 08873 (USA), 340 (1985)
Jackson, M., Yariv, L.: Diffusion on social networks. Economie Publique 16, 69–82 (2005)
Kempe, D., Kleinberg, J., Tardos, É.: Maximizing the spread of influence through a social network. In: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137–146. ACM (2003)
Luccio, F., Pagli, L., Sanossian, H.: Irreversible dynamos in butterflies. In: Proc. of 6th Colloquium on Structural Information and Communication Complexity, pp. 204–218. Citeseer (1999)
Mossel, E., Roch, S.: On the submodularity of influence in social networks. In: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, pp. 128–134. ACM (2007)
Mossel, E., Schoenebeck, G.: Reaching consensus on social networks. In: Innovations in Computer Science, ICS (2009)
Pastor-Satorras, R., Vespignani, A.: Epidemic spreading in scale-free networks. Physical Review Letters 86(14), 3200–3203 (2001)
Peleg, D.: Local majorities, coalitions and monopolies in graphs: a review. Theoretical Computer Science 282(2), 231–257 (2002)
Pike, D., Zou, Y.: Decycling Cartesian products of two cycles. SIAM Journal on Discrete Mathematics 19, 651 (2005)
Richardson, M., Domingos, P.: Mining knowledge-sharing sites for viral marketing. In: Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 61–70. ACM (2002)
Tang, J., Sun, J., Wang, C., Yang, Z.: Social influence analysis in large-scale networks. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 807–816. ACM (2009)
Wilson, D.: Levels of selection: An alternative to individualism in biology and the human sciences. Social Networks 11(3), 257–272 (1989)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fazli, M., Ghodsi, M., Habibi, J., Jalaly Khalilabadi, P., Mirrokni, V., Sadeghabad, S.S. (2012). On the Non-progressive Spread of Influence through Social Networks. In: Fernández-Baca, D. (eds) LATIN 2012: Theoretical Informatics. LATIN 2012. Lecture Notes in Computer Science, vol 7256. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-29344-3_27
Download citation
DOI: https://doi.org/10.1007/978-3-642-29344-3_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-29343-6
Online ISBN: 978-3-642-29344-3
eBook Packages: Computer ScienceComputer Science (R0)