Top

Social Network Analysis and Mining

Published in:

01-12-2020 | Original Article

Lifetime distribution of information diffusion on simultaneously growing networks

Author: Emily M. Fischer

Published in: Social Network Analysis and Mining | Issue 1/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This paper studies information diffusion modeled by the SIS epidemic model on several classes of growing networks. It is shown through a thorough simulation study that there is a fundamental difference in the behavior of epidemic processes on growing temporal networks in comparison with the same processes on static networks. An infection under the SIS model tends to persist longer on a growing network than on a static network, and further, the empirical distribution of the lifetime of an infection on growing networks has a considerably heavier tail. In fact, evidence is provided that, under certain combinations of model parameters, it may be possible for an infection to survive for an infinite amount of time. These results are observed for the SIS model acting on growing temporal networks generated via the preferential attachment model and a uniform attachment model, as well as a real-world, time-stamped citation network.

previous article A Twitter-based approach of news media impartiality in multipartite political scenes

next article A graph modification approach for k-anonymity in social networks using the genetic algorithm

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Albano A, Guillaume JL, Heymann S, Grand BL (2015) Studying graph dynamics through intrinsic time based diffusion analysis. Springer, Cham, pp 103–124

Antonakaki D, Ioannidis S, Fragopoulou P (2018) Utilizing the average node degree to assess the temporal growth rate of Twitter. Soc Netw Anal Min 8(1):1–11. https://doi.org/10.1007/s13278-018-0490-5CrossRef

Bakshy E, Rosenn I, Marlow C, Adamic L (2012) The role of social networks in information diffusion. In: Proceedings of the 21st international conference on World Wide Web, WWW’12. ACM, New York, pp 519–528. https://doi.org/10.1145/2187836.2187907

Barabási AL, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509–512. https://doi.org/10.1126/science.286.5439.509MathSciNetCrossRefMATH

Barbour AD (1975) The duration of the closed stochastic epidemic. Biometrika 62(2):477–482. https://doi.org/10.1093/biomet/62.2.477MathSciNetCrossRefMATH

Barthélemy M, Barrat A, Pastor-Satorras R, Vespignani A (2005) Dynamical patterns of epidemic outbreaks in complex heterogeneous networks. J Theor Biol 235(2):275–288. https://doi.org/10.1016/j.jtbi.2005.01.011MathSciNetCrossRefMATH

Basaras P, Katsaros D (2019) Identifying influential spreaders in complex networks with probabilistic links. Springer, Cham, pp 57–84. https://doi.org/10.1007/978-3-319-78256-0_4CrossRef

Battiston F, Nicosia V, Latora V (2017) The new challenges of multiplex networks: measures and models. Eur Phys J Spec Top 226(3):401–416. https://doi.org/10.1140/EPJST/E2016-60274-8CrossRef

Boccaletti S, Bianconi G, Criado R, del Genio CI, Gómez-Gardeñes J, Romance M, Sendiña-Nadal I, Wang Z, Zanin M (2014) The structure and dynamics of multilayer networks. Phys Rep. https://doi.org/10.1016/j.physrep.2014.07.001MathSciNetCrossRef

Boguñá M, Castellano C, Pastor-Satorras R (2013) Nature of the epidemic threshold for the susceptible-infected-susceptible dynamics in networks. Phys Rev Lett 111(6):068701. https://doi.org/10.1103/PhysRevLett.111.068701. arXiv:1305.4819CrossRef

Bollobás B, Riordan O, Spencer J, Tusnády G (2001) The degree sequence of a scale-free random graph process. Random Struct Algorithms 18(3):279–290. https://doi.org/10.1002/rsa.1009MathSciNetCrossRefMATH

Bouanan Y, Forestier M, Ribault J, Zacharewicz G, Vallespir B (2017) Diffusion process in a multi-dimension networks: generating, modelling, and simulation. Springer, Cham, pp 199–225. https://doi.org/10.1007/978-3-319-51049-1_9CrossRef

Callaway DS, Hopcroft JE, Kleinberg JM, Newman ME, Strogatz SH (2001) Are randomly grown graphs really random? Phys Rev E Stat Phys Plasmas Fluids Related Interdiscip Top 64(4):7. https://doi.org/10.1103/PhysRevE.64.041902CrossRef

Cloteaux B, Marbukh V (2019) SIS contagion avoidance on a network growing by preferential attachment. In: Proceedings of the ACM SIGACT-SIGMOD-SIGART symposium on principles of database systems. Association for Computing Machinery, New York, New York, pp 1–4. https://doi.org/10.1145/3327964.3328502

Demirel G, Barter E, Gross T (2017) Dynamics of epidemic diseases on a growing adaptive network. Sci Rep 7:42352. https://doi.org/10.1038/srep42352CrossRef

