Polina Rozenshtein
Aristides Gionis
ABSTRACT
Networks (or graphs) are used to represent and analyze large datasets of objects and their relations. Naturally, real-world networks have a temporal component: for instance, interactions between objects have a timestamp and a duration. In this tutorial we present models and algorithms for mining temporal networks, i.e., network data with temporal information. We overview different models used to represent temporal networks. We highlight the main differences between static and temporal networks, and discuss the challenges arising from introducing the temporal dimension in the network representation. We present recent papers addressing the most well-studied problems in the setting of temporal networks, including computation of centrality measures, motif detection and counting, community detection and monitoring, event and anomaly detection, analysis of epidemic processes and influence spreading, network summarization, and structure prediction.
Supplemental Material
- C. Aggarwal and K. Subbian. Evolutionary network analysis: A survey. ACM Computing Surveys (CSUR), 47 (1): 10, 2014. Google Scholar
Digital Library
- C. C. Aggarwal and H. Wang. Graph data management and mining: A survey of algorithms and applications. In Managing and mining graph data, pages 13--68. Springer, 2010.Google ScholarCross Ref
- L. Akoglu, H. Tong, and D. Koutra. Graph based anomaly detection and description: a survey. Data mining and knowledge discovery, 29 (3): 626--688, 2015. Google ScholarDigital Library
- et al.(2016)}barabasi2016networkA.-L. Barabási et al. Network science. Cambridge university press, 2016.Google Scholar
- M. Berlingerio, F. Bonchi, B. Bringmann, and A. Gionis. Mining graph evolution rules. In ECML PKDD, pages 115--130. Springer, 2009.Google ScholarCross Ref
- A. Casteigts, P. Flocchini, W. Quattrociocchi, and N. Santoro. Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems, 27 (5): 387--408, 2012. Google ScholarDigital Library
- M. Cordeiro and J. Gama. Online social networks event detection: a survey. In Solving Large Scale Learning Tasks. Challenges and Algorithms, pages 1--41. Springer, 2016.Google ScholarCross Ref
- Y. Dhote, N. Mishra, and S. Sharma. Survey and analysis of temporal link prediction in online social networks. In 2013 International Conference on Advances in Computing, Communications and Informatics, pages 1178--1183. IEEE, 2013.Google ScholarCross Ref
- A. Goswami and A. Kumar. A survey of event detection techniques in online social networks. Social Network Analysis and Mining, 6 (1): 107, 2016.Google ScholarCross Ref
- S. A. Hill and D. Braha. Dynamic model of time-dependent complex networks. Physical Review E, 82 (4): 046105, 2010.Google ScholarCross Ref
- P. Holme. Epidemiologically optimal static networks from temporal network data. PLoS computational biology, 9 (7): e1003142, 2013.Google Scholar
- P. Holme. Modern temporal network theory: a colloquium. The European Physical Journal B, 88 (9): 234, 2015.Google ScholarCross Ref
- (2012)}holme2012temporalP. Holme and J. Saram"aki. Temporal networks. Physics reports, 519 (3): 97--125, 2012.Google Scholar
- H.-P. Hsieh and C.-T. Li. Mining temporal subgraph patterns in heterogeneous information networks. In 2010 IEEE Second International Conference on Social Computing, pages 282--287. IEEE, 2010. Google ScholarDigital Library
- A. Impedovo, C. Loglisci, and M. Ceci. Temporal pattern mining from evolving networks. arXiv preprint arXiv:1709.06772, 2017.Google Scholar
- H.-H. Jo, R. K. Pan, and K. Kaski. Emergence of bursts and communities in evolving weighted networks. PloS one, 6 (8): e22687, 2011.Google Scholar
- R. Kumar, J. Novak, and A. Tomkins. Structure and evolution of online social networks. In Link mining: models, algorithms, and applications, pages 337--357. Springer, 2010.Google ScholarCross Ref
- R. Kumar, T. Calders, A. Gionis, and N. Tatti. Maintaining sliding-window neighborhood profiles in interaction networks. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 719--735, 2015.Google ScholarCross Ref
- M. Latapy, T. Viard, and C. Magnien. Stream graphs and link streams for the modeling of interactions over time. Social Network Analysis and Mining, 8 (1): 61, 2018.Google ScholarCross Ref
- S. Lee, L. E. Rocha, F. Liljeros, and P. Holme. Exploiting temporal network structures of human interaction to effectively immunize populations. PloS one, 7 (5), 2012.Google Scholar
- Y. Liu, T. Safavi, A. Dighe, and D. Koutra. Graph summarization methods and applications: A survey. ACM Computing Surveys (CSUR), 51 (3): 62, 2018. Google ScholarDigital Library
- A. McGregor. Graph stream algorithms: a survey. ACM SIGMOD Record, 43 (1): 9--20, 2014. Google ScholarDigital Library
- O. Michail. An introduction to temporal graphs: An algorithmic perspective. Internet Mathematics, 12 (4): 239--280, 2016.Google ScholarCross Ref
- A. Nurwidyantoro and E. Winarko. Event detection in social media: A survey. In International Conference on ICT for Smart Society, pages 1--5. IEEE, 2013.Google ScholarCross Ref
- opf(2012)}rodriguez2012influenceM. G. Rodriguez and B. Schölkopf. Influence maximization in continuous time diffusion networks. arXiv preprint arXiv:1205.1682, 2012.Google Scholar
- G. Rossetti and R. Cazabet. Community discovery in dynamic networks: a survey. ACM Computing Surveys (CSUR), 51 (2): 35, 2018. Google ScholarDigital Library
- P. Rozenshtein. Methods for analyzing temporal networks. PhD thesis, Aalto University, Helsinki, Finland, 2018.Google Scholar
- P. Rozenshtein, A. Anagnostopoulos, A. Gionis, and N. Tatti. Event detection in activity networks. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1176--1185. ACM, 2014. Google ScholarDigital Library
- P. Rozenshtein, A. Gionis, B. A. Prakash, and J. Vreeken. Reconstructing an epidemic over time. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1835--1844. ACM, 2016. Google ScholarDigital Library
- Rozenshtein, Tatti, and Gionis}rozenshtein2017findingP. Rozenshtein, N. Tatti, and A. Gionis. Finding dynamic dense subgraphs. ACM Transactions on Knowledge Discovery from Data (TKDD), 11 (3): 27, 2017 a . Google ScholarDigital Library
- Rozenshtein, Tatti, and Gionis}rozenshtein2017networkP. Rozenshtein, N. Tatti, and A. Gionis. The network-untangling problem: From interactions to activity timelines. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 701--716. Springer, 2017 b .Google ScholarCross Ref
- P. Rozenshtein, F. Bonchi, A. Gionis, M. Sozio, and N. Tatti. Finding events in temporal networks: Segmentation meets densest-subgraph discovery. In 2018 IEEE International Conference on Data Mining (ICDM), pages 397--406. IEEE, 2018.Google ScholarCross Ref
- , and Borgwardt}wackersreuther2010frequentB. Wackersreuther, P. Wackersreuther, A. Oswald, C. Böhm, and K. M. Borgwardt. Frequent subgraph discovery in dynamic networks. In Proceedings of the Eighth Workshop on Mining and Learning with Graphs, pages 155--162. ACM, 2010. Google ScholarDigital Library
- H. Xiao, P. Rozenshtein, and A. Gionis. Discovering topically-and temporally-coherent events in interaction networks. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 690--705. Springer, 2016.Google ScholarCross Ref
- H. Xiao, P. Rozenshtein, N. Tatti, and A. Gionis. Reconstructing a cascade from temporal observations. In Proceedings of the 2018 SIAM International Conference on Data Mining, pages 666--674. SIAM, 2018.Google ScholarCross Ref
- L. Zhu, D. Guo, J. Yin, G. Ver Steeg, and A. Galstyan. Scalable temporal latent space inference for link prediction in dynamic social networks. IEEE Transactions on Knowledge and Data Engineering, 28 (10): 2765--2777, 2016. Google ScholarDigital Library
Index Terms
- Mining Temporal Networks
Recommendations
Motifs in Temporal Networks
WSDM '17: Proceedings of the Tenth ACM International Conference on Web Search and Data MiningNetworks are a fundamental tool for modeling complex systems in a variety of domains including social and communication networks as well as biology and neuroscience. The counts of small subgraph patterns in networks, called network motifs, are crucial ...
Mining Temporal Networks
WWW '24: Companion Proceedings of the ACM on Web Conference 2024In World Wide Web (WWW) systems, networks (or graphs) serve as a fundamental tool for representing, analyzing, and understanding linked data, providing significant insights into the underlying systems. Naturally, most real-world systems have inherent ...
ONBRA: Rigorous Estimation of the Temporal Betweenness Centrality in Temporal Networks
WWW '22: Proceedings of the ACM Web Conference 2022In network analysis, the betweenness centrality of a node informally captures the fraction of shortest paths visiting that node. The computation of the betweenness centrality measure is a fundamental task in the analysis of modern networks, enabling the ...
Comments