Tracking online topics over time: understanding dynamic hashtag communities
Tóm tắt
Hashtags are widely used for communication in online media. As a condensed version of information, they characterize topics and discussions. For their analysis, we apply methods from network science and propose novel tools for tracing their dynamics in time-dependent data. The observations are characterized by bursty behaviors in the increases and decreases of hashtag usage. These features can be reproduced with a novel model of dynamic rankings. We build temporal and weighted co-occurrence networks from hashtags. On static snapshots, we infer the community structure using customized methods. On temporal networks, we solve the bipartite matching problem of detected communities at subsequent timesteps by taking into account higher-order memory. This results in a matching protocol that is robust toward temporal fluctuations and instabilities of the static community detection. The proposed methodology is broadly applicable and its outcomes reveal the temporal behavior of online topics. We consider the size of the communities in time as a proxy for online popularity dynamics. We find that the distributions of gains and losses, as well as the interevent times are fat-tailed indicating occasional, but large and sudden changes in the usage of hashtags. Inspired by typical website designs, we propose a stochastic model that incorporates a ranking with respect to a time-dependent prestige score. This causes occasional cascades of rank shift events and reproduces the observations with good agreement. This offers an explanation for the observed dynamics, based on characteristic elements of online media.
Tài liệu tham khảo
Fortunato S. Community detection in graphs. Phys Rep. 2010;486(3—-5):75–174.
Ahn Y-Y, Bagrow JP, Lehmann S. Link communities reveal multiscale complexity in networks. Nature. 2010;466(7307):761–4.
Palla G, Derenyi I, Farkas I, Vicsek T. Uncovering the overlapping community structure of complex networks in nature and society. Nature. 2005;435(7043):814–8.
Peixoto TP. Hierarchical block structures and high-resolution model selection in large networks. Phys Rev X. 2014;4:011047.
Palla G, Barabasi A-L, Vicsek T. Quantifying social group evolution. Nature. 2007;446:664.
Cazabet R, Amblard F, Hanachi C. Detection of overlapping communities in dynamical social networks. In: 2010 IEEE second international conference on social computing. 2010. p. 309–14.
Sekara V, Stopczynski A, Lehmann S. Fundamental structures of dynamic social networks. Proc Natl Acad Sci USA. 2016;113(36):9977–82.
Hopcroft J, Khan O, Kulis B, Selman B. Tracking evolving communities in large linked networks. Proc Natl Acad Sci. 2004;101(suppl 1):5249–53.
Asur S, Parthasarathy S, Ucar D. An event-based framework for characterizing the evolutionary behavior of interaction graphs. ACM Trans Knowl Discov Data (TKDD). 2009;3(4):16.
Greene D, Doyle D, Cunningham P. Tracking the evolution of communities in dynamic social networks. In: 2010 international conference on advances in social networks analysis and mining. 2010. p. 176–83.
Tantipathananandh C, Berger-Wolf T, Kempe D. A framework for community identification in dynamic social networks. In: Proceedings of the 13th ACM SIGKDD international conference on knowledge discovery and data mining. KDD ’07. New York:ACM; 2007. p. 717–26.
Aynaud T, Fleury E, Guillaume J-L, Wang Q. Communities in evolving networks: definitions, detection, and analysis techniques. Dynamics on and of complex networks, vol. 2. Dordrecht: Springer; 2013. p. 159–200.
Rosvall M, Esquivel AV, Lancichinetti A, West JD, Lambiotte R. Memory in network flows and its effects on spreading dynamics and community detection. Nat Commun. 2014;5:4630.
Lorenz P, Wolf F, Braun J, Djurdjevac Conrad N, Hövel P Capturing the dynamics of hashtag-communities. In: Cherifi C, Cherifi H, Karsai M, Musolesi M, editors. Complex networks & their applications VI. Complex networks 2017. Studies in Computational Intelligence, vol 689. Cham: Springer; 2018. p. 401–13.
Barabasi A-L, Albert R. Emergence of scaling in random networks. Science. 1999;286:509.
Leskovec J, Backstrom L, Kleinberg J. Meme-tracking and the dynamics of the news cycle. In: Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining. New York: ACM; 2009. p. 497–506.
Ratkiewicz J, Fortunato S, Flammini A, Menczer F, Vespignani A. Characterizing and modeling the dynamics of online popularity. Phys Rev Lett. 2010;105(15):158701.
Miotto JM, Kantz H, Altmann EG. Stochastic dynamics and the predictability of big hits in online videos. Phys Rev E. 2017;95:032311.
Fortunato S, Flammini A, Menczer F. Scale-free network growth by ranking. Phys Rev Lett. 2006;96(21):218701.
Au Yeung C-M, Gibbins N, Shadbolt N. Contextualising tags in collaborative tagging systems. In: Proceedings of the 20th ACM conference on hypertext and hypermedia. HT ’09. New York: ACM; 2009. p. 251–60.
Cazabet R, Takeda H, Hamasaki M, Amblard F. Using dynamic community detection to identify trends in user-generated content. Soc Netw Anal Min. 2012;2(4):361–71.
Cancho RFI, Solé RV. The small world of human language. Proc R Soc Lond B. 2001;268(1482):2261–5.
Newman MEJ. Modularity and community structure in networks. Proc Natl Acad Sci USA. 2006;103:8577.
Blondel VD, Guillaume J-L, Lambiotte R, Lefebvre E. Fast unfolding of communities in large networks. J Stat Mech. 2008;2008(10):10008.
Ravasz E, Barabasi A. Hierarchical organization in complex networks. Phys Rev E. 2003;67:026112.
Djurdjevac N, Bruckner S, Conrad TO, Schütte C. Random walks on complex modular networks12. JNAIAM. 2011;6(1–2):29–50.
Sarich M, Djurdjevac N, Bruckner S, Conrad TO, Schütte C. Modularity revisited: a novel dynamics-based concept for decomposing complex networks. J Comput Dyn. 2014;1(1):191–212.
Papadopoulos S, Kompatsiaris Y, Vakali A. A graph-based clustering scheme for identifying related tags in folksonomies. In: Proceedings of the 12th international conference on data warehousing and knowledge discovery. DaWaK ’10. Berlin: Springer; 2010. p. 65–76.
Chakraborty A, Ghosh S, Ganguly N. Detecting overlapping communities in folksonomies. In: Proceedings of the 23rd ACM conference on hypertext and social media. HT ’12. New York: ACM; 2012. p. 213–8.
Metzner P, Schütte C, Vanden-Eijnden E. Transition path theory for markov jump processes. Multiscale Model Simul. 2009;7(3):1192–219.
Kuhn HW. The Hungarian method for the assignment problem. Naval Res Logist Q. 1955;2(1–2):83–97.
Rosvall M, Bergstrom CT. Mapping change in large networks. PloS ONE. 2010;5(1):8694.
Borge-Holthoefer J, Rivero A, García I, Cauhé E, Ferrer JC, Francos D, Iniguez D, Pérez MP, Ruiz G. Structural and dynamical patterns on online social networks: the spanish may 15th movement as a case study. PloS ONE. 2011;6(8):23883.
Eom Y, Fortunato S. Characterizing and modeling citation dynamics. PloS ONE. 2011;6(9):24926.
Clauset A, Shalizi CR, Newman MEJ. Power-law distributions in empirical data. SIAM Rev. 2009;51(4):661–703.
Weng L, Flammini A, Vespignani A, Menczer F. Competition among memes in a world with limited attention. Sci Rep. 2012;2:335.
Dorogovtsev SN, Mendes JFF. Evolution of networks with aging of sites. Phys Rev E. 2000;62(2):1842.
Bastian M, Heymann S, Jacomy M. Gephi: an open source software for exploring and manipulating networks. Icwsm. 2009;8:361–2.