Algorithmic Aspects of Temporal Graphs II*
Satellite workshop of ICALP 2019
Patras, Greece
Monday 8 July 2019
Topic
In modern systems the classical modeling paradigm using static graphs may be restrictive or oversimplifying,
as the interactions among the elementary system units usually change over time in a highly dynamic manner.
For example, friendships are added and removed over time in a social network and
links in a communication network may change dynamically,
either according to a specific known pattern (satellites following a trajectory)
or in an unpredictable manner (mobile ad hoc networks).
The common characteristic in all these application areas is that the system structure,
i.e. graph topology, is subject to discrete changes over time.
In such dynamically changing graphs the notion of vertex adjacency needs to be
revisited and various graph concepts, e.g. reachability and connectedness, now crucially
depend on the exact temporal ordering of the edges' presence.
A temporal graph is a graph that changes over time. Assuming discrete time and a fixed set V of vertices,
a temporal graph can be viewed as a discrete sequence G1, G2, ... of static graphs, each with vertex set V.
Many notions and algorithms from the static case can be naturally transferred in a meaningful way
to their temporal counterpart, while in other cases new approaches are needed to define the
appropriate temporal notions. In particular, some problems become radically different and
substantially more difficult when the time dimension is additionally taken into account.
In this one-day workshop, recent advances in the area of temporal / dynamically changing graphs will be presented, as well as some of the key challenges will be highlighted.
As this research area grows and broadens, our aim is to bring together people from theoretical and practical communities of temporal graphs in order to establish new and strengthen existing links between these communities.
Presentations are given by invitation only. Everyone is welcome to register and attend.
Practical information
Every presentation is given 25 minutes in total, which is expected to be 20 minutes of talk and 5 minutes of questions.
The presentations are grouped into four sessions (two in the morning and two in the afternoon).
Details of the invited speakers and the schedule can be found below. A participant can register only to the workshop (Monday 8 July),
or to both the workshop and the conference (Monday 8 July to Friday 12 July). Early registration is until 31 May.
Full information about the registration to the workshop and/or the conference, as well as about accommodation, is given here:
https://icalp2019.upatras.gr/regis.php
Workshop Schedule (tentative)
Abstracts
Kitty Meeks (University of Glasgow, UK)
[slides]
Optimising reachability by reordering
Abstract:
The concept of reachability (i.e. which vertices in a graph can be reached by travelling along edges from a given starting vertex)
is central to many applications, including the dissemination of information or the spread of disease through a network.
Depending on the application, it might be desirable to increase or decrease the number of vertices that are reachable from any one starting vertex.
In most applications, time plays a crucial role: each contact between individuals, represented by an edge, will only occur at certain time(s).
The relative timing of edges is clearly crucial in determining the reachability of any vertex in the graph.
In the static setting, there has been a significant body of work addressing how graph modifications
(typically the insertion and/or deletion of vertices and/or edges) can be used to increase or decrease the number of vertices reachable from a single starting vertex.
While these notions are still relevant in the temporal setting, we can also consider a different kind of modification in which we do not modify the underlying graph
but instead change the relative temporal ordering of the edges. This kind of modification - in which only the timing of certain contacts is changed - is potentially
more feasible to carry out on real networks in practice (we consider, for example, the feasibility of re-ordering the trades that give rise to a contact network between
livestock) than modifications that completely remove certain edges; the model becomes more realistic still if we allow for some restrictions on how this rescheduling
can be done (e.g. only certain times are permitted, or specified pairs of edges must be active simultaneously).
At the 2018 workshop, Jessica Enright and myself reported on some initial results in this setting (almost all of which demonstrated intractability).
In this talk I will provide updates on some more recent progress, including both stronger hardness results and some positive results for special cases,
as well as discussing several promising directions for future work.
This is joint work with Jessica Enright and Fiona Skerman.
Argyrios Deligkas (University of Liverpool, UK)
[slides]
On minimizing/maximizing reachability sets in temporal graphs by independent time delays
Abstract:
A temporal graph is the variant of a dynamic graph, where a set of pairwise relations between objects is not permanent and can be changed in discrete time steps.
In this paper we study how the changes of the time labels (e.g. corresponding to global delays) for a given temporal graph can effect its (temporal) connectivity
estimating the size of the reachability sets from given sources. These reachability questions have been motivated by the applications of the temporal graphs to model
various disease-spreading contact networks or supply networks in manufacturing. In particular we analyze the mechanisms of independent delays implemented by merging
operations and show that finding the optimal set of delays with different minimization and maximization reachability objectives is NP-hard even for very simple graph
structures. We provide several new encodings of satisfiability questions into the realm of temporal graphs and independent delays that reveal various new mechanisms
of controlling reachability sets in indirect way.
This is joint work with Igor Potapov.
Christos Zaroliagis (University of Patras, Greece)
[slides]
Multimodal dynamic journey planning
Abstract: Timetable information systems of multimodal public (schedule-based) transport networks can be represented by a suitable directed graph model, whose arcs are associated with travel times. The graph may change over time as delays of public transport vehicles inevitably occur. Two key routines in timetable information systems are (i) the efficient update the timetable information in case of delays, and (ii) the real-time computation of multimodal journey planning queries. In this work, we present multimodal DTM, a new model for multimodal journey planning in public (schedule-based) transport networks. Multimodal DTM constitutes an extension of the dynamic timetable model (DTM), developed originally for unimodal journey planning. Multimodal DTM exhibits a very fast query algorithm, meeting the request for real-time response to best journey queries and an extremely fast update algorithm for updating the timetable information in case of delays. In particular, an experimental study on real-world metropolitan networks demonstrates that our methods compare favorably with other state-of-the-art approaches when public transport along with unrestricted with respect to departing time traveling (walking and electric vehicles) is considered.
Thomas Erlebach (University of Leicester, UK)
[slides]
A game of cops and robbers on graphs with periodic edge-connectivity
Abstract:
We consider a game in which a single cop and a single robber take turns moving along the edges of a given graph G.
If there exists a strategy for the cop which enables it to be positioned at the same vertex as the robber eventually,
then G is called cop-win, and robber-win otherwise. We study this classical combinatorial game in a novel context,
broadening the class of potential game arenas to include the edge-periodic graphs.
These are graphs with an infinite lifetime comprised of discrete time steps such that each edge e is assigned a bit pattern of length
le, with a 1 in the i-th position of the pattern indicating the presence of edge e in the i-th step of each consecutive block of
le steps. Utilising the existing framework of reachability games, we obtain, amongst other results, an O(LCM(L) * n3)
upper bound on the time required to decide if a given n-vertex edge-periodic graph is cop or robber win as well as compute a strategy for the winning player
(here, L is the set of all edge pattern lengths le, and LCM(L) denotes the least common multiple of the set L). We also prove an upper bound of 8*k*LCM(L)
on the length that is sufficient to ensure that an edge-periodic cycle is robber win, where k = 1 if LCM(L) ≥ 2*max(L), and k=2 otherwise.
This is joint work with Jakob T. Spooner.
Arnaud Casteigts (LaBRI and University of Bordeaux, France)
[slides]
A few sparsification techniques preserving temporal connectivity
Abstract: In this talk, I will present some techniques for removing edges from a temporal graph without breaking its temporal connectivity. These techniques were recently used to obtain sparse spanners in a class of dense temporal graphs whose schedule is adversarial, the very existence of such spanners being open before (ICALP 2019, joint work with J. Peters and J. Schoeters). The presented techniques are 1) delegation and k-hop delegation, 2) dismountability, 3) forward and backward fireworks, and 4) pivotability. Some of these techniques seem specific to the case of complete graphs, while some others may be more widely applicable.
Spyros Kontogiannis (University of Ioannina, Greece)
[slides]
Exploring earliest-arrival paths in large-scale, time-dependent networks via combinatorial oracles
Abstract: A novel landmark-based oracle (CFLAT) is designed, analyzed and engineered, for providing earliest-arrival-time routes in time-dependent road networks. The preprocessesed information consists of combinatorial structures (i.e., collections of time-stamped min-travel-time-path trees) rather than approximations of travel-time functions. This information is then exploited by a novel query algorithm (CFCA) which computes (and has to pay for it) the actual connecting path that preserves the theoretical approximation guarantees. A thorough experimental evaluation on two real-world benchmark instances, as well as a typical synthetic benchmark, shows that CFLAT achieves significant improvements on the preprocessing requirements, approximation guarantee and query-time for providing earliest-arrival-time paths, in comparison to previous landmark-based oracles. It also achieves competitive query-time performance, compared to state-of-art speedup heuristics for time-dependent road networks, whose query-times in most cases do not account for path construction.
Francesco Pasquale (Tor Vergata University of Rome, Italy)
[slides]
Self-stabilization and expansion of a simple dynamic random graph model for Bitcoin-like unstructured P2P networks
Abstract:
The Bitcoin P2P network is formed by thousands of nodes running the Bitcoin
protocol. While the nodes participating in the network are mostly known, the
peer discovery process in the protocol is explgicitly designed to hide the
global network structure.
In this talk we present a simple dynamic random graph model inspired by the
peer discovery process in the Bitcoin protocol and we analyze its robustness
with respect to self-stabilization and expansion: We show that the network
dynamics quickly converges to a stable random graph that turns out to be a good
expander, with high probability.
Based on a joint work with Luca Becchetti, Andrea Clementi, Emanuele Natale, and Luca Trevisan.
Malte Renken (TU Berlin, Germany)
[slides]
Comparing temporal graphs with time warping
Abstract:
The connections within many real-world networks change over time,
leading to the study of so-called temporal graphs. Recognizing patterns
in these requires a similarity measure to compare different temporal
graphs. To this end, we propose an approach using dynamic time warping
(an established concept in the context of time series). The resulting
measure is called the temporal graph warping distance.
Finally, we talk about the hardness of computing this distance, give
ways to get around it, and show some examples involving real-world data.
Based on joint work with Vincent Froese, Brijnesh Jain and Rolf Niedermeier.
Prithwish Basu (Raytheon BBN Technologies, USA)
[slides]
Clustering and summarizing temporal graphs
Abstract: Real-world networks and processes running on them typically evolve over time and can be naturally modeled as temporal graphs. Detecting the existence of significant groups of nodes over space and time may reveal important information about the network's function. We will discuss three diverse methods to address this challenge: (1) detection of spatio-temporal clusters using tensor-decomposition; (2) detection of significant node-valued clusters in temporal graphs using graph-convolution neural networks; and (3) application of tools from topological data analysis for summarizing temporal graphs. We will also discuss real-world applications of these methods.
Polina Rozenshtein (Aalto University, Finland)
[slides]
The network-untangling problem: From interactions to activity timelines
Abstract:
We introduce and a novel problem formulation for summarizing temporal networks.
The inferred network summary has the form of an activity timeline over network entities.
In particular, we consider a set of entities V and a sequence of time-stamped edges E among the entities.
Each edge (u, v, t) ∊ E denotes an interaction between entities u and v that takes place at time t.
Then we assume a simple activity model in which each entity can be active during at most k time intervals.
An interaction (u, v, t) can be explained if at least one of the two entities, u or v, is active at time t.
Our goal is to reconstruct the activity intervals for all entities in the network so as to explain all observed interactions.
We seek parsimonious models and activity intervals with minimum length. The resulting problem is refer to as the network-untangling problem.
We provide two formulations of the network-untangling problem: (i) minimizing the total activity interval length (sum version),
and (ii) minimizing the maximum activity interval length (max version). We study separately the two problems for k = 1 and k > 1 activity intervals per entity.
For the single activity-interval model (where k = 1), we show that the sum problem is NP-hard, while, surprisingly, the max problem can be solved optimally
in linear time, using a mapping to 2-SAT. For the sum problem we provide efficient algorithms motivated by realistic assumptions.
For the case of k > 1 activity intervals per entity, we show that both formulations are inapproximable. However, we propose efficient algorithms.
We complement our study with evaluation on synthetic and real-world datasets, which demonstrates the validity of the proposed problem definitions and the good
performance of our algorithms.
This is joint work with Nikolaj Tatti and Aristides Gionis.
Zwi Lotker (Ben-Gurion University of the Negev, Israel)
[slides]
The tale of two clocks
Abstract:
It is common knowledge that people perceive time differently in different situations. However, when studying dynamic networks,
there is always a single time (single clock). The talk will explain how to incorporate time perceptions into the basic model of
dynamic networks by using different clocks.
The talk is based on the paper "The tale of two clocks", published at ASONAM 2016.
Marco Piangerelli (University of Camerino, Italy)
[slides]
TDA and Persistent Homology: a new method for analysing temporal graphs
Abstract:
Temporal networks are a mathematical model to represent correlations (interactions) evolving over time.
Topological Data Analysis (TDA) is a framework that allows one to examine data across multiple scales in a robust and mathematically
established manner and, via Persistent Homology (PH) to extract the topological invariants.
So far, these methods were employed with static graphs in order to provide a summary of topological features, but applications to temporal
networks have never been studied in detail. Among the main features of TDA it is possible to mention that the analysis is metric-free
and the data set has to be presented, almost every time, as a graph or as a point cloud. We investigate applications of TDA and PH to
dynamically generated graphs using a tool developed by our group: CholeR.
That tool allows to generate different kind of networks and then using TDA equipped with a particular filtration,
the clique weighted rank filtration (CWRF), for investigate the main features of the graph. Moreover, CholeR has been used to analyze
the networks derived from real data: a EEG signals of epileptic and non epileptic signals to deriving temporal graphs and temporal simplicial complex.
This is joint work with Emanuela Merelli.
Amitabh Trehan (Loughborough University, UK)
[slides]
Temporal evolution of self-healing graphs
Abstract: Self-healing is a fault-tolerance paradigm for reconfigurable/peer-to-peer/overlay network/graphs. Over time, at each adversarial attempt, an adversary deletes a node or inserts one with edges - the affected nodes respond by locally inserting edges. The aim is to maintain certain global properties such as diameter, stretch, expansion etc over the whole timeline. In this talk, we discuss some results and the issues related to analysing self-healing algorithms in the dynamic settings.
Nicola Santoro (Carleton University, Canada)
[slides]
On infinity, continuity, regularity, and time-varying graphs
Abstract: This talk will briefly highlight some important viewpoints, intriguing aspects and interesting issues in the research on Time-Varying Graphs, which however are sometimes neglected or unclear. The aim is to stimulate the research attention to these aspects and issues.
George B. Mertzios (Durham University, UK)
Paul G. Spirakis (University of Liverpool, UK and University of Patras, Greece)
Eleni C. Akrida (University of Liverpool, UK)
Viktor Zamaraev (Durham University, UK)
* Partially supported by the EPSRC grants EP/P020372/1 and EP/P02002X/1, and by the EEE/CS University of Liverpool Initiative NeST.