research-article

Why Do Cascade Sizes Follow a Power-Law?

Authors:

Karol Wegrzycki,

Piotr Sankowski,

Piotr WygockiAuthors Info & Claims

WWW '17: Proceedings of the 26th International Conference on World Wide Web

Pages 569 - 576

https://doi.org/10.1145/3038912.3052565

Published: 03 April 2017 Publication History

Abstract

We introduce random directed acyclic graph and use it to model the information diffusion network. Subsequently, we analyze the cascade generation model (CGM) introduced by Leskovec et al. [19]. Until now only empirical studies of this model were done. In this paper, we present the first theoretical proof that the sizes of cascades generated by the CGM follow the power-law distribution, which is consistent with multiple empirical analysis of the large social networks. We compared the assumptions of our model with the Twitter social network and tested the goodness of approximation.

References

[1]

D. Achlioptas, A. Clauset, D. Kempe, and C. Moore. On the bias of traceroute sampling: Or, power-law degree distributions in regular graphs. J. ACM, 56(4):21:1--21:28, 2009.

Digital Library

[2]

M. Barthelemy, A. Barrat, and A. Vespignani. The role of geography and traffic in the structure of complex networks. Advances in Complex Systems, 10(1):5--28, 2007.

[3]

N. Bayley. The mathematical theory of epidemics. Griffin, London, 1975.

[4]

Z. Beerliova, F. Eberhard, T. Erlebach, A. Hall, M. Hoffmann, M. Mihal'ak, and L. S. Ram. Network discovery and verification. IEEE Journal on selected areas in communications, 24(12):2168--2181, 2006.

[5]

P. Brach, M. Cygan, J. Lacki, and P. Sankowski.Algorithmic complexity of power law networks. InR. Krauthgamer, editor,Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10--12, 2016, pages 1306--1325. SIAM, 2016.

Digital Library

[6]

P. Brach, A. Epasto, A. Panconesi, and P. Sankowski. Spreading rumours without the network. In A. Sala, A. Goel, and K. P. Gummadi, editors,Proceedings of the second ACM conference on Online social networks, COSN 2014, Dublin, Ireland, October 1-2, 2014, pages 107--118. ACM, 2014.

Digital Library

[7]

J. Cheng, L. A. Adamic, J. M. Kleinberg, and J. Leskovec. Do cascades recur? In J. Bourdeau,J. Hendler, R. Nkambou, I. Horrocks, and B. Y. Zhao, editors, Proceedings of the 25th International Conference on World Wide Web, WWW 2016, Montreal, Canada, April 11-15, 2016, pages 671--681. ACM, 2016.

Digital Library

[8]

B. Cui, S. J. Yang, and C. Homan. Non-independent cascade formation: Temporal and spatial effects. In J. Li, X. S. Wang, M. N. Garofalakis, I. Soboroff, T. Suel, and M. Wang, editors, Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, CIKM 2014, Shanghai, China, November 3-7, 2014, pages 1923--1926. ACM, 2014.

Digital Library

[9]

P. Erdös and A. Rényi. On the evolution of random graphs. In PUBLICATION OF THE MATHEMATICAL INSTITUTE OF THE HUNGARIAN ACADEMY OF SCIENCES, pages 17--61, 1960.

[10]

A. Gaba, S. Voulgaris, K. Iwanicki, and M. van Steen. Revisiting gossip-based ad-hoc routing. In WiMAN 2012: Proceedings of the 6th International Workshop on Wireless Mesh and Ad Hoc Networks, Munich, Germany, July 2012. IEEE.

[11]

R. Ghosh and B. A. Huberman. Ultrametricity of information cascades. CoRR, abs/1310.2619, 2013.

[12]

S. Havlin, N. A. M. Araujo, S. V. Buldyrev, C. S. Dias, R. Parshani, G. Paul, and H. E. Stanley. Catastrophic cascade of failures in interdependent networks. CoRR, abs/1012.0206, 2010.

[13]

J. L. Iribarren and E. Moro. Branching dynamics of viral information spreading. CoRR, abs/1110.1884, 2011.

[14]

D. Kempe, J. M. Kleinberg, and E. Tardos. Maximizing the spread of influence through a social network. In L. Getoor, T. E. Senator, P. M. Domingos, and C. Faloutsos, editors, Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 24-27, 2003, pages 137--146. ACM, 2003.