Dorogovtsev SN, Mendes JFF (2000) Scaling behaviour of developing and decaying networks. EPL (Europhys Lett) 52(1):33. https://doi.org/10.1209/EPL/I2000-00400-0CrossRef

Ferreira SC, Castellano C, Pastor-Satorras R (2012) Epidemic thresholds of the susceptible-infected-susceptible model on networks: a comparison of numerical and theoretical results. Phys Rev E 86(4):041125. https://doi.org/10.1103/PhysRevE.86.041125CrossRef

Fischer EM, Ghosh S, Samorodnitsky G (2019) Epidemic threshold and lifetime distribution for information diffusion on simultaneously growing networks. In: International conference on advances in social networks analysis and mining, ASONAM’19. ACM, pp 242–249, https://doi.org/10.1145/3341161.3342891

Ganesh A, Massoulie L, Towsley D (2005) The effect of network topology on the spread of epidemics. In: Proceedings IEEE 24th annual joint conference of the IEEE computer and communications societies, vol 2, pp 1455–1466. https://doi.org/10.1109/INFCOM.2005.1498374

Ganguly A, Mehta T, Patel T, Sundaram R, Tiwari D (2020) Resilience and coevolution of preferential interdependent networks. Soc Netw Anal Min 10(1):1–12. https://doi.org/10.1007/s13278-019-0614-6CrossRef

Gehrke J, Ginsparg P, Kleinberg J (2003) Overview of the 2003 KDD Cup. Tech rep, www.cs.cornell.edu/projects/kddcup

Gross T, D’Lima CJ, Blasius B (2006) Epidemic dynamics on an adaptive network. Phys Rev Lett 96(20):208701. https://doi.org/10.1103/PhysRevLett.96.208701CrossRef

Guerra B, Gómez-Gardeñes J (2010) Annealed and mean-field formulations of disease dynamics on static and adaptive networks. Phys Rev E 82:035101. https://doi.org/10.1103/PhysRevE.82.035101CrossRef

Guille A, Hacid H, Favre C, Zighed DA (2013) Information diffusion in online social networks: a survey. SIGMOD Rec 42(2):17–28. https://doi.org/10.1145/2503792.2503797CrossRef

Holme P, Saramäki J (2012) Temporal networks. Phys Rep 519(3):97–125. https://doi.org/10.1016/j.physrep.2012.03.001CrossRef

Iribarren JL, Moro E (2009) Impact of human activity patterns on the dynamics of information diffusion. Phys Rev Lett 103(3):038702. https://doi.org/10.1103/PhysRevLett.103.038702CrossRef

Karsai M, Kivelä M, Pan RK, Kaski K, Kertész J, Barabási AL, Saramäki J (2011) Small but slow world: how network topology and burstiness slow down spreading. Phys Rev E Stat Nonlinear Soft Matter Phys 83(2):025102. https://doi.org/10.1103/PhysRevE.83.025102CrossRef

Kiss IZ, Miller JC, Simon PL (2017) Mathematics of epidemics on networks, interdisciplinary applied mathematics, vol 46. Springer, Cham. https://doi.org/10.1007/978-3-319-50806-1CrossRef

Kivelä M, Arenas A, Barthelemy M, Gleeson JP, Moreno Y, Porter MA (2014) Multilayer networks. J Complex Netw 2(3):203–271. https://doi.org/10.1093/COMNET/CNU016CrossRef

Krapivsky PL, Redner S (2001) Organization of growing random networks. Phys Rev E Stat Phys Plasmas Fluids Related Interdiscip Top 63(6):066123. https://doi.org/10.1103/PhysRevE.63.066123CrossRef

Leitch J, Alexander KA, Sengupta S (2019) Toward epidemic thresholds on temporal networks: a review and open questions. Appl Netw Sci. https://doi.org/10.1007/s41109-019-0230-4CrossRef

Leskovec J, Kleinberg J, Faloutsos C (2005) Graphs over time: densification laws, shrinking diameters and possible explanations. In: ACM SIGKDD international conference on knowledge discovery and data mining, KDD

Li A, Cornelius SP, Liu YY, Wang L, Barabási AL (2017) The fundamental advantages of temporal networks. Science 358(6366):1042–1046. https://doi.org/10.1126/science.aai7488CrossRef

Liu QH, Xiong X, Zhang Q, Perra N (2018) Epidemic spreading on time-varying multiplex networks. Phys Rev E. https://doi.org/10.1103/PhysRevE.98.062303CrossRef

