1st International Workshop on Large-Scale Time Dependent Graphs (TD-LSG’17) in conjunction with the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD 2017) Skopje, Macedonia, September 18, 2017 Editors Sabeur Aridhi LORIA/INRIA Nancy Grand Est, University of Lorraine (France) https://members.loria.fr/SAridhi/ José Fernandes de Universidade Federale do Ceara, Fortaleza (Brazil) Macedo http://www.lia.ufc.br/~jose.macedo Engelbert Mephu Nguifo LIMOS, Blaise Pascal University (France) http://www.isima.fr/mephu Karine Zeitouni DAVID, Université de Versailles Saint-Quentin (France) http://perso.prism.uvsq.fr/users/zeitouni 1 Preface 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. Aims and Scope 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. Workshop topics 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 2 Workshop contributions 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. Keynote speakers 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 time- dependentness, 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. Oral presentations The six accepted papers were presented during the workshop. Workshop program Session 1: Evolving (Social) Graphs • 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 3 Session 2: Transportation networks • 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 Session 3: Performance issues of large-scale evolving graphs • 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 Program Committee First Last name Email Organization name Sabeur Aridhi sabeur.aridhi@loria.fr University of Lorraine, LORIA, Campus Scientifique, BP 239, 54506 Vandoeuvre-lès-Nancy, France Karine Zeitouni Karine.Zeitouni@prism.uvsq.fr University of Versailles- Saint-Quentin Vincent Oria oria@njit.edu NJIT Quentin Bramas quentin.bramas@gmail.com Sorbonne Universités, UPMC Univ Paris 06, UMR 7606, F-75005, Paris, France Davide Mottin davide.mottin@hpi.de Hasso-Plattner-Institut an der Universität Potsdam Wajdi Dhifli wajdi.dhifli@univ-evry.fr University of Evry Radu Ciucanu radu.ciucanu@uca.fr Université Clermont Auvergne Engelbert Mephu engelbert.mephu_nguifo@uca.fr LIMOS - University Nguifo Clermont Auvergne - CNRS Talel Abdessalem Talel.Abdessalem@telecom- Télécom ParisTech paristech.fr 4 Ticiana Coelho Da ticianalc@ufc.br Federal University of Ceara L. Silva Zoubida Kedad zoubida.kedad@prism.uvsq.fr University of Versailles Fabio Porto fporto@lncc.br National Laboratory of Scientific Computation Jose Macedo jose.macedo@lia.ufc.br Federal University of Ceara Wagner Meira Jr. meira@dcc.ufmg.br UFMG Raja Chiky raja.chiky@isep.fr ISEP Chiara Renso chiara.renso@isti.cnr.it ISTI-CNR, Pisa, Italy Jan Ramon Jan.Ramon@inria.fr INRIA Alice Marascu alice.marascu@ie.ibm.com IBM Research - Ireland Yannis Velegrakis velgias@disi.unitn.eu University of Trento Alberto Montresor alberto.montresor@unitn.it University of Trento The Workshop chairs Sabeur Aridhi José Fernandes de Macedo Engelbert Mephu Nguifo Karine Zeitouni 5