The aim of this workshop called Large-Scale Time Dependent Graphs (TD-LSG) is to bring together active scholars and practitioners of dynamic graphs. Graph models and algorithms are ubiquitous of a large number of application domains, ranging from transportation to social networks, semantic web, or data mining. However, many applications require graph models that are time dependent. For example, applications related to urban mobility analysis employ a graph structure of the underlying road network. Indeed, the nature of such networks are spatiotemporal. Therefore, the time a moving object takes to cross a path segment typically depends on the starting instant of time. So, we call time-dependent graphs, the graphs that have this spatiotemporal feature.
The aim of this workshop called Large-Scale Time Dependent Graphs (TD-LSG) is to bring together active scholars and practitioners of dynamic graphs. Graph models and algorithms are ubiquitous of a large number of application domains, ranging from transportation to social networks, semantic web, or data mining. However, many applications require graph models that are time dependent. For example, applications related to urban mobility analysis employ a graph structure of the underlying road network. Indeed, the nature of such networks are spatiotemporal. Therefore, the time a moving object takes to cross a path segment typically depends on the starting instant of time. So, we call time-dependent graphs, the graphs that have this spatiotemporal feature.
In this workshop, we aim to discuss the problem of mining large-scale time-dependent graphs, since there are many real world applications deal with a large volumes of spatio-temporal data (e.g. moving objects’ trajectories). Managing and analysing large-scale time-dependent graphs is very challenging since this requires sophisticated methods and techniques for creating, storing, accessing and processing such graphs in a distributed environment, because centralized approaches do not scale in a Big Data scenario. Contributions will clearly point out answers to one of these challenges focusing on large-scale graphs.
Topics of interest lie at important new insights and experiences on knowledge discovery aspects with dynamic and evolving graphs. Topics of interest of LD_TDG include, but are not limited to, the following inter-linked topics, with regards to mining process: • • • • • • • • • •
Theoretical foundation of TD-LSG Construction and maintenance of TD-LSG Data quality in TD-LSG Data integration in TD-LSG Indexing techniques for TD-LSG Distributed algorithms & navigational query processing TD-LSG data mining: frequent pattern mining, similarity, cluster analysis, predictive learning Trajectory mining in TD-LSG Probabilistic TD-LSG Applications related to TD-LSG
This year, the papers submitted to the workshop were carefully peer reviewed by at least three members of the program committee and the 6 submissions were selected. We would like to thank all the PC members and the reviewers for their reviews, as well as all the authors for their contributions. The TD-LSG workshop and the DyNo workshop were held as a join workshop (Joint Workshop on Large-Scale Evolving Networks and Graphs) in a one day format. TD-LSG workshop and two keynote speakers and six oral presentations.
The first keynote speaker was Nicolas Kourtellis, a researcher in the Telefonica I+D research team, Barcelona. His talk was entitled : « Dealing with betweenness in evolving graphs and imposed system workload imbalance ». During his talk, he introduced the problems of efficiency and scalability to handle million-node graphs are exacerbated in a dynamic setting, where the input is an evolving graph seen edge by edge, and the goal is to keep the graph measure under computation up to date. He also presented a framework that applies parallelized execution of properly defined subtasks on parallel and streaming platforms for computing betweenness centrality on evolving graphs while generating scores on pseudo-real time. The last part of his talk, he highlights efforts to address system workload imbalance arising when computing such highly skewed graph metrics, which impose uneven load to the computation nodes of the streaming platform.
The second keynote speaker was Jan Ramon, a senior researcher in the MAGNET (Machine learniNG in large-scale information NETworks) group at INRIA-Lille, France. His talk was entitled : « Learning from hidden time-dependent graphs ». During his talk, he first motivates the problem of learning from hidden time-dependent graphs with examples, to get at a classification of common settings in terms of observability, objective, type of timedependentness, etc. Next, he sketches approaches for a number of interesting cases where the interaction with the data has a common structure and one can make reasonable assumptions about the underlying process. He concluded his talk with a set of open questions.
The six accepted papers were presented during the workshop.
• •
Dealing with betweenness in evolving graphs and imposed system workload imbalance (keynote talk) 1 Nicolas Kourtellis Finding simple temporal cycles in an interaction network 2-5 Rohit Kumar, Toon Calders
Learning from hidden time-dependent graphs (keynote talk) 6 Jan Ramon Link++: Adaptive Linking of Multiple Transportation Networks 7-20 Ali Masri, Karine Zeitouni, Zoubida Kedad Finding the Nearest Service Provider on Time-Dependent Road Networks 21-31 Lívia Almada Cruz, Francesco Lettich, Leopoldo Soares Júnior, Regis Pires Magalhães and José Antônio Fernandes de Macedo Design and implementation issues of a time-dependent shortest path algorithm for multimodal transportation network 32-43 Abdelfattah Idri, Mariyem Oukarfi, Azedine Boulmakoul, Karine Zeitouni Synthetic Graph Generation from Finely-Tuned Temporal Constraints 44-47 Karim Alami, Radu Ciucanu, Engelbert Mephu Nguifo A Distributed Framework for Large-Scale Time-Dependent Graph Analysis 48-53 Wissem Inoubli, Lívia Almada, Ticiana Linhares Coelho da Silva, Gustavo Coutinho, Lucas Peres, Regis Pires Magalhães, José Antônio Fernandes de Macedo, Sabeur Aridhi, Engelbert Mephu Nguifo • • • • • •
Sabeur Karine Vincent Quentin Davide Wajdi Radu Engelbert Talel
Aridhi
sabeur.aridhi@loria.fr Zeitouni Oria Bramas Mottin Dhifli Ciucanu Mephu Nguifo Abdessalem
Karine.Zeitouni@prism.uvsq.fr
University of Lorraine, LORIA, Campus Scientifique, BP 239, 54506 Vandoeuvre-lès-Nancy, France University of VersaillesSaint-Quentin NJIT Sorbonne Universités, UPMC Univ Paris 06, UMR 7606, F-75005, Paris, France Hasso-Plattner-Institut an der Universität Potsdam University of Evry Université Clermont Auvergne LIMOS - University Clermont Auvergne - CNRS Télécom ParisTech Jose Wagner Raja Chiara Jan Alice Yannis Alberto Macedo Meira Jr.
Chiky Renso Ramon Marascu Velegrakis Montresor Federal University of Ceara University of Versailles National Laboratory of Scientific Computation Federal University of Ceara UFMG ISEP ISTI-CNR, Pisa, Italy INRIA IBM Research - Ireland University of Trento University of Trento