Mining Temporal Networks
Pages 1260 - 1263
Abstract
In 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 temporal information, e.g., interactions in social networks occur at specific moments in time and last for a certain period. Temporal networks, i.e., network data modeling temporal information, enable novel and fundamental discoveries about the underlying systems they model, otherwise not captured by static networks that ignore such temporal information.
In this tutorial, we present state-of-the-art models and algorithmic techniques for mining temporal networks that can provide precious insights into a plethora of web-related applications. We present how temporal networks can be used to extract novel information, especially in web-related network data, and highlight the challenges that arise when modeling temporal information compared to traditional static network-based approaches. We first overview different temporal network models. We then show how such powerful models can be leveraged to extract novel insights through suitable mining primitives. In particular, we present recent advances addressing most foundational problems for temporal network mining---ranging from the computation of temporal centrality measures, temporal motif counting, and temporal communities to bursty events and anomaly detection.
Supplemental Material
MP4 File
Presentation video - Tutorial
- Download
- 6469.47 MB
MP4 File
Supplemental video
- Download
- 6.93 MB
References
[1]
Charu Aggarwal and Karthik Subbian. 2014. Evolutionary network analysis: A survey. ACM Computing Surveys (CSUR), Vol. 47, 1 (2014), 10.
[2]
Charu C Aggarwal and Haixun Wang. 2010. Graph data management and mining: A survey of algorithms and applications. In Managing and mining graph data. Springer, 13--68.
[3]
Leman Akoglu, Hanghang Tong, and Danai Koutra. 2015. Graph based anomaly detection and description: a survey. Data mining and knowledge discovery, Vol. 29, 3 (2015), 626--688.
[4]
Albert-László Barabási et al. 2016. Network science. Cambridge university press.
[5]
Caleb Belth, Xinyi Zheng, and Danai Koutra. 2020. Mining Persistent Activity in Continually Evolving Networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM.
[6]
Austin R. Benson, Rediet Abebe, Michael T. Schaub, Ali Jadbabaie, and Jon Kleinberg. 2018. Simplicial closure and higher-order link prediction. Proceedings of the National Academy of Sciences, Vol. 115, 48 (2018).
[7]
Michele Berlingerio, Francesco Bonchi, Björn Bringmann, and Aristides Gionis. 2009. Mining graph evolution rules. In ECML PKDD. Springer, 115--130.
[8]
Sandeep Bhadra and Afonso Ferreira. 2003. Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks. In Ad-Hoc, Mobile, and Wireless Networks: ADHOC-NOW2003. Springer, 259--270.
[9]
Sebastian Buß, Hendrik Molter, Rolf Niedermeier, and Maciej Rymar. 2020. Algorithmic Aspects of Temporal Betweenness. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM.
[10]
Arnaud Casteigts, Timothée Corsini, and Writika Sarkar. 2022. Simple, strict, proper, happy: A study of reachability in temporal graphs. In International Symposium on Stabilizing, Safety, and Security of Distributed Systems. Springer, 3--18.
[11]
Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. 2012. Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems, Vol. 27, 5 (2012), 387--408.
[12]
Mário Cordeiro and Jo ao Gama. 2016. Online social networks event detection: a survey. In Solving Large Scale Learning Tasks. Challenges and Algorithms. Springer, 1--41.
[13]
Isnard Lopes Costa, Raul Lopes, Andrea Marino, and Ana Silva. 2023. On Computing Large Temporal (Unilateral) Connected Components. In IWOCA. Springer, 282--293.
[14]
Yugchhaya Dhote, Nishchol Mishra, and Sanjeev Sharma. 2013. Survey and analysis of temporal link prediction in online social networks. In 2013 International Conference on Advances in Computing, Communications and Informatics. IEEE, 1178--1183.
[15]
A. Feldmann, A. Greenberg, C. Lund, N. Reingold, and J. Rexford. 2000. NetScope: traffic engineering for IP networks. IEEE Network, Vol. 14, 2 (2000), 11--19.
[16]
Edoardo Galimberti, Martino Ciaperoni, Alain Barrat, Francesco Bonchi, Ciro Cattuto, and Francesco Gullo. 2020. Span-core decomposition for temporal networks: Algorithms and applications. TKDD, Vol. 15, 1 (2020), 1--44.
[17]
Zhongqiang Gao, Chuanqi Cheng, Yanwei Yu, Lei Cao, Chao Huang, and Junyu Dong. 2022. Scalable Motif Counting for Large-scale Temporal Graphs. In 2022 IEEE 38th International Conference on Data Engineering (ICDE). IEEE.
[18]
Laetitia Gauvin, Mathieu Gé nois, Má rton Karsai, Mikko Kivelä, Taro Takaguchi, Eugenio Valdano, and Christian L. Vestergaard. 2022. Randomized Reference Models for Temporal Networks. SIAM Rev., Vol. 64, 4 (2022), 763--830.
[19]
K-I Goh and A-L Barabási. 2008. Burstiness and memory in complex systems. Europhysics Letters, Vol. 81, 4 (2008), 48002.
[20]
Anuradha Goswami and Ajey Kumar. 2016. A survey of event detection techniques in online social networks. Social Network Analysis and Mining, Vol. 6, 1 (2016), 107.
[21]
Scott A Hill and Dan Braha. 2010. Dynamic model of time-dependent complex networks. Physical Review E, Vol. 82, 4 (2010), 046105.
[22]
Petter Holme. 2013. Epidemiologically optimal static networks from temporal network data. PLoS computational biology, Vol. 9, 7 (2013), e1003142.
[23]
Petter Holme. 2015. Modern temporal network theory: a colloquium. The European Physical Journal B, Vol. 88, 9 (2015), 234.
[24]
Petter Holme and Jari Saram"aki. 2012. Temporal networks. Physics reports, Vol. 519, 3 (2012), 97--125.
[25]
Hsun-Ping Hsieh and Cheng-Te Li. 2010. Mining temporal subgraph patterns in heterogeneous information networks. In 2010 IEEE Second International Conference on Social Computing. IEEE, 282--287.
[26]
Angelo Impedovo, Corrado Loglisci, and Michelangelo Ceci. 2017. Temporal Pattern Mining from Evolving Networks. arXiv preprint arXiv:1709.06772 (2017).
[27]
Ali Jazayeri and Christopher C Yang. 2020. Motif discovery algorithms in static and temporal networks: A survey. Journal of Complex Networks, Vol. 8, 4 (2020).
[28]
Hang-Hyun Jo, Raj Kumar Pan, and Kimmo Kaski. 2011. Emergence of bursts and communities in evolving weighted networks. PloS one, Vol. 6, 8 (2011), e22687.
[29]
Lauri Kovanen, Márton Karsai, Kimmo Kaski, János Kertész, and Jari Saramäki. 2011. Temporal motifs in time-dependent networks. J. Stat. Mech. (2011) P11005 (2011).
[30]
Rohit Kumar, Toon Calders, Aristides Gionis, and Nikolaj Tatti. 2015. Maintaining sliding-window neighborhood profiles in interaction networks. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases. 719--735.
[31]
Ravi Kumar, Jasmine Novak, and Andrew Tomkins. 2010. Structure and evolution of online social networks. In Link mining: models, algorithms, and applications. Springer, 337--357.
[32]
Srijan Kumar, Xikun Zhang, and Jure Leskovec. 2019. Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM.
[33]
Matthieu Latapy, Tiphaine Viard, and Clémence Magnien. 2018. Stream graphs and link streams for the modeling of interactions over time. Social Network Analysis and Mining, Vol. 8, 1 (2018), 61.
[34]
Geon Lee and Kijung Shin. 2021. Thyme: Temporal hypergraph motifs and fast algorithms for exact counting. In 2021 IEEE International Conference on Data Mining (ICDM). IEEE, 310--319.
[35]
Sungmin Lee, Luis EC Rocha, Fredrik Liljeros, and Petter Holme. 2012. Exploiting temporal network structures of human interaction to effectively immunize populations. PloS one, Vol. 7, 5 (2012).
[36]
Rong-Hua Li, Jiao Su, Lu Qin, Jeffrey Xu Yu, and Qiangqiang Dai. 2018. Persistent Community Search in Temporal Networks. In 2018 IEEE 34th International Conference on Data Engineering (ICDE). IEEE.
[37]
Longlong Lin, Pingpeng Yuan, Rong-Hua Li, Jifei Wang, Ling Liu, and Hai Jin. 2022. Mining Stable Quasi-Cliques on Temporal Networks. IEEE Transactions on Systems, Man, and Cybernetics: Systems, Vol. 52, 6 (2022), 3731--3745.
[38]
Paul Liu, Austin R. Benson, and Moses Charikar. 2019. Sampling Methods for Counting Temporal Motifs. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining. ACM.
[39]
Penghang Liu, Valerio Guarrasi, and A. Erdem Sariyuce. 2021. Temporal Network Motifs: Models, Limitations, Evaluation. IEEE Transactions on Knowledge and Data Engineering (2021), 1--1.
[40]
Penghang Liu and Ahmet Erdem Sariyüce. 2023. Using Motif Transitions for Temporal Graph Generation. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. ACM.
[41]
Yike Liu, Tara Safavi, Abhilash Dighe, and Danai Koutra. 2018. Graph summarization methods and applications: A survey. ACM Computing Surveys (CSUR), Vol. 51, 3 (2018), 62.
[42]
Antonio Longa, Giulia Cencetti, Bruno Lepri, and Andrea Passerini. 2021. An efficient procedure for mining egocentric temporal motifs. Data Mining and Knowledge Discovery, Vol. 36, 1 (2021), 355--378.
[43]
Andrew McGregor. 2014. Graph stream algorithms: a survey. ACM SIGMOD Record, Vol. 43, 1 (2014), 9--20.
[44]
Othon Michail. 2016. An introduction to temporal graphs: An algorithmic perspective. Internet Mathematics, Vol. 12, 4 (2016), 239--280.
[45]
Katarzyna Musiał and Przemysław Kazienko. 2012. Social networks on the Internet. World Wide Web, Vol. 16, 1 (2012), 31--72.
[46]
Petra Mutzel and Lutz Oettershagen. 2019. On the enumeration of bicriteria temporal paths. In Theory and Applications of Models of Computation, TAMC. Springer, 518--535.
[47]
Mohammad Hossein Namaki, Yinghui Wu, Qi Song, Peng Lin, and Tingjian Ge. 2017. Discovering Graph Temporal Association Rules. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. ACM.
[48]
Mark Newman. 2018. Networks. Oxford University Press.
[49]
Arif Nurwidyantoro and Edi Winarko. 2013. Event detection in social media: A survey. In International Conference on ICT for Smart Society. IEEE, 1--5.
[50]
Lutz Oettershagen. 2022. Temporal Graph Algorithms. Ph.,D. Dissertation. Universit"ats-und Landesbibliothek Bonn.
[51]
Lutz Oettershagen, Athanasios L Konstantinidis, and Giuseppe F Italiano. 2022a. Inferring Tie Strength in Temporal Networks. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, 69--85.
[52]
Lutz Oettershagen, Nils M Kriege, Christopher Morris, and Petra Mutzel. 2020. Classifying dissemination processes in temporal graphs. Big Data, Vol. 8, 5 (2020), 363--378.
[53]
Lutz Oettershagen, Nils M. Kriege, and Petra Mutzel. 2023. A Higher-Order Temporal H-Index for Evolving Networks. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (Long Beach, CA, USA) (KDD '23). Association for Computing Machinery, New York, NY, USA, 1770--1782.
[54]
Lutz Oettershagen and Petra Mutzel. 2022a. Computing top-k temporal closeness in temporal networks. Knowledge and Information Systems (2022), 1--29.
[55]
Lutz Oettershagen and Petra Mutzel. 2022b. Tglib: an open-source library for temporal graph analysis. In 2022 IEEE International Conference on Data Mining Workshops (ICDMW). IEEE, 1240--1245.
[56]
Lutz Oettershagen and Petra Mutzel. 2023. An Index For Temporal Closeness Computation in Evolving Graphs. In Proceedings of the 2023 SIAM International Conference on Data Mining (SDM). SIAM, 280--288.
[57]
Lutz Oettershagen, Petra Mutzel, and Nils M Kriege. 2022b. Temporal walk centrality: ranking nodes in evolving networks. In Proceedings of the ACM Web Conference 2022. 1640--1650.
[58]
Noujan Pashanasangi and C. Seshadhri. 2021. Faster and Generalized Temporal Triangle Counting, via Degeneracy Ordering. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. ACM.
[59]
Alexandra Porter, Baharan Mirzasoleiman, and Jure Leskovec. 2022. Analytical Models for Motifs in Temporal Networks. In Companion Proceedings of the Web Conference 2022. ACM.
[60]
Hongchao Qin, Rong-Hua Li, Ye Yuan, Yongheng Dai, and Guoren Wang. 2023. Densest Periodic Subgraph Mining on Large Temporal Graphs. IEEE Transactions on Knowledge and Data Engineering (2023), 1--14.
[61]
Hongchao Qin, Rong-Hua Li, Ye Yuan, Guoren Wang, Lu Qin, and Zhiwei Zhang. 2022. Mining Bursting Core in Large Temporal Graphs. Proceedings of the VLDB Endowment, Vol. 15, 13 (2022), 3911--3923.
[62]
Manuel Gomez Rodriguez and Bernhard Schölkopf. 2012. Influence maximization in continuous time diffusion networks. arXiv preprint arXiv:1205.1682 (2012).
[63]
Giulio Rossetti and Rémy Cazabet. 2018. Community discovery in dynamic networks: a survey. ACM Computing Surveys (CSUR), Vol. 51, 2 (2018), 35.
[64]
Polina Rozenshtein, Aris Anagnostopoulos, Aristides Gionis, and Nikolaj Tatti. 2014. Event detection in activity networks. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 1176--1185.
[65]
Polina Rozenshtein, Francesco Bonchi, Aristides Gionis, Mauro Sozio, and Nikolaj Tatti. 2019. Finding events in temporal networks: segmentation meets densest subgraph discovery. Knowledge and Information Systems, Vol. 62, 4 (Oct. 2019), 1611--1639.
[66]
Polina Rozenshtein and Aristides Gionis. 2019. Mining Temporal Networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM.
[67]
Polina Rozenshtein, Aristides Gionis, B Aditya Prakash, and Jilles Vreeken. 2016. Reconstructing an epidemic over time. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 1835--1844.
[68]
Polina Rozenshtein, Nikolaj Tatti, and Aristides Gionis. 2017a. Finding dynamic dense subgraphs. ACM Transactions on Knowledge Discovery from Data (TKDD), Vol. 11, 3 (2017), 27.
[69]
Polina Rozenshtein, Nikolaj Tatti, and Aristides Gionis. 2017b. The network-untangling problem: From interactions to activity timelines. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, 701--716.
[70]
Diego Santoro and Ilie Sarpe. 2022. ONBRA: Rigorous Estimation of the Temporal Betweenness Centrality in Temporal Networks. In Proceedings of the ACM Web Conference 2022. ACM.
[71]
Ilie Sarpe and Fabio Vandin. 2021a. OdeN: Simultaneous Approximation of Multiple Motif Counts in Large Temporal Networks. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management. ACM.
[72]
Ilie Sarpe and Fabio Vandin. 2021b. PRESTO: Simple and Scalable Sampling Techniques for the Rigorous Approximation of Temporal Motif Counts. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM). Society for Industrial and Applied Mathematics, 145--153.
[73]
Xiaoli Sun, Yusong Tan, Qingbo Wu, Baozi Chen, and Changxiang Shen. 2019. ™-Miner: TFS-Based Algorithm for Mining Temporal Motifs in Large Temporal Network. IEEE Access, Vol. 7 (2019), 49778--49789.
[74]
John Tang, Mirco Musolesi, Cecilia Mascolo, and Vito Latora. 2009. Temporal distance metrics for social network analysis. In Proceedings of the 2nd ACM workshop on Online social networks. 31--36.
[75]
John Tang, Salvatore Scellato, Mirco Musolesi, Cecilia Mascolo, and Vito Latora. 2010. Small-world behavior in time-varying graphs. Physical Review E, Vol. 81, 5 (2010), 055101.
[76]
Bianca Wackersreuther, Peter Wackersreuther, Annahita Oswald, Christian Böhm, and Karsten M Borgwardt. 2010. Frequent subgraph discovery in dynamic networks. In Proceedings of the Eighth Workshop on Mining and Learning with Graphs. ACM, 155--162.
[77]
Senzhang Wang, Jiannong Cao, and Philip S. Yu. 2022. Deep Learning for Spatio-Temporal Data Mining: A Survey. IEEE Transactions on Knowledge and Data Engineering, Vol. 34, 8 (2022), 3681--3700.
[78]
Huanhuan Wu, James Cheng, Yi Lu, Yiping Ke, Yuzhen Huang, Da Yan, and Hejun Wu. 2015. Core decomposition in large temporal graphs. In Big Data. IEEE, 649--658.
[79]
Jiajing Wu, Jieli Liu, Weili Chen, Huawei Huang, Zibin Zheng, and Yan Zhang. 2022. Detecting Mixing Services via Mining Bitcoin Transaction Network With Hybrid Motifs. IEEE Transactions on Systems, Man, and Cybernetics: Systems, Vol. 52, 4 (apr 2022), 2237--2249.
[80]
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. 2021. A Comprehensive Survey on Graph Neural Networks. IEEE Transactions on Neural Networks and Learning Systems, Vol. 32, 1 (2021), 4--24.
[81]
Han Xiao, Polina Rozenshtein, and Aristides Gionis. 2016. Discovering topically-and temporally-coherent events in interaction networks. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, 690--705.
[82]
Han Xiao, Polina Rozenshtein, Nikolaj Tatti, and Aristides Gionis. 2018. Reconstructing a cascade from temporal observations. In Proceedings of the 2018 SIAM International Conference on Data Mining. SIAM, 666--674.
[83]
Qiankun Zhao, Yuan Tian, Qi He, Nuria Oliver, Ruoming Jin, and Wang-Chien Lee. 2010. Communication motifs. In Proceedings of the 19th ACM international conference on Information and knowledge management - CIKM textquotesingle10. ACM Press.
[84]
Linhong Zhu, Dong Guo, Junming Yin, Greg Ver Steeg, and Aram Galstyan. 2016. Scalable temporal latent space inference for link prediction in dynamic social networks. IEEE Transactions on Knowledge and Data Engineering, Vol. 28, 10 (2016), 2765--2777.
Index Terms
- Mining Temporal Networks
Recommendations
Mining Temporal Networks
KDD '19: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data MiningNetworks (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 ...
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 ...
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
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
May 2024
1928 pages
ISBN:9798400701726
DOI:10.1145/3589335
- General Chairs:
- Tat-Seng Chua,
- Chong-Wah Ngo,
- Program Chairs:
- Ravi Kumar,
- Hady W. Lauw,
- Roy Ka-Wei Lee
Copyright © 2024 Owner/Author.
This work is licensed under a Creative Commons Attribution International 4.0 License.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 13 May 2024
Check for updates
Author Tags
Qualifiers
- Tutorial
Funding Sources
- Wallenberg AI, Autonomous Systems and Software Program
- ERC Advanced Grant REBOUND
- EC H2020 RIA project SoBigData++
Conference
WWW '24
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,899 of 8,196 submissions, 23%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 231Total Downloads
- Downloads (Last 12 months)231
- Downloads (Last 6 weeks)45
Reflects downloads up to 30 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in