Three open problems related to temporal graphs

Here are three open problems with relations to temporal graphs that I find interesting. I mentioned them at a recent Dagstuhl Seminar (and I fixed a couple of small errors below).

Self-preserving communities

In their recent work Krakauer et al. [1] put forward a definition of what a biological individual is, based on information-theoretic measures. Essentially, they propose that individuals are subsets of the environment that represent local maxima in the so-called mutual information between consecutive time steps. In plain words, the mutual information of some subset between two time steps is large, if there are many possible states of this subset and the states are strongly correlated between time steps. Even simpler, an individual is lively and it preserves itself. As Krakauer et al. briefly alluded to, this notion also applies in other contexts, such as communities in social networks. The advantage of looking at communities in social networks is that there is ample data to test Krakauer et al.’s hypothesis modified to this context. However, we lack the algorithmic research to do this. What is a concrete formulation as a computational problem to test Krakauer et al.’s hypothesis and what is the computational complexity of solving this problem?

Meta-theorems for multistage problems

The general aim in multistage problems is to find solutions, e.g. independent sets, for each snapshot of a given temporal graph such that the solutions satisfy some quality measure, e.g. an upper bound on the independent set size, and such that the solutions have some temporal relationship, such as differing in few vertices between consecutive snapshots. Several authors studied the computational complexity of concrete multistage problems, see e.g. [2, 3] and references therein. Perhaps time is rife to study the complexity of common problem formulations more generally. A somewhat informal common problem formulation is the following. Given a temporal graph $(G_i)_{i \in [\tau]}$ on vertex set $V$ and integers $k, \ell \in \mathbb{N}$, we want to decide whether the following formula holds: $$\exists (x_{i, j})_{i \in [k], j \in [\tau]} \in V^{k + \tau} \colon \forall j \in [\tau - 1] \colon \textsf{similar}_{j}((x_{i, j}, x_{i, j + 1})_{i \in [k]}, \ell) \wedge \forall j \in [\tau] \colon \textsf{property}_j((x_{i, j})_{i \in [k]}).$$ E.g. to solve a recently studied multistage path problem [3], set $\textsf{property}_j$ to a function that checks whether the sequence of $k$ variables given as an argument is the sequence of vertices of a path in $G_j$ and set $\textsf{similar}_j$ to a formula that checks whether the two sequences of vertices given as an argument differ by at most $\ell$ vertices when interpreted as a set. An example of the type of results that this formulation affords is the following. We may consider a temporal graph as a structure from formal logic, whose domain contains the vertex set and whose signature contains equality and the adjacency relation for each snapshot $G_i$. If the maximum degree in each snapshot is bounded by $\Delta$, and if $\textsf{property}_j$ and $\textsf{similar}_j$ are expressible in first-order logic, then from Seese’s theorem [4] it follows that that the above problem is solvable in $f(\tau, \Delta, \zeta)n$ time where $n$ is the number of vertices, $\zeta$ is the quantifier depth of $\textsf{property}_j$ and $\textsf{similar}_j$ (trivially upper bounded by their length), and $f$ is an exponential function. The (exponential) dependency on $\tau$ is not nice and there are nontrivial examples for which it can be avoided, such as the above mentioned multistage path problem [3]. An open question is for example to explore and characterize the formulas for $\textsf{property}_j$ and $\textsf{similar}_j$ such that dropping exponential dependency on $\tau$ is possible. Another direction is to consider generalizations of Seese’s theorem for structures of bounded local treewidth or other structural sparsity measures [5] and properly adapt them to the multistage setting.

Burstiness

Burstiness refers to the temporal clustering of activity, such as in sending emails, where it can be observed that users have short periods of activity followed by long periods of inactivity. In particular, such clustering results in distributions of inter-interaction times that roughly follow a power law [6]. It is not far-fetched to assume that such structure can be used algorithmically. For example, a simple measure of the degree distribution of a graph is the h-index. The h-index is the largest integer $h$ such that there are at least $h$ vertices of degree at least $h$. This parameter is a small constant in real world networks [7], which often have degree distributions similar to power laws. It is not hard to show then, that the in general NP-hard Independent Set problem is solvable in $O(2^h \cdot h^k \cdot (n + m))$ time, where $k$ is the desired size of the independent set, $n$ the number of vertices and $m$ the number of edges. Similar results hold for other problems including various dense-subgraph problems [8, 9]. The only research in the direction of measuring and exploiting burstiness algorithmically that I am aware of is when we think of burstiness as a kind of temporal sparsity. Himmel et al. [10] looked at unions of intervals of snapshot graphs and computed their so-called degeneracy, a measure of sparsity, and showed that it is a small constant in real-world temporal graphs, much smaller than the degeneracy of the union of all snapshots. However, this is not a first-principles approach and with this method we do not learn or exploit, for example, whether (and how many) bursts temporally overlap. What is a good combinatorial measure of burstiness? Is there one that can be exploited algorithmically, for example, in algorithms enumerating dense temporal subgraphs?

1. The information theory of individuality, Krakauer, D., Bertschinger, N., Olbrich, E., Flack, J.C., Ay, N. Theory in Biosciences. 139, 209–223 (2020).
2. Cluster Editing in Multi-Layer and Temporal Graphs, Chen, J., Molter, H., Sorge, M., Suchý, O. In: Hsu, W.-L., Lee, D.-T., and Liao, C.-S. (eds.) 29th International Symposium on Algorithms and Computation (ISAAC 2018). pp. 24:1–24:13. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2018).
3. Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs, Fluschnik, T., Niedermeier, R., Schubert, C., Zschoche, P. In: Cao, Y., Cheng, S.-W., and Li, M. (eds.) 31st International Symposium on Algorithms and Computation (ISAAC 2020). pp. 43:1–43:16. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2020).
4. Linear time computable problems and first-order descriptions, Seese, D. Mathematical Structures in Computer Science. 6, 505–526 (1996).
5. Deciding First-Order Properties of Nowhere Dense Graphs, Grohe, M., Kreutzer, S., Siebertz, S. J. ACM. 64, 17:1–17:32 (2017).
6. Impact of Non-Poissonian Activity Patterns on Spreading Processes, Vazquez, A., Rácz, B., Lukács, A., Barabási, A.-L. Physical Review Letters. 98, 158702 (2007).
7. The h-Index of a Graph and its Application to Dynamic Subgraph Statistics, Eppstein, D., Spiro, E.S. Journal of Graph Algorithms and Applications. 16, 543–567 (2012).
8. An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems, Komusiewicz, C., Sorge, M. Discrete Applied Mathematics. 193, 145–161 (2015).
9. Finding Highly Connected Subgraphs, Hüffner, F., Komusiewicz, C., Sorge, M. In: SOFSEM 2015: Theory and Practice of Computer Science. pp. 254–265. Springer, Berlin, Heidelberg (2015).
10. Adapting the Bron–Kerbosch algorithm for enumerating maximal cliques in temporal graphs, Himmel, A.-S., Molter, H., Niedermeier, R., Sorge, M. Social Network Analysis and Mining. 7, 35 (2017).