Relay-Linking Models for Prominence and Obsolescence in Evolving Networks

ABSTRACT

The rate at which nodes in evolving social networks acquire links (friends, citations) shows complex temporal dynamics. Preferential attachment and link copying models, while enabling elegant analysis, only capture rich-gets-richer effects, not aging and decline. Recent aging models are complex and heavily parameterized; most involve estimating 1-3 parameters per node. These parameters are intrinsic: they explain decline in terms of events in the past of the same node, and do not explain, using the network, where the linking attention might go instead. We argue that traditional characterization of linking dynamics are insufficient to judge the faithfulness of models. We propose a new temporal sketch of an evolving graph, and introduce several new characterizations of a network's temporal dynamics. Then we propose a new family of frugal aging models with no per-node parameters and only two global parameters. Our model is based on a surprising inversion or undoing of triangle completion, where an old node relays a citation to a younger follower in its immediate vicinity. Despite very few parameters, the new family of models shows remarkably better fit with real data. Before concluding, we analyze temporal signatures for various research communities yielding further insights into their comparative dynamics. To facilitate reproducible research, we shall soon make all the codes and the processed dataset available in the public domain.

References

1. Odd Aalen, Ornulf Borgan, and Hakon Gjessing. 2008. Survival and event history analysis: a process point of view. Springer.
2. Réka Albert and Albert-László Barabási. 2002. Statistical mechanics of complex networks. Reviews of modern physics 74, 1 (2002), 47.
3. Emmanuel Bacry, Stéphane Gaïffas, Iacopo Mastromatteo, and Jean-François Muzy. 2015. Mean-field inference of Hawkes point processes. arXiv/1511.01512 (2015). http://arxiv.org/pdf/1511.01512.pdf
4. Somendra M Bhattacharjee and Flavio Seno. 2001. A measure of data collapse for scaling. J. Physics A: Mathematical and General 34, 33 (2001), 6375. http: //arxiv.org/pdf/cond-mat/0102515v2.pdf
5. Tanmoy Chakraborty, Suhansanu Kumar, Pawan Goyal, Niloy Ganguly, and Animesh Mukherjee. 2014. Towards a Stratified Learning Approach to Predict Future Citation Counts. In Proceedings of the 14th ACM/IEEE-CS Joint Conference on Digital Libraries (JCDL '14). IEEE Press, 351--360.
6. Tanmoy Chakraborty, Suhansanu Kumar, Pawan Goyal, Niloy Ganguly, and Animesh Mukherjee. 2015. On the Categorization of Scientific Citation Profiles in Computer Science. Commun. ACM 58, 9 (Aug. 2015), 82--90. DOI: http://dx. doi.org/10.1145/2701412
7. Junghoo Cho, Sourashis Roy, and Robert E Adams. 2005. Page quality: In search of an unbiased Web ranking. In SIGMOD conference. ACM, 551--562.
8. Franco Dalfovo, Stefano Giorgini, Lev P Pitaevskii, and Sandro Stringari. 1999. Theory of Bose-Einstein condensation in trapped gases. Reviews of Modern Physics 71, 3 (1999), 463.
9. Derek J. de Solla Price. 1965. Networks of Scientific Papers. Science 149, 3683 (1965), 510--515. DOI: http://dx.doi.org/10.1126/science.149.3683.510arXiv:http://science.sciencemag.org/content/149/3683/510.full.pdf
10. Sergey N Dorogovtsev and José Fernando F Mendes. 2000. Evolution of networks with aging of sites. Physical Review E 62, 2 (2000), 1842.
11. Mehrdad Farajtabar, Yichen Wang, Manuel Gomez-Rodriguez, Shuang Li, Hongyuan Zha, and Le Song. 2015. COEVOLVE: A Joint Point Process Model for Information Diffusion and Network Co-evolution. CoRR abs/1507.02293 (2015). http://arxiv.org/abs/1507.02293
12. Eugene Garfield. 2006. The history and meaning of the journal impact factor. JAMA 295, 1 (2006), 90--93.
13. Kamalika Basu Hajra and Parongama Sen. 2005. Aging in citation networks. Physica A: Statistical Mechanics and its Applications 346, 1 (2005), 44--48.
14. Petter Holme and Beom Jun Kim. 2002. Growing scale-free networks with tunable clustering. Phys. Rev. E 86 (2002), 026107-(1--5).
15. Hawoong Jeong, Zoltan Néda, and Albert-László Barabási. 2003. Measuring preferential attachment in evolving networks. EPL (Europhysics Letters) 61, 4 (2003), 567.
16. Qing Ke, Emilio Ferrara, Filippo Radicchi, and Alessandro Flammini. 2015. Defining and identifying Sleeping Beauties in science. Proceedings of the National Academy of Sciences (2015), 201424329.
17. Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, D Sivakumar, Andrew Tomkins, and Eli Upfal. 2000. Random graph models for the web graph.. In FOCS. 57--65.
18. Jure Leskovec, Lars Backstrom, Ravi Kumar, and Andrew Tomkins. 2008. Microscopic evolution of social networks. In SIGKDD Conference. 462--470. http: //www-cs.stanford.edu/people/jure/pubs/microEvol-kdd08.pdf
19. Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. 2005. Graphs over time: densification laws, shrinking diameters and possible explanations. In SIGKDD Conference. 177--187.
20. Yu-Ying Liu, Shuang Li, Fuxin Li, Le Song, and James M Rehg. 2015. Efficient Learning of Continuous-Time Hidden Markov Models for Disease Progression. In NIPS. 3599--3607.
21. Sandeep Pandey, Sourashis Roy, Christopher Olston, Junghoo Cho, and Soumen Chakrabarti. 2005. Shuffing a stacked deck: the case for partially randomized ranking of search engine results. In VLDB conferenc. 781--792.
22. Pietro Della Briotta Parolo, Raj Kumar Pan, Rumi Ghosh, Bernardo A. Huberman, Kimmo Kaski, and Santo Fortunato. 2015. Attention decay in science. Journal of Informetrics 9, 4 (2015), 734--745. DOI: http://dx.doi.org/10.1016/j.joi.2015.07.006
23. David M Pennock, Gary W Flake, Steve Lawrence, Eric J Glover, and C Lee Giles. 2002. Winners don't take all: Characterizing the competition for links on the web. PNAS 99, 8 (2002), 5207--5211.
24. Joseph Polchinski, Shyamoli Chaudhuri, and Clifford V Johnson. 1996. Notes on D-branes. arXiv preprint hep-th/9602052 (1996).
25. Derek De Solla Price. 1976. A general theory of bibliometric and other cumulative advantage processes. Journal of the American Society for Information Science 27, 5 (1976), 292--306. DOI: http://dx.doi.org/10.1002/asi.4630270505
26. A Vazquez. 2001. Disordered networks generated by recursive searches. Euro- physics Letters 54, 4 (2001), 430--435.
27. Alex Verstak, Anurag Acharya, Helder Suzuki, Sean Henderson, Mikhail Iakhiaev, Cliff Chiung-Yu Lin, and Namit Shetty. 2014. On the Shoulders of Giants: The Growing Impact of Older Articles. CoRR abs/1411.0275 (2014). http://arxiv.org/ abs/1411.0275
28. Dashun Wang, Chaoming Song, and Albert-László Barabási. 2013. Quantifying long-term scientific impact. Science 342, 6154 (2013), 127--132.
29. Mingyang Wang, Guang Yu, and Daren Yu. 2009. Effect of the age of papers on the preferential attachment in citation networks. Physica A: Statistical Mechanics and its Applications 388, 19 (2009), 4273--4276. DOI: http://dx.doi.org/10.1016/j. physa.2009.05.008
30. Michaël Charles Waumans and Hugues Bersini. 2016. Genealogical trees of scientific papers. PloS one 11, 3 (2016), e0150588.
31. Han Zhu, Xinran Wang, and Jian-Yang Zhu. 2003. Effect of aging on network structure. Physical Review E 68, 5 (2003), 056121.

Index Terms

• Computing methodologies

  • Modeling and simulation

    • Model development and analysis

      • Modeling methodologies