research-article

Public Access

General Threshold Model for Social Cascades: Analysis and Simulations

Authors:

Golnaz Ghasemiesfeh,

Grant Schoenebeck,

Fang-Yi YuAuthors Info & Claims

EC '16: Proceedings of the 2016 ACM Conference on Economics and Computation

Pages 617 - 634

https://doi.org/10.1145/2940716.2940778

Published: 21 July 2016 Publication History

Abstract

Social behaviors and choices spread through interactions and may lead to a cascading behavior. Understanding how such social cascades spread in a network is crucial for many applications ranging from viral marketing to political campaigns. The behavior of cascade depends crucially on the model of cascade or social influence and the topological structure of the social network.

In this paper we study the general threshold model of cascades which are parameterized by a distribution over the natural numbers, in which the collective influence from infected neighbors, once beyond the threshold of an individual u, will trigger the infection of u. By varying the choice of the distribution, the general threshold model can model cascades with and without the submodular property. In fact, the general threshold model captures many previously studied cascade models as special cases, including the independent cascade model, the linear threshold model, and k-complex contagions.

We provide both analytical and experimental results for how cascades from a general threshold model spread in a general growing network model, which contains preferential attachment models as special cases. We show that if we choose the initial seeds as the early arriving nodes, the contagion can spread to a good fraction of the network and this fraction crucially depends on the fixed points of a function derived only from the specified distribution. We also show, using a coauthorship network derived from DBLP databases and the Stanford web network, that our theoretical results can be used to predict the infection rate up to a decent degree of accuracy, while the configuration model does the job poorly.

References

[1]

Lada A Adamic and Natalie Glance. 2005. The political blogosphere and the 2004 US election: divided they blog. In Proceedings of the 3rd International Workshop on Link discovery. 36--43.

Digital Library

[2]

Lars Backstrom, Dan Huttenlocher, Jon Kleinberg, and Xiangyang Lan. 2006. Group Formation in Large Social Networks: Membership, Growth, and Evolution. In Proc. of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 44--54.

Digital Library

[3]

Abhijit Banerjee, Arun G Chandrasekhar, Esther Duflo, and Matthew O Jackson. 2013. The diffusion of microfinance. Science 341, 6144 (2013).

[4]

A. Barabási and R. Albert. 1999. Emergence of scaling in random networks. Science 286 (1999), 509--512.

[5]

J. Coleman, E. Katz, and H. Menzel. 1957. The diffusion of an innovation among physicians. Sociometry 20 (1957), 253--270.

[6]

James S. Coleman, Elihu Katz, and Herbert Menzel. 1966. Medical Innovation: A Diffusion Study. Bobbs-Merrill Co.

[7]

Devdatt P Dubhashi and Alessandro Panconesi. 2009. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press.

Digital Library

[8]

D.Watts, P.Dodds, and M.Newman. 2002. Identity and Search in Social Networks. Science 296 (2002), 1302--1305.

[9]

D.Watts and S.Strogatz. 1998. Collective dynamics of "small-world" networks. Nature 393, 6684 (1998), 409--410.

[10]

Roozbeh Ebrahimi, Jie Gao, Golnaz Ghasemiesfeh, and Grant Schoenebeck. 2014. How Complex Contagions Spread Quickly in the Preferential Attachment Model and Other Time-Evolving Networks. arXiv preprint arXiv:1404.2668 (2014).

[11]

Roozbeh Ebrahimi, Jie Gao, Golnaz Ghasemiesfeh, and Grant Schoenebeck. 2015. Complex Contagions in Kleinberg's Small World Model. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (ITCS). 63--72.

Digital Library

[12]

Golnaz Ghasemiesfeh, Roozbeh Ebrahimi, and Jie Gao. 2013. Complex contagion and the weakness of long ties in social networks: revisited. In Proceedings of the fourteenth ACM conference on Electronic Commerce. 507--524.

Digital Library

[13]

J. Goldenberg, B. Libai, and Muller. 2001. Using complex systems analysis to advance marketing theory development. Academy of Marketing Science Review (2001).

[14]

M. Granovetter. 1978. Threshold Models of Collective Behavior. Am. Journal of Sociology 83, 6 (1978), 1420--1443.

[15]

Geoffrey Grimmett and David Stirzaker. 2001. Probability and random processes. Oxford university press.

[16]

Matthew O. Jackson. 2008. Social and Economic Networks. Princeton University Press, Princeton, NJ, USA.

Digital Library

[17]

David Kempe, Jon Kleinberg, and Éva Tardos. 2003. Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. 137--146.

Digital Library

[18]

Jon Kleinberg. 2000. The small-world phenomenon: an algorithm perspective. In Proceedings of the 32-nd annual ACM symposium on Theory of Computing. 163--170.

Digital Library

[19]

Jon M. Kleinberg. 2001. Small-World Phenomena and the Dynamics of Information. In NIPS. 431--438.

Digital Library

[20]

Jon M. Kleinberg, Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, and Andrew S. Tomkins. 1999. The web as a graph: measurements, models, and methods. In Proceedings of the 5th annual international conference on Computing and combinatorics. 1--17.

Digital Library

[21]

R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, and E. Upfal. 2000. Stochastic models for the Web graph. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS'00). 57--.

Digital Library

[22]

Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, and Andrew Tomkins. 1999. Extracting Large-Scale Knowledge Bases from the Web. In Proceedings of the 25th International Conference on Very Large Data Bases. 639--650.

Digital Library

[23]

J S Macdonald and L D Macdonald. 1964. Chain Migration, Ethnic Neighborhood Formation and Social Networks. The Milbank Memorial Fund Quarterly 42, 1 (1964), 82--97.

[24]

Robin Mermelstein, Sheldon Cohen, Edward Lichtenstein, John S Baer, and Tom Kamarck. 1986. Social support and smoking cessation and maintenance. Journal of consulting and clinical psychology 54, 4 (1986), 447.

[25]

Elchanan Mossel and Sebastien Roch. 2007. On the submodularity of influence in social networks. In Proc. of the thirty-ninth annual ACM symposium on Theory of computing. 128--134.

Digital Library

[26]

Elchanan Mossel and Sébastien Roch. 2010. Submodularity of Influence in Social Networks: From Local to Global. SIAM J. Comput. 39, 6 (2010), 2176--2188.

Digital Library

[27]

M E J Newman and D J Watts. 1999. Scaling and percolation in the small-world network model. Physical Review E 60, 6 (1999), 7332--7342.

[28]

Robin Pemantle. 1991. When are Touchpoints Limits For Generalized Polya Urns. In Proceedings of the American Mathematical Society, Vol. 113. 235--243.

[29]

Robin Pemantle and others. 2007. A survey of random processes with reinforcement. Probab. Surv 4, 0 (2007), 1--79.

[30]

Daniel M. Romero, Brendan Meeder, and Jon Kleinberg. 2011. Differences in the mechanics of information diffusion across topics: idioms, political hashtags, and complex contagion on twitter. In Proceedings of the 20th international conference on World wide web. 695--704.

Digital Library

[31]

J. Ugander, L. Backstrom, C. Marlow, and J. Kleinberg. 2012. Structural Diversity in Social Contagion. Proc. National Academy of Sciences 109, 16 (April 2012), 5962--5966.

Cited By

SENO HUCHIOKE RDANSU E(2024)A DISCRETE-TIME POPULATION DYNAMICS MODEL FOR THE INFORMATION SPREAD UNDER THE EFFECT OF SOCIAL RESPONSEJournal of Biological Systems10.1142/S021833902440007232:04(1379-1426)Online publication date: 7-Aug-2024
https://doi.org/10.1142/S0218339024400072
Chen HWilder BQiu WAn BRice ETambe MElkind E(2023)Complex contagion influence maximizationProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/614(5531-5540)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/614
Dansu ESeno H(2023)A rejoinder model for the population dynamics of the spread of two interacting pieces of informationAfrika Matematika10.1007/s13370-023-01134-935:1Online publication date: 24-Nov-2023
https://doi.org/10.1007/s13370-023-01134-9
Show More Cited By

Recommendations

Maximizing the spread of influence through a social network
KDD '03: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining

Models for the processes by which ideas and influence propagate through a social network have been studied in a number of domains, including the diffusion of medical and technological innovations, the sudden and widespread adoption of various strategies ...
Characterizing social cascades in flickr
WOSN '08: Proceedings of the first workshop on Online social networks

Online social networking sites like MySpace and Flickr have become a popular way to share and disseminate content. Their massive popularity has led to the viral marketing of content, products, and political campaigns on the sites themselves. Despite the ...
A Survey of Information Cascade Analysis: Models, Predictions, and Recent Advances

The deluge of digital information in our daily life—from user-generated content, such as microblogs and scientific papers, to online business, such as viral marketing and advertising—offers unprecedented opportunities to explore and exploit the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EC '16: Proceedings of the 2016 ACM Conference on Economics and Computation

July 2016

874 pages

ISBN:9781450339360

DOI:10.1145/2940716

General Chair:
Vincent Conitzer
Duke University, USA
,
Program Chairs:
Dirk Bergemann
Yale University, USA
,
Yiling Chen
Harvard University, USA

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGecom: Special Interest Group on Economics and Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 July 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

EC '16

Sponsor:

SIGecom

EC '16: ACM Conference on Economics and Computation

July 24 - 28, 2016

Maastricht, The Netherlands

Acceptance Rates

EC '16 Paper Acceptance Rate 80 of 242 submissions, 33%;

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Upcoming Conference

EC '25

Sponsor:
sigecom

The 25th ACM Conference on Economics and Computation

July 7 - 11, 2025

Stanford , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
618
Total Downloads

Downloads (Last 12 months)184
Downloads (Last 6 weeks)61

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

SENO HUCHIOKE RDANSU E(2024)A DISCRETE-TIME POPULATION DYNAMICS MODEL FOR THE INFORMATION SPREAD UNDER THE EFFECT OF SOCIAL RESPONSEJournal of Biological Systems10.1142/S021833902440007232:04(1379-1426)Online publication date: 7-Aug-2024
https://doi.org/10.1142/S0218339024400072
Chen HWilder BQiu WAn BRice ETambe MElkind E(2023)Complex contagion influence maximizationProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/614(5531-5540)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/614
Dansu ESeno H(2023)A rejoinder model for the population dynamics of the spread of two interacting pieces of informationAfrika Matematika10.1007/s13370-023-01134-935:1Online publication date: 24-Nov-2023
https://doi.org/10.1007/s13370-023-01134-9
DANSU ESENO H(2022)A Mathematical Model for the Dynamics of Information Spread under the Effect of Social ResponseInterdisciplinary Information Sciences10.4036/iis.2022.R.0328:1(75-93)Online publication date: 2022
https://doi.org/10.4036/iis.2022.R.03
Rezaei AGao J(2019)On Privacy of Socially Contagious Attributes2019 IEEE International Conference on Data Mining (ICDM)10.1109/ICDM.2019.00163(1294-1299)Online publication date: Nov-2019
https://doi.org/10.1109/ICDM.2019.00163
Képes TGaskó NLung RSuciu M(2019)Influence Maximization and Extremal OptimizationHybrid Artificial Intelligent Systems10.1007/978-3-030-29859-3_36(416-427)Online publication date: 4-Sep-2019
https://dl.acm.org/doi/10.1007/978-3-030-29859-3_36
Li QChen WSun XZhang J(2017)Influence maximization with ε-almost submodular threshold functionsProceedings of the 31st International Conference on Neural Information Processing Systems10.5555/3294996.3295137(3804-3814)Online publication date: 4-Dec-2017
https://dl.acm.org/doi/10.5555/3294996.3295137
Gao JSchoenebeck GYu F(2017)Cascades and Myopic Routing in Nonhomogeneous Kleinberg’s Small World ModelWeb and Internet Economics10.1007/978-3-319-71924-5_27(383-394)Online publication date: 25-Nov-2017
https://doi.org/10.1007/978-3-319-71924-5_27

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten