Algorithmic Aspects of Temporal Graphs III*
Satellite workshop of ICALP 2020
Saarbrücken, Germany
Tuesday 7 July 2020
(held online due to the corona pandemic)
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.
Access to the workshops will be free of charge.
However, you should first fill-in the registration form
(use "2. Free Sign-Up" and check the option "AATG: Algorithmic Aspects of Temporal Graphs (July 7)"):
https://icalp2020.saarland-informatics-campus.de/icalp-registration/
The meeting will be hosted on Zoom at the following link (password will be sent to participants):
zoom meeting
We will have the following rules in place for the workshop to run smoothly:
- Please log in to the Zoom meeting using your REAL NAME and AFFILIATION, e.g. "Eleni Akrida, Durham University" or "Eleni Akrida, Durham".
- Please keep your microphone muted unless it is your turn to speak, e.g. if you are the speaker or you are asking a question.
- Should you have any questions while a speaker is presenting, please do not interrupt.
- Instead, please write "question" in the chat. After the talk is over and it is time for questions, the chair of the session will advise those who have commented to ask their questions.
Full information about the registration to the main conference (ICALP 2020) is given here:
https://icalp2020.saarland-informatics-campus.de/registration/
Video Recording
The video recording of most talks can be found in the following playlist on YouTube:
AATG 2020 YouTube playlist.
The individual slides and videos can be found next to the corresponding speaker in the workshop schedule below.
Workshop Schedule
Abstracts
Arnaud Casteigts (LaBRI and University of Bordeaux, France)
Efficient generation of simple temporal graphs up to isomorphism
Abstract: In this work, we consider a particular kind of isomorphism between temporal graphs, where two graphs are isomorphic if and only if they have the same set of temporal paths up to time distortion. The underlying motivation is to capture infinite sets of temporal graphs by finitely many representatives, on which conjectures can subsequently be tested in a comprehensive manner. In this talk, I will focus on the case of "simple temporal graphs", where the edges have exactly one presence time and times are different for adjacent edges. It turns out that the automorphisms of these graphs have special features which allows one to generate the canonical representatives efficiently. The talk will be structured as a gentle discussion covering several topics, from symmetry, to spanners, to generation trees, and a few conjectures.
Amitabh Trehan (Loughborough University, UK)
Sending and Forgetting: Termination of Amnesiac Flooding on a Graph
Abstract:
Imagine a network where every user is very aggressive about forwarding the messages they receive
(like hyperactive WhatsApp users). The users are polite enough in that they do not send the message back
to the users they have just received the message from in the previous round. However, as busy social media
users, they quickly forget this interaction and forward the same message if they get it again in the
future - potentially circulating the same message till the end of social media civilisation!
Consider any arbitrary finite graph modelling such a network and a user who begins the process by flooding
(we call this Amnesiac Flooding) one such message. Amnesiac flooding can also be viewed as a temporal process
on a fixed graph.The natural question is will Amnesiac flooding ever stop i.e. will this message stop
getting circulated? In general, flooding is about the simplest of distributed algorithms achieving broadcast
of messages to all nodes but termination is a critical property to achieve. We analyse both the termination
of Amnesiac Flooding and termination times and get somewhat surprising results.
Based on:
- Walter Hussak and Amitabh Trehan: On The Termination of Flooding, STACS 2020
- Walter,Hussk and Amitabh Trehan: On Termination of a Flooding Process, PODC 2019 (Brief Announcement)
- Walter Hussak and Amitabh Trehan: On The Termination of a Flooding Process (Arxiv 2019)
Clémence Magnien (CNRS and LIP6, Sorbonne Université, France)
Computing Betweenness Centrality in Link Streams
Abstract: Betweeness centrality is one of the most important concepts in graph analysis. It was recently extended to link streams, a graph generalization where links arrive over time. However, its computation raises non-trivial issues, due in particular to the fact that time is considered as continuous. We provide here the first algorithms to compute this generalized betweenness centrality. They work in polynomial time and space, and we illustrate them on typical examples.
Hendrik Molter (Technical University Berlin, Germany)
On Temporal Betweenness Centrality
Abstract:
The betweenness centrality of a graph vertex measures how often this vertex is visited on
shortest paths between other vertices of the graph. In the analysis of many real-world graphs or
networks, betweenness centrality of a vertex is used as an indicator for its relative importance
in the network. In particular, it is among the most popular tools in social network analysis. In
recent years, a growing number of real-world networks is modeled as temporal graphs instead of
conventional (static) graphs. In a temporal graph, we have a fixed set of vertices and there is a
finite discrete set of time steps and every edge might be present only at some time steps. While
shortest paths are straightforward to define in static graphs, temporal paths can be considered
"optimal" with respect to many different criteria, including length, arrival time, and overall
travel time (shortest, foremost, and fastest paths). This leads to different concepts of temporal
betweenness centrality, posing new challenges on the algorithmic side.
Computing the betweenness centrality for vertices in a graph is closely related to count-
ing the number of shortest between vertex pairs. It turns out that counting foremost and fastest
paths is computationally intractable (#P-hard) and hence the computation of the correspond-
ing temporal betweenness values is intractable as well. For shortest paths and two selected
special cases of foremost paths, there are polynomial-time algorithms for temporal betweenness
computation. We provide a overview of the computational complexity of temporal betweenness
variants based on various concepts of optimal temporal paths.
Based on joint work with Sebastian Buß, Rolf Niedermeier, and Maciej Rymar.
Till Fluschnik (Technical University Berlin, Germany)
Temporal Graph Problems From the Multistage Model
Abstract:
In the multistage model, on a high level, we are given a sequence of T instances (stages) of the same problem,
and the task is to find good solutions for each instance such that any two solutions to consecutive instances are of small distance
(w.r.t some given distance function).
As an illustrative example, in the Multistage Vertex Cover problem, given T instances of Vertex Cover --over the same vertex set
and each with the same integer k-- and an integer l, the question is whether there is a sequence of k-sized solutions to the
instances such that any two solutions to consecutive instances have symmetric difference of size at most l.
This is a temporal graph problem: Given a temporal graph with lifetime T, integers k and l, is there a k-sized vertex cover
for each layer such that any two vertex covers to consecutive layers have symmetric difference of size at most l.
In this talk, we consider temporal graph problems derived from the multistage model. We give a brief introduction, present
two multistage graph problems (finding small vertex covers and short s-t paths) in more (algorithmic) detail, and discuss other
(than the symmetric difference) distance functions in and variations to the multistage model.
Philipp Zschoche (Technical University Berlin, Germany)
Finding Temporal Paths under Waiting Time Constraints
Abstract:
Computing a (short) path between two vertices is one of the
most fundamental primitives in graph algorithmics. In recent years, the
study of paths in temporal graphs, that is, graphs where the vertex set
is fixed but the edge set changes over time, gained more and more
attention. A path is time-respecting, or temporal, if it uses edges with
non-decreasing time stamps. We investigate a basic constraint for
temporal paths, where the time spent at each vertex must not exceed a
given duration Δ, referred to as Δ-restless temporal
paths. This constraint arises naturally in the modeling of real-world
processes like packet routing in communication networks and infection
transmission routes of diseases where recovery confers lasting
resistance. While finding temporal paths without waiting time
restrictions is known to be doable in polynomial time, we show that the
"restless variant" of this problem becomes computationally hard even in
very restrictive settings. For example, it is W[1]-hard when
parameterized by the feedback vertex number or the pathwidth of the
underlying graph. The main question thus is whether the problem becomes
tractable in some natural settings. We explore several natural
parameterizations, presenting FPT algorithms for three kinds of
parameters: (1) output-related parameters (here, the maximum length of
the path), (2) classical parameters applied to the underlying graph
(e.g., feedback edge number), and (3) a new parameter called timed
feedback vertex number, which captures finer-grained temporal features
of the input temporal graph, and which may be of interest beyond this work.
This is joint work with Arnaud Casteigts, Anne-Sophie Himmel, and Hendrik Molter.
Thomas Erlebach (University of Leicester, UK)
Non-Strict Temporal Exploration
Abstract:
A temporal graph G = (G_1, ..., G_L) is a sequence of graphs G_i, all of which are spanning subgraphs of an underlying graph.
We consider the non-strict variant of the Temporal Exploration problem, in which we are looking for a walk that visits all vertices and
in which the time steps during which edges are traversed are non-decreasing (but an arbitrary number of edges can be traversed in the same time step).
Deciding the existence of an exploration schedule is shown to be NP-complete for this variant. We also consider the hardness of
approximating the exploration time for yes-instances in which the input graph with n vertices satisfies certain assumptions that
ensure that exploration schedules always exist. The first is that each pair of vertices are contained in the same component at least
once in every period of n steps, whilst the second is that the temporal diameter of the input graph is bounded by a constant c.
For the latter of these two assumptions we show O(n^{1/2-eps})-inapproximability and O(n^{1-eps})-inapproximability in the cases c = 2 and c >= 3,
respectively. For graphs with temporal diameter c = 2, we also prove an O(n^{1/2} log n) upper bound on the worst-case time required for exploration,
as well as a lower bound of Omega(n^{1/2}) steps.
This is a joint work with Jakob Spooner.
Andrea Clementi (University of Rome Tor Vergata, Italy)
Simple Dynamic Graphs with Churn
Abstract:
We consider a natural dynamic network model with random node churn,
namely, a model where the nodes are inserted and deleted in the
network according to a simple random process. The dynamic random
topology of the network is determined by an elementary local rule that
keeps the graph sparse at every round.
We first prove that each snapshot of the graph process has constant
vertex expansion, with high probability. Then, we exploit this key
property to give a logarithmic bound on the flooding time.
Finally, we discuss possible extensions of our analysis techniques to
other models of dynamic graphs with churn.
This is a joint research with Luca Becchetti, Francesco Pasquale, Luca
Trevisan, and Isabella Ziccardi.
George Skretas (University of Liverpool, UK)
Distributed Algorithms for Actively Dynamic Networks
Abstract:
In this talk, motivated by recent advances in the algorithmic theory of dynamic networks, we study systems of distributed entities
that can actively modify their communication network. This gives rise to distributed algorithms that apart from communication can also
exploit network reconfiguration in order to carry out a given task. At the same time, the distributed task itself may now require a
global reconfiguration from a given initial network G_s to a target network G_f from a family of networks having some good properties,
like small diameter.
To formally capture costs associated with creating and maintaining connections, we define three reasonable edge-complexity measures:
the total edge activations, the maximum active edges per round, and the maximum degree of a node. We highlight a
natural trade-off between time and edge complexity. We give (poly)log(n)
time algorithms for transforming any initial connected network G_s into a network G_f of (poly)logarithmic diameter and at the same
time electing a unique leader, while minimizing the edge-complexity. We then discuss lower bounds.
This novel model of distributed computation and reconfiguration in actively dynamic networks and the proposed measures of the edge
complexity of distributed algorithms may open new avenues for research in the algorithmic theory of dynamic networks. At the same time,
they may serve as an abstraction of more constrained active-reconfiguration systems, such as reconfigurable robotics which come with
geometric constraints, and draw interesting connections with alternative network reconfiguration models, like overlay network construction
and network constructors. We discuss several open problems and promising future research directions.
This talk is based on a joint work with O. Michail and P. G. Spirakis to appear in PODC 2020.
Julia Stoyanovich (New York University Tandon School of Engineering, USA)
Querying billion-edge evolving property graphs with Portal
Abstract: In this talk I will give an overview of the Portal project that aims to support principled and efficient querying and analysis of evolving property graphs. We build on advances in graph databases and in temporal relational databases and propose an evolving graph model called TGraph, together with a compositional Temporal Graph Algebra (TGA) that operates under point-based semantics. TGA includes principled temporal generalizations of conventional graph operators, as well as novel zoom operators that support exploratory analysis of evolving graphs at different levels of temporal and structural granularity. I will briefly describe our implementation of TGraph and TGA on top of Apache Spark --- a scalable distributed dataflow system. Additional details about our project, and the open-source code base, are available at portaldb.github.io.
Jessica Enright (University of Glasgow, UK)
Incorporating temporal graph structure from data in pandemic modelling
Abstract: Infectious diseases spread over graphs that describe contact between infectious units, and it is no surprise that temporal characteristics of the graph play an important role on the course of the disease spread. Many models being used for the current COVID-19 pandemic make use of data-derived contact graphs that change over time - some make use of this information explicitly as a network, and some more implicitly as a replay of simulated contacts. I will outline some of the examples of this (I’m sure to miss many out - my apologies for that!) and highlight examples in which the network plays a key role, or the model is highly sensitive to the temporal graph involved. This will be a largely non-technical talk, with examples of data types and sources, and a frank discussion of the limitations of some of the approaches and simplifications that I have been using in my own modelling work.
Nicola Santoro (Carleton University, Canada)
Exploration of Asynchronous Temporal Graphs (of Unknown Arbitrary Topology)
Abstract: The graph exploration problem (Exploration) requires each node of the graph to be visited by one or more mobile computational entities, called agents, a nite number of times (exploration with termination) or innitely often (perpetual exploration). This problem has been extensively studied over a variety of assumptions and settings, depending on whether the nodes have distinct labelings or are anonymous, on whether the agents have Ids or are anonymous, the type of mechanism available to the agents for in- teraction communication (i.e., whiteboards, tokens, face-to-face, vision), on the degree of synchronization (i.e., asynchronous, semi-synchronous, fully-synchronous), on the level of knowledge the agents have about the graph, on their memory, etc. Exploration has been recently investigated also in temporal (or evolving) graphs. All the existing results on distributed exploration of temporal graphs have been obtained for synchronous temporal graphs, with strict connectivity assumptions, and usually with very specic topologies (rings, tori, or collections of cycles). In this talk I will discuss the recent investigation and results on the problem of exploring temporal graphs of arbitrary unknown topology, and more in general on distributed computing in asynchronous temporal graphs.
Paola Flocchini (University of Ottawa, Canada)
Exploration of dangerous temporal graphs
Abstract:
In this talk I am going to focus on the exploration of temporal graphs
by mobile agents in presence of a black hole, a harmful node
that destroys all incoming agents without leaving any trace.
The goal of the agents is to visit all the nodes of the graph and to have
at least one surviving agent know the exact location of the black hole.
Clearly, dangerous exploration (also called black hole search)
is unsafe for the agents, as any agent entering the black hole will be destroyed
and some losses have to be expected.
Black Hole Search has been investigated extensively in static graphs,
where strategies employing the minimum number of agents have been
studied in various settings, minimizing the number of moves and time.
Nothing is known when the graph is dynamic, and in this talk I will move
the first steps in this direction describing optimal algorithms for 1-interval connected rings.
George B. Mertzios (Durham University, UK)
Paul G. Spirakis (University of Liverpool, UK and University of Patras, Greece)
Eleni C. Akrida (Durham University, UK)
Viktor Zamaraev (University of Liverpool, UK)
* Partially supported by the EPSRC grants EP/P020372/1 and EP/P02002X/1, and by the EEE/CS University of Liverpool Initiative NeST.