Mahmoudi A, Yaakub MR, Abu Bakar A (2018) A new method to discretize time to identify the milestones of online social networks. Soc Netw Anal Min 8(1):1–20. https://doi.org/10.1007/s13278-018-0511-4CrossRef

Masuda N, Holme P (eds) (2017) Temporal network epidemiology. Theoretical biology. Springer, Singapore. https://doi.org/10.1007/978-981-10-5287-3CrossRef

Min B, Goh KI, Vazquez A (2011) Spreading dynamics following bursty human activity patterns. Phys Rev E Stat Nonlinear Soft Matter Phys 83(3):036102. https://doi.org/10.1103/PhysRevE.83.036102CrossRef

Mussumeci E, Coelho FC (2018) Reconstructing news spread networks and studying its dynamics. Soc Netw Anal Min 8(1):1–8. https://doi.org/10.1007/s13278-017-0483-9CrossRef

Nadini M, Sun K, Ubaldi E, Starnini M, Rizzo A, Perra N (2018) Epidemic spreading in modular time-varying networks. Sci Rep 8(1):2352. https://doi.org/10.1038/s41598-018-20908-xCrossRef

Newman MEJ (2002) Spread of epidemic disease on networks. Phys Rev E 66:016128. https://doi.org/10.1103/PhysRevE.66.016128MathSciNetCrossRef

Pastor-Satorras R, Vespignani A (2002) Epidemic dynamics in finite size scale-free networks. Phys Rev E Stat Phys Plasmas Fluids Related Interdiscip Top 65(3):035108. https://doi.org/10.1103/PhysRevE.65.035108CrossRef

Pastor-Satorras R, Castellano C, Van Mieghem P, Vespignani A (2015) Epidemic processes in complex networks. Rev Mod Phys 87:925–979. https://doi.org/10.1103/RevModPhys.87.925MathSciNetCrossRef

Pellis L, Ball F, Bansal S, Eames K, House T, Isham V, Trapman P (2015) Eight challenges for network epidemic models. Epidemics 10:58–62. https://doi.org/10.1016/j.epidem.2014.07.003CrossRef

Perra N, Gonçalves B, Pastor-Satorras R, Vespignani A (2012) Activity driven modeling of time varying networks. Sci Rep 2(1):1–7. https://doi.org/10.1038/srep00469CrossRef

Pozzana I, Sun K, Perra N (2017) Epidemic spreading on activity-driven networks with attractiveness. Phys Rev E. https://doi.org/10.1103/PhysRevE.96.042310CrossRef

Prakash BA, Tong H, Valler N, Faloutsos M, Faloutsos C (2010) Virus propagation on time-varying networks: theory and immunization algorithms. In: Lecture notes in computer science (including subseries lecture notes in artificial intelligence and lecture notes in bioinformatics) LNAI, vol 6323. Springer, Berlin, pp 99–114. https://doi.org/10.1007/978-3-642-15939-8_7

Rocha LE, Blondel VD (2013) Bursts of vertex activation and epidemics in evolving networks. PLoS Comput Biol 9(3):e1002974. https://doi.org/10.1371/journal.pcbi.1002974MathSciNetCrossRef

Sanatkar MR (2020) The dynamics of polarized beliefs in networks governed by viral diffusion and media influence. Soc Netw Anal Min 10(1):1–21. https://doi.org/10.1007/s13278-020-0627-1CrossRef

Saramäki J, Kaski K (2005) Modelling development of epidemics with dynamic small-world networks. J Theor Biol 234(3):413–421. https://doi.org/10.1016/j.jtbi.2004.12.003MathSciNetCrossRefMATH

Sarkar S, Guo R, Shakarian P (2019) Using network motifs to characterize temporal network evolution leading to diffusion inhibition. Soc Netw Anal Min 9(1):1–24. https://doi.org/10.1007/s13278-019-0556-zCrossRef

Scarpino SV, Petri G (2019) On the predictability of infectious disease outbreaks. Nat Commun. https://doi.org/10.1038/s41467-019-08616-0CrossRef

Simon PL, Kiss IZ (2005) From exact stochastic to mean-field ODE models: a new approach to prove convergence results. IMA J Appl Math. https://doi.org/10.1093/imamat/dri017CrossRefMATH

Simon PL, Taylor M, Kiss IZ (2011) Exact epidemic models on graphs using graph-automorphism driven lumping. J Math Biol 62(4):479–508. https://doi.org/10.1007/s00285-010-0344-xMathSciNetCrossRefMATH

SNAP (2003) Dataset cit-HepTh. http://snap.stanford.edu/data/cit-HepTh.html

Song B, Song YR, Jiang GP, Xia LL (2019) Dynamical rewiring in adaptive weighted heterogeneous networks. Int J Modern Phys. https://doi.org/10.1142/S0217979219500693MathSciNetCrossRefMATH