Digital Library

[15]

S. Krishnan, P. Butler, R. Tandon, J. Leskovec, and N. Ramakrishnan. Seeing the forest for the trees: new approaches to forecasting cascades. In W. Nejdl, W. Hall, P. Parigi, and S. Staab, editors, Proceedings of the 8th ACM Conference on Web Science, WebSci 2016, Hannover, Germany, May 22-25, 2016, pages 249--258. ACM, 2016.

Digital Library

[16]

M. Kurant, A. Markopoulou, and P. Thiran. On the bias of bfs (breadth first search). In Teletraffic Congress (ITC), 2010 22nd International, pages 1--8. IEEE, 2010.

[17]

K. Lerman and R. Ghosh. Information contagion: An empirical study of the spread of news on digg and twitter social networks. In W. W. Cohen and S. Gosling, editors, Proceedings of the Fourth International Conference on Weblogs and Social Media, ICWSM 2010, Washington, DC, USA, May 23-26, 2010. The AAAI Press, 2010.

[18]

J. Leskovec, L. A. Adamic, and B. A. Huberman. The dynamics of viral marketing. TWEB, 1(1), 2007.

Digital Library

[19]

J. Leskovec, M. McGlohon, C. Faloutsos, N. S. Glance, and M. Hurst. Patterns of cascading behavior in large blog graphs. In Proceedings of the Seventh SIAM International Conference on Data Mining, April 26-28, 2007, Minneapolis, Minnesota, USA, pages 551--556. SIAM, 2007.

[20]

A. Pacuk, P. Sankowski, K. Wegrzycki, and P. Wygocki. There is something beyond the twitter network. In J. Blustein, E. Herder, J. Rubart, and H. Ashman, editors, Proceedings of the 27th ACM Conference on Hypertext and Social Media, HT 2016, Halifax, NS, Canada, July 10-13, 2016, pages 279--284. ACM, 2016.

Digital Library

[21]

A. Pacuk, P. Sankowski, K. Wgrzycki, and P. Wygocki. Python code of experiments and results. http://social-networks.mimuw.edu.pl/#rdag, 2017.

[22]

A. Pacuk, P. Sankowski, K. Wegrzycki, and P. Wygocki. Twitter anonymised graph. http://social-networks.mimuw.edu.pl/#beyond, 2017.

[23]

E. M. Rogers. Diffusion of innovations. Free Press, 2010.

[24]

G. V. Steeg, R. Ghosh, and K. Lerman. What stops social epidemics? In L. A. Adamic, R. A. Baeza-Yates, and S. Counts, editors, Proceedings of the Fifth International Conference on Weblogs and Social Media, Barcelona, Catalonia, Spain, July 17-21, 2011. The AAAI Press, 2011.

[25]

D. Stutzbach, R. Rejaie, N. Duffield, S. Sen, and W. Willinger. On unbiased sampling for unstructured peer-to-peer networks. IEEE/ACM Transactions on Networking (TON), 17(2):377--390, 2009.

Digital Library

[26]

D. J. Watts. A simple model of global cascades on random networks. In Proceedings of the National Academy of Sciences of the United States of America, volume 99, pages 5766--5771, April 30 2002. http://www.jstor.org/view/00278424/sp020038/02x3936j/0.

[27]

Q. Zhao, M. A. Erdogdu, H. Y. He, A. Rajaraman, and J. Leskovec. SEISMIC: A self-exciting point process model for predicting tweet popularity. In L. Cao, C. Zhang, T. Joachims, G. I. Webb, D. D. Margineantu, and G. Williams, editors, Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, Australia, August 10-13, 2015, pages 1513--1522. ACM, 2015

Digital Library

Cited By

Meng FXie JMa XWang JHu Y(2024)Predictability of information spreading on online social networksInternational Journal of Modern Physics C10.1142/S0129183124501699Online publication date: 29-Jun-2024
https://doi.org/10.1142/S0129183124501699
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: 20-Jan-2023
https://dl.acm.org/doi/10.1016/j.ipm.2022.103152
Oida K(2023)Information cascade final size distributions derived from urn modelsApplied Network Science10.1007/s41109-023-00554-78:1Online publication date: 7-Jun-2023
https://doi.org/10.1007/s41109-023-00554-7
Show More Cited By

