logo

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.

Important dates:

  • Abstract Submission Deadline: Monday, July 10, 2017 (extended)
  • Paper Submission Deadline: Monday, July 10, 2017 (extended)
  • Author Notification: Monday, July 24, 2017
  • Camera Ready Deadline: Monday, August 7, 2017

Useful links:

Jan Ramon.
MAGNET team
INRIA Lille Nord Europe, France

Research interests

I'm a senior researcher in the MAGNET (Machine learniNG in large-scale information NETworks) group at INRIA-Lille, France. My research interests include data mining and machine learning on graph-structured data, algorithmic and statistical aspects of graph-structured data, privacy-preserving techniques and applications in biomedical domains and traffic.
Nicolas Kourtellis
Telefonica I+D
Barcelona, Spain

Bio

Dr. Nicolas Kourtellis is a Researcher in the Telefonica I+D research team, Barcelona. Previously he was a Postdoctoral Researcher in the Web Mining Research Group at Yahoo Labs, Barcelona. He holds a Ph.D. in Computer Science and Engineering from the University of South Florida (2012), a MSc in Computer Science from the University of South Florida (2008), and a BSc in Electrical and Computer Engineering from the National Technical University of Athens, Greece (2006). He is currently interested in distributed management and analysis of user private data, advertising for personal data, load balancing of distributed streaming processing engines, streaming graph analysis, behavior analysis of users in online platforms. He has published more than 40 papers in top conferences and journals such as IEEE International Conference on Data Engineering, ACM World Wide Web Conference, ACM Knowledge Discovery and Data Mining, ACM/IFIP/USENIX Middleware Conference, ACM International Internet Measurement Conference, etc. He has also presented his work on Apache Samoa in relevant venues such as Apache Big Data Conferences in Europe and North America. He has served in many program committees of top academic conferences and journals (e.g., WWW, KDD, CIKM, ACM TKDD, IEEE TKDE, IEEE TPDS, etc.)

Title

Dealing with betweenness in evolving graphs and imposed system workload imbalance

Abstract

Graph problems such as betweenness centrality can be notoriously hard to compute in a static setting. 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. In order to solve such problems efficiently, and compute respective graph metrics online, some have proposed approximation or incremental methods, and others have proposed parallelized execution of properly defined subtasks on parallel and/or streaming platforms. In the first part of this talk, I will cover a framework that applies both strategies for computing betweenness centrality on evolving graphs while generating scores on pseudo-real time. In the second part, I will cover 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.