St-Onge G, Young JG, Laurence E, Murphy C, Dubé LJ (2018) Phase transition of the susceptible-infected-susceptible dynamics on time-varying configuration model networks. Phys Rev E. https://doi.org/10.1103/PhysRevE.97.022305CrossRef

Takaguchi T, Masuda N, Holme P (2013) Bursty communication patterns facilitate spreading in a threshold-based epidemic dynamics. PLoS ONE 8(7):e68629. https://doi.org/10.1371/journal.pone.0068629CrossRef

Taylor M, Taylor TJ, Kiss IZ (2012) Epidemic threshold and control in a dynamic network. Phys Rev E Stat Nonlinear Soft Matter Phys 85(1):016103. https://doi.org/10.1103/PhysRevE.85.016103CrossRef

Valdano E, Ferreri L, Poletto C, Colizza V (2015) Analytical computation of the epidemic threshold on temporal networks. Phys Rev X 5:021005. https://doi.org/10.1103/PhysRevX.5.021005CrossRef

Valdano E, Fiorentin MR, Poletto C, Colizza V (2018) Epidemic threshold in continuous-time evolving networks. Phys Rev Lett 120:068302. https://doi.org/10.1103/PhysRevLett.120.068302CrossRef

Van Mieghem P (2013) Decay towards the overall-healthy state in SIS epidemics on networks. arXiv:13103980 [cond-mat, physics:physics] https://www.nas.ewi.tudelft.nl/people/Piet/papers/TUD20131016_SISdecay_rate.pdfhttp://arxiv.org/abs/1310.3980%5Cnhttp://www.arxiv.org/pdf/1310.3980.pdf

Van Mieghem P, Stevanović D, Kuipers F, Li C, van de Bovenkamp R, Liu D, Wang H (2011) Decreasing the spectral radius of a graph by link removals. Phys Rev E 84:016101. https://doi.org/10.1103/PhysRevE.84.016101CrossRef

Watts DJ, Strogatz SH (1998) Collective dynamics of ‘small-world’ networks. Nature 393:440–442. https://doi.org/10.1038/30918CrossRefMATH

Woo J, Chen H (2016) Epidemic model for information diffusion in web forums: experiments in marketing exchange and political dialog. SpringerPlus 5(1):66. https://doi.org/10.1186/s40064-016-1675-xCrossRef

Zhang X, Shan C, Jin Z, Zhu H (2019) Complex dynamics of epidemic models on adaptive networks. J Differ Equ 266(1):803–832. https://doi.org/10.1016/j.jde.2018.07.054MathSciNetCrossRefMATH

Zhou R, Wu Q (2019) Epidemic spreading dynamics on complex networks with adaptive social-support. Phys A Stat Mech Appl 525:778–787. https://doi.org/10.1016/j.physa.2019.03.107MathSciNetCrossRef

Title: Lifetime distribution of information diffusion on simultaneously growing networks
Author: Emily M. Fischer
Publication date: 01-12-2020
Publisher: Springer Vienna
Published in: Social Network Analysis and Mining / Issue 1/2020
Print ISSN: 1869-5450
Electronic ISSN: 1869-5469
DOI: https://doi.org/10.1007/s13278-020-00651-w

On detecting urgency in short crisis messages using minimal supervision and transfer learning

Original Article

Using complex networks to identify patterns in specialty mathematical language: a new approach

Original Article

Mining latent academic social relationships by network fusion of multi-type data

Original Article

Achieving spectral localization of network using betweenness-based edge perturbation

Original Article

Automatic extraction of urban outdoor perception from geolocated free texts

Review Paper

Networked experiments and modeling for producing collective identity in a group of human subjects using an iterative abduction framework

Original Article

Springer Professional

Lifetime distribution of information diffusion on simultaneously growing networks

Abstract

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2020

On detecting urgency in short crisis messages using minimal supervision and transfer learning

Using complex networks to identify patterns in specialty mathematical language: a new approach

Mining latent academic social relationships by network fusion of multi-type data

Achieving spectral localization of network using betweenness-based edge perturbation

Automatic extraction of urban outdoor perception from geolocated free texts

Networked experiments and modeling for producing collective identity in a group of human subjects using an iterative abduction framework

Premium Partner

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

On detecting urgency in short crisis messages using minimal supervision and transfer learning

Using complex networks to identify patterns in specialty mathematical language: a new approach

Mining latent academic social relationships by network fusion of multi-type data

Achieving spectral localization of network using betweenness-based edge perturbation

Automatic extraction of urban outdoor perception from geolocated free texts

Networked experiments and modeling for producing collective identity in a group of human subjects using an iterative abduction framework