Index Terms

Why Do Cascade Sizes Follow a Power-Law?
1. Applied computing
  1. Law, social and behavioral sciences
    1. Sociology
2. Computing methodologies
  1. Modeling and simulation
    1. Model development and analysis
      1. Model verification and validation
    2. Simulation theory
      1. Network science

Recommendations

Correcting for missing data in information cascades
WSDM '11: Proceedings of the fourth ACM international conference on Web search and data mining

Transmission of infectious diseases, propagation of information, and spread of ideas and influence through social networks are all examples of diffusion. In such cases we say that a contagion spreads through the network, a process that can be modeled by ...
Modelling information diffusion based on non-dominated friends in social networks

In recent years, social networks have played a strong role in diffusing information among people all around the globe. Therefore, the ability to analyse the diffusion pattern is essential. A diffusion model can identify the information dissemination ...
There is Something Beyond the Twitter Network
HT '16: Proceedings of the 27th ACM Conference on Hypertext and Social Media

How information spreads through a social network? Can we assume, that the information is spread only through a given social network graph? What is the correct way to compare the models of information flow? These are the basic questions we address in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

WWW '17: Proceedings of the 26th International Conference on World Wide Web

April 2017

1678 pages

ISBN:9781450349130

General Chairs:
Rick Barrett
W3Events
,
Rick Cummings
Murdoch University
,
Program Chairs:
Eugene Agichtein
Emory University
,
Evgeniy Gabrilovich
Google Research

Copyright © 2017 Copyright is held by the International World Wide Web Conference Committee (IW3C2).

Sponsors

IW3C2: International World Wide Web Conference Committee

In-Cooperation

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

Publisher

International World Wide Web Conferences Steering Committee

Republic and Canton of Geneva, Switzerland

Publication History

Published: 03 April 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

FET IP
NCN
ERC
polish funds for years 2013-2016 for co-financed international projects

Conference

WWW '17

Sponsor:

IW3C2

WWW '17: 26th International World Wide Web Conference

April 3 - 7, 2017

Perth, Australia

Acceptance Rates

WWW '17 Paper Acceptance Rate 164 of 966 submissions, 17%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
215
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)2

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Meng FXie JMa XWang JHu Y(2024)Predictability of information spreading on online social networksInternational Journal of Modern Physics C10.1142/S0129183124501699Online publication date: 29-Jun-2024
https://doi.org/10.1142/S0129183124501699
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: 20-Jan-2023
https://dl.acm.org/doi/10.1016/j.ipm.2022.103152
Oida K(2023)Information cascade final size distributions derived from urn modelsApplied Network Science10.1007/s41109-023-00554-78:1Online publication date: 7-Jun-2023
https://doi.org/10.1007/s41109-023-00554-7
Péron G(2022)Reproductive skews of territorial species in heterogeneous landscapesOikos10.1111/oik.096272023:2Online publication date: 21-Oct-2022
https://doi.org/10.1111/oik.09627
Notarmuzi DCastellano CFlammini AMazzilli DRadicchi F(2022)Universality, criticality and complexity of information propagation in social mediaNature Communications10.1038/s41467-022-28964-813:1Online publication date: 14-Mar-2022
https://doi.org/10.1038/s41467-022-28964-8
Cai SLiu PHuang P(2021)Temporal propagating network approach to long-term evolutionary process of public opinionInternational Journal of Modern Physics C10.1142/S012918312150048032:04(2150048)Online publication date: 6-Jan-2021
https://doi.org/10.1142/S0129183121500480
Chen XZhou FZhang KTrajcevski GZhong TZhang F(2019)Information Diffusion Prediction via Recurrent Cascades Convolution2019 IEEE 35th International Conference on Data Engineering (ICDE)10.1109/ICDE.2019.00074(770-781)Online publication date: Apr-2019
https://doi.org/10.1109/ICDE.2019.00074
Notarmuzi DCastellano C(2018)Analytical study of quality-biased competition dynamics for memes in social mediaEPL (Europhysics Letters)10.1209/0295-5075/122/28002122:2(28002)Online publication date: 19-Jun-2018
https://doi.org/10.1209/0295-5075/122/28002

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.

Media

Figures

Other

Tables

View Table of Contents