research-article

Twin Peaks, a Model for Recurring Cascades

Authors:

Matteo Almanza,

Silvio Lattanzi,

Alessandro Panconesi,

Giuseppe ReAuthors Info & Claims

WWW '21: Proceedings of the Web Conference 2021

Pages 681 - 692

https://doi.org/10.1145/3442381.3449807

Published: 03 June 2021 Publication History

Abstract

Understanding information dynamics and their resulting cascades is a central topic in social network analysis. In a recent seminal work, Cheng et al. analyzed multiples cascades on Facebook over several months, and noticed that many of them exhibit a recurring behaviour. They tend to have multiple peaks of popularity, with periods of quiescence in between.

In this paper, we propose the first mathematical model that provably explains this interesting phenomenon, besides exhibiting other fundamental properties of information cascades. Our model is simple and shows that it is enough to have a good clustering structure to observe this interesting recurring behaviour with a standard information diffusion model. Furthermore, we complement our theoretical analysis with an experimental evaluation where we show that our model is able to reproduce the observed phenomenon on several social networks.

References

[1]

Emmanuel Abbe. 2017. Community detection and stochastic block models: recent developments. JMLR 18, 1 (2017), 6446–6531.

Digital Library

[2]

Lars Backstrom, Dan Huttenlocher, Jon Kleinberg, and Xiangyang Lan. 2006. Group formation in large social networks: membership, growth, and evolution. In KDD. 44–54.

[3]

Norman TJ Bailey 1975. The mathematical theory of infectious diseases and its applications. Charles Griffin & Company Ltd.

[4]

Albert-Laszlo Barabasi. 2005. The origin of bursts and heavy tails in human dynamics. Nature 435, 7039 (2005), 207.

[5]

Maurice S Bartlett. 1957. Measles periodicity and community size. J. Royal Stat. Soc., Ser. A (Gen.) 120, 1 (1957), 48–70.

[6]

Pavel Berkhin. 2005. A survey on pagerank computing. Internet Math. 2, 1 (2005), 73–120.

[7]

Ayan K Bhowmick, Martin Gueuning, Jean-Charles Delvenne, Renaud Lambiotte, and Bivas Mitra. 2017. Temporal pattern of (re) tweets reveal cascade migration. In ASONAM. 483–488.

[8]

Sushil Bikhchandani, David Hirshleifer, and Ivo Welch. 1992. A theory of fads, fashion, custom, and cultural change as informational cascades. JPE 100, 5 (Oct. 1992), 992–1026.

[9]

Ottar N Bjørnstad, Bärbel F Finkenstädt, and Bryan T Grenfell. 2002. Dynamics of measles epidemics: estimating scaling of transmission rates using a time series SIR model. Ecol. Monogr. 72, 2 (2002), 169–184.

[10]

Avrim Blum, John Hopcroft, and Ravi Kannan. 2016. Foundations of data science. Vorabversion eines Lehrbuchs(2016).

[11]

Justin Cheng, Lada A Adamic, Jon Kleinberg, and Jure Leskovec. 2016. Do Cascades Recur?. In WWW. 671–681.

[12]

Flavio Chierichetti, David Liben-nowell, and Jon Kleinberg. 2011. Reconstructing patterns of information diffusion from incomplete observations. In NIPS. 792–800.

[13]

Eunjoon Cho, Seth Myers, and Jure Leskovec. 2011. Friendship and mobility: user movement in location-based social networks. In KDD. 1082–1090.

[14]

Paul Erdős and Alfréd Rényi. 1960. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci 5, 1 (1960), 17–60.

[15]

Institute for Disease Modeling (IDM). 2019. SIR and SIRS models. https://docs.idmod.org/projects/emod-malaria/en/latest/model-sir.html

[16]

Adam Fourney, Miklos Z Racz, Gireeja Ranade, Markus Mobius, and Eric Horvitz. 2017. Geographic and Temporal Trends in Fake News Consumption During the 2016 US Presidential Election. In CIKM, Vol. 17. 6–10.

[17]

Michelle Girvan, Duncan S Callaway, Mark EJ Newman, and Steven H Strogatz. 2002. Simple model of epidemics with pathogen mutation. Phys. Rev. 65, 3 (2002).

[18]

Sharad Goel, Duncan J Watts, and Daniel G Goldstein. 2012. The structure of online diffusion networks. In EC2012. ACM, 623–638.

Digital Library

[19]

Daniel Gruhl, Ramanathan Guha, David Liben-Nowell, and Andrew Tomkins. 2004. Information diffusion through blogspace. In WWW. 491–501.

[20]

Tad Hogg and Kristina Lerman. 2012. Social dynamics of digg. EPJ Data Science 1, 1 (2012), 5.

[21]

Paul W Holland, Kathryn B Laskey, and Samuel Leinhardt. 1983. Stochastic blockmodels: First steps. Social networks 5, 2 (1983), 109–137.

[22]

Ting-Kai Huang, MD Sazzadur Rahman, Harsha V Madhyastha, Michalis Faloutsos, and Bruno Ribeiro. 2013. An Analysis of Socware Cascades in Online Social Networks. In WWW. 619–630.

[23]

Zhenhua Huang, Zhenyu Wang, Yingbo Zhu, Chengqi Yi, and Tingxuan Su. 2017. Prediction of Cascade Structure and Outbreaks Recurrence in Microblogs. In Chinese National Conference SMP2017. 53–64.

[24]

Anders Johansen. 1996. A simple model of recurrent epidemics. J. Theor. Biol. 178, 1 (1996), 45–51.

[25]

David Kempe, Jon Kleinberg, and Éva Tardos. 2003. Maximizing the Spread of Influence Through a Social Network. In KDD. 137–146.

[26]

David Kempe, Jon Kleinberg, and Éva Tardos. 2005. Influential nodes in a diffusion model for social networks. In ICALP2005. 1127–1138.

Digital Library

[27]

William O Kermack and Anderson G McKendrick. 1927. A contribution to the mathematical theory of epidemics. Proc. R. Soc. Lond., Ser. A (math. and phys.) 115, 772 (1927), 700–721.

[28]

Ravi Kumar, Mohammad Mahdian, and Mary McGlohon. 2010. Dynamics of conversations. In KDD. ACM, 553–562.

[29]

Jérôme Kunegis. 2013. KONECT: The Koblenz Network Collection. In WWW. 1343–1350.

Digital Library

[30]

Jure Leskovec, Lada A Adamic, and Bernardo A Huberman. 2007. The dynamics of viral marketing. TWEB 1, 1 (2007), 5.

Digital Library

[31]

Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http://snap.stanford.edu/data.

[32]

Jure Leskovec, Mary McGlohon, Christos Faloutsos, Natalie Glance, and Matthew Hurst. 2007. Cascading behavior in large blog graphs: Patterns and a model. SDM (2007), 551–556.

[33]

Jure Leskovec and Rok Sosič. 2016. Snap: A general-purpose network analysis and graph-mining library. TIST 8, 1 (2016), 1.

Digital Library

[34]

Dan Li, Meng Liu, Shengqiang Liu, 2015. The evolutionary dynamics of stochastic epidemic model with nonlinear incidence rate. Bull. Math. Biol. 77, 9 (2015), 1705–1743.

[35]

David Liben-Nowell and Jon Kleinberg. 2008. Tracing information flow on a global scale using Internet chain-letter data. PNAS 105, 12 (2008), 4633–4638.

[36]

Seth A Myers and Jure Leskovec. 2014. The bursty dynamics of the twitter information network. In WWW. 913–924.

[37]

Kazumasa Oida and Kyota Okubo. 2018. Adopter community formation accelerated by repeaters of product advertisement campaigns. IEEE Trans. Computat. Social Syst. 6, 1 (2018), 56–72.

[38]

Andrzej Pacuk, Piotr Sankowski, Karol Wegrzycki, and Piotr Wygocki. 2016. There is something beyond the twitter network. In HT. 279–284.

[39]

Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1999. The PageRank citation ranking: Bringing order to the web.Technical Report. Stanford InfoLab.

[40]

Romualdo Pastor-Satorras, Claudio Castellano, Piet Van Mieghem, and Alessandro Vespignani. 2015. Epidemic processes in complex networks. Rev. Mod. Phys. 87, 3 (2015), 925.

[41]

Zafarani Reza and Liu Huan. 2009. Social computing data repository. (2009).

[42]

Ganna Rozhnova and Ana Nunes. 2009. Fluctuations and oscillations in a simple epidemic model. Phys. Rev. 79, 4 (2009), 041922.

[43]

Elisa Shearer. 2018. Social media outpaces print newspapers in the U.S. as a news source. https://www.pewresearch.org/fact-tank/2018/12/10/social-media-outpaces-print-newspapers-in-the-u-s-as-a-news-source/

[44]

Lubos Takac and Michal Zabovsky. 2012. Data analysis in public social networks. In Int. Sci. Conf. and Int. Wksp Present Day Trends of Innovations, Vol. 1.

[45]

Gabriel Tarde. 1903. The Laws of Imitation. Henry Holt.

[46]

Yu Wang, Gao Cong, Guojie Song, and Kunqing Xie. 2010. Community-based greedy algorithm for mining top-k influential nodes in mobile social networks. In KDD. 1039–1048.

[47]

Duncan J Watts. 2002. A simple model of global cascades on random networks. PNAS 99, 9 (2002), 5766–5771.

[48]

Karol Wegrzycki, Piotr Sankowski, Andrzej Pacuk, and Piotr Wygocki. 2017. Why Do Cascade Sizes Follow a Power-Law?. In WWW. 569–576.

[49]

Jiang Yang and Scott Counts. 2010. Predicting the speed, scale, and range of information diffusion in twitter. In ICWSM.

[50]

Jaewon Yang and Jure Leskovec. 2013. Overlapping community detection at scale: a nonnegative matrix factorization approach. In WSDM. 587–596.

[51]

Jaewon Yang and Jure Leskovec. 2015. Defining and evaluating network communities based on ground-truth. KAIS 42, 1 (2015), 181–213.

Digital Library

[52]

Choujun Zhan, Fujian Wu, Zhenhua Huang, Wei Jiang, and Qizhi Zhang. 2020. Analysis of collective action propagation with multiple recurrences. Neur. Com. & Appl. (2020).

Cited By

Cao RLiu XFang ZXu XWang X(2023)How do scientific papers from different journal tiers gain attention on social media?Information Processing and Management: an International Journal10.1016/j.ipm.2022.10315260:1Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1016/j.ipm.2022.103152

Recommendations

Do Cascades Recur?
WWW '16: Proceedings of the 25th International Conference on World Wide Web

Cascades of information-sharing are a primary mechanism by which content reaches its audience on social media, and an active line of research has studied how such cascades, which form as content is reshared from person to person, develop and subside. In ...
A framework for quantitative analysis of cascades on networks
WSDM '11: Proceedings of the fourth ACM international conference on Web search and data mining

How does information flow in online social networks? How does the structure and size of the information cascade evolve in time? How can we efficiently mine the information contained in cascade dynamics? We approach these questions empirically and ...
Super-blockers and the Effect of Network Structure on Information Cascades
WWW '18: Companion Proceedings of the The Web Conference 2018

Modelling information cascades over online social networks is important in fields from marketing to civil unrest prediction, however the underlying network structure strongly affects the probability and nature of such cascades. Even with simple cascade ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WWW '21: Proceedings of the Web Conference 2021

April 2021

4054 pages

ISBN:9781450383127

DOI:10.1145/3442381

Editors:
Jure Leskovec
Stanford
,
Marko Grobelnik
Jožef Stefan Institute
,
Marc Najork
Google
,
Jie Tang
Tsinghua University
,
Leila Zia
Wikimedia Foundation

Copyright © 2021 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

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 June 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

WWW '21

Sponsor:

SIGWEB

WWW '21: The Web Conference 2021

April 19 - 23, 2021

Ljubljana, Slovenia

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
190
Total Downloads

Downloads (Last 12 months)19
Downloads (Last 6 weeks)1

Reflects downloads up to 29 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cao RLiu XFang ZXu XWang X(2023)How do scientific papers from different journal tiers gain attention on social media?Information Processing and Management: an International Journal10.1016/j.ipm.2022.10315260:1Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1016/j.ipm.2022.103152

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Table of Contents