Lutz Oettershagen
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Lutz Oettershagen has a total of 13 co-authors. Here are the top co-authors by number of shared publications:
- Petra Mutzel
University of Bonn, Bonn, Germany
4 shared publications - Aristides Gionis
KTH Royal Institute of Technology, Stockholm, Sweden and Digital Futures, Stockholm, Sweden
2 shared publications - Giuseppe Francesco Italiano
Luiss University, Rome, Italy
2 shared publications - Nils Morten Kriege
Faculty of Computer Science University of Vienna Vienna Austria
2 shared publications Petra Mutzel
Institute of Computer Science, University of Bonn, Bonn, Germany
2 shared publications- Anne Driemel
University of Bonn
1 shared publication
Latest Publications
- Open Access
- 10 March 2025
- Published by Association for Computing Machinery (ACM)
- p. 735-743
An Edge-Based Decomposition Framework for Temporal Networks
- 10 March 2025
- Published by Association for Computing Machinery (ACM)
- p. 735-743
Open AccessAn Edge-Based Decomposition Framework for Temporal Networks
- Open Access
- 13 May 2024
- Published by Association for Computing Machinery (ACM)
- p. 1260-1263
Mining Temporal Networks
In World Wide Web (WWW) systems, networks (or graphs) serve as a fundamental tool for representing, analyzing, and understanding linked data, providing significant insights into the underlying systems. Naturally, most real-world systems have inherent temporal information, e.g., interactions in social networks occur at specific moments in time and last for a certain period. Temporal networks, i.e., network data modeling temporal information, enable novel and fundamental discoveries about the underlying systems they model, otherwise not captured by static networks that ignore such temporal information. In this tutorial, we present state-of-the-art models and algorithmic techniques for mining temporal networks that can provide precious insights into a plethora of web-related applications. We present how temporal networks can be used to extract novel information, especially in web-related network data, and highlight the challenges that arise when modeling temporal information compared to traditional static network-based approaches. We first overview different temporal network models. We then show how such powerful models can be leveraged to extract novel insights through suitable mining primitives. In particular, we present recent advances addressing most foundational problems for temporal network mining---ranging from the computation of temporal centrality measures, temporal motif counting, and temporal communities to bursty events and anomaly detection.
- 13 May 2024
- Published by Association for Computing Machinery (ACM)
- p. 1260-1263
Open AccessMining Temporal Networks
In World Wide Web (WWW) systems, networks (or graphs) serve as a fundamental tool for representing, analyzing, and understanding linked data, providing significant insights into the underlying systems. Naturally, most real-world systems have inherent temporal information, e.g., interactions in social networks occur at specific moments in time and last for a certain period. Temporal networks, i.e., network data modeling temporal information, enable novel and fundamental discoveries about the underlying systems they model, otherwise not captured by static networks that ignore such temporal information. In this tutorial, we present state-of-the-art models and algorithmic techniques for mining temporal networks that can provide precious insights into a plethora of web-related applications. We present how temporal networks can be used to extract novel information, especially in web-related network data, and highlight the challenges that arise when modeling temporal information compared to traditional static network-based approaches. We first overview different temporal network models. We then show how such powerful models can be leveraged to extract novel insights through suitable mining primitives. In particular, we present recent advances addressing most foundational problems for temporal network mining---ranging from the computation of temporal centrality measures, temporal motif counting, and temporal communities to bursty events and anomaly detection.
- Open Access
- 13 May 2024
- Published by Association for Computing Machinery (ACM)
- p. 936-947
Finding Densest Subgraphs with Edge-Color Constraints
We consider a variant of the densest subgraph problem in networks with single or multiple edge attributes. For example, in a social network, the edge attributes may describe the type of relationship between users, such as friends, family, or acquaintances, or different types of communication. For conceptual simplicity, we view the attributes as edge colors. The new problem we address is to find a diverse densest subgraph that fulfills given requirements on the numbers of edges of specific colors. When searching for a dense social network community, our problem will enforce the requirement that the community is diverse according to criteria specified by the edge attributes. We show that the decision versions for finding exactly, at most, and at least h colored edges densest subgraph, where h is a vector of color requirements, are NP-complete, for already two colors. For the problem of finding a densest subgraph with at least h colored edges, we provide a linear-time constant-factor approximation algorithm when the input graph is sparse. On the way, we introduce the related at least h (non-colored) edges densest subgraph problem, show its hardness, and also provide a linear-time constant-factor approximation. In our experiments, we demonstrate the efficacy and efficiency of our new algorithms.
- 13 May 2024
- Published by Association for Computing Machinery (ACM)
- p. 936-947
Open AccessFinding Densest Subgraphs with Edge-Color Constraints
We consider a variant of the densest subgraph problem in networks with single or multiple edge attributes. For example, in a social network, the edge attributes may describe the type of relationship between users, such as friends, family, or acquaintances, or different types of communication. For conceptual simplicity, we view the attributes as edge colors. The new problem we address is to find a diverse densest subgraph that fulfills given requirements on the numbers of edges of specific colors. When searching for a dense social network community, our problem will enforce the requirement that the community is diverse according to criteria specified by the edge attributes. We show that the decision versions for finding exactly, at most, and at least h colored edges densest subgraph, where h is a vector of color requirements, are NP-complete, for already two colors. For the problem of finding a densest subgraph with at least h colored edges, we provide a linear-time constant-factor approximation algorithm when the input graph is sparse. On the way, we introduce the related at least h (non-colored) edges densest subgraph problem, show its hardness, and also provide a linear-time constant-factor approximation. In our experiments, we demonstrate the efficacy and efficiency of our new algorithms.
- Open Access
- 4 August 2023
- Published by Association for Computing Machinery (ACM)
- p. 1770-1782
A Higher-Order Temporal H-Index for Evolving Networks
The H-index of a node in a static network is the maximum value h such that at least h of its neighbors have a degree of at least h. Recently, a generalized version, the n-th order H-index, was introduced, allowing to relate degree centrality, H-index, and the k-core of a node. We extend the n-th order H-index to temporal networks and define corresponding temporal centrality measures and temporal core decompositions. Our n-th order temporal H-index respects the reachability in temporal networks leading to node rankings, which reflect the importance of nodes in spreading processes. We derive natural decompositions of temporal networks into subgraphs with strong temporal coherence. We analyze a recursive computation scheme and develop a highly scalable streaming algorithm. Our experimental evaluation demonstrates the efficiency of our algorithms and the conceptional validity of our approach. Specifically, we show that the n-th order temporal H-index is a strong heuristic for identifying possible super-spreaders in evolving social networks and detects temporally well-connected components.
- 4 August 2023
- Published by Association for Computing Machinery (ACM)
- p. 1770-1782
Open AccessA Higher-Order Temporal H-Index for Evolving Networks
The H-index of a node in a static network is the maximum value h such that at least h of its neighbors have a degree of at least h. Recently, a generalized version, the n-th order H-index, was introduced, allowing to relate degree centrality, H-index, and the k-core of a node. We extend the n-th order H-index to temporal networks and define corresponding temporal centrality measures and temporal core decompositions. Our n-th order temporal H-index respects the reachability in temporal networks leading to node rankings, which reflect the importance of nodes in spreading processes. We derive natural decompositions of temporal networks into subgraphs with strong temporal coherence. We analyze a recursive computation scheme and develop a highly scalable streaming algorithm. Our experimental evaluation demonstrates the efficiency of our algorithms and the conceptional validity of our approach. Specifically, we show that the n-th order temporal H-index is a strong heuristic for identifying possible super-spreaders in evolving social networks and detects temporally well-connected components.
- Open Access
A Temporal Graphlet Kernel for Classifying Dissemination in Evolving Networks
We introduce the \emph{temporal graphlet kernel} for classifying dissemination processes in labeled temporal graphs. Such dissemination processes can be spreading (fake) news, infectious diseases, or computer viruses in dynamic networks. The networks are modeled as labeled temporal graphs, in which the edges exist at specific points in time, and node labels change over time. The classification problem asks to discriminate dissemination processes of different origins or parameters, e.g., infectious diseases with different infection probabilities. Our new kernel represents labeled temporal graphs in the feature space of temporal graphlets, i.e., small subgraphs distinguished by their structure, time-dependent node labels, and chronological order of edges. We introduce variants of our kernel based on classes of graphlets that are efficiently countable. For the case of temporal wedges, we propose a highly efficient approximative kernel with low error in expectation. We show that our kernels are faster to compute and provide better accuracy than state-of-the-art methods.
Open AccessA Temporal Graphlet Kernel for Classifying Dissemination in Evolving Networks
We introduce the \emph{temporal graphlet kernel} for classifying dissemination processes in labeled temporal graphs. Such dissemination processes can be spreading (fake) news, infectious diseases, or computer viruses in dynamic networks. The networks are modeled as labeled temporal graphs, in which the edges exist at specific points in time, and node labels change over time. The classification problem asks to discriminate dissemination processes of different origins or parameters, e.g., infectious diseases with different infection probabilities. Our new kernel represents labeled temporal graphs in the feature space of temporal graphlets, i.e., small subgraphs distinguished by their structure, time-dependent node labels, and chronological order of edges. We introduce variants of our kernel based on classes of graphlets that are efficiently countable. For the case of temporal wedges, we propose a highly efficient approximative kernel with low error in expectation. We show that our kernels are faster to compute and provide better accuracy than state-of-the-art methods.
- Open Access
- 8 January 2022
- Published by Springer Nature in Knowledge and Information Systems
- Vol. 64 (2) , 507-535
Computing top-k temporal closeness in temporal networks
The closeness centrality of a vertex in a classical static graph is the reciprocal of the sum of the distances to all other vertices. However, networks are often dynamic and change over time. Temporal distances take these dynamics into account. In this work, we consider the harmonic temporal closeness with respect to the shortest duration distance. We introduce an efficient algorithm for computing the exact top-ktemporal closeness values and the corresponding vertices. The algorithm can be generalized to the task of computing all closeness values. Furthermore, we derive heuristic modifications that perform well on real-world data sets and drastically reduce the running times. For the case that edge traversal takes an equal amount of time for all edges, we lift two approximation algorithms to the temporal domain. The algorithms approximate the transitive closure of a temporal graph (which is an essential ingredient for the top-kalgorithm) and the temporal closeness for all vertices, respectively, with high probability. We experimentally evaluate all our new approaches on real-world data sets and show that they lead to drastically reduced running times while keeping high quality in many cases. Moreover, we demonstrate that the top-ktemporal and static closeness vertex sets differ quite largely in the considered temporal networks.
- 8 January 2022
- Published by Springer Nature in Knowledge and Information Systems
- Vol. 64 (2) , 507-535
Open AccessComputing top-k temporal closeness in temporal networks
The closeness centrality of a vertex in a classical static graph is the reciprocal of the sum of the distances to all other vertices. However, networks are often dynamic and change over time. Temporal distances take these dynamics into account. In this work, we consider the harmonic temporal closeness with respect to the shortest duration distance. We introduce an efficient algorithm for computing the exact top-ktemporal closeness values and the corresponding vertices. The algorithm can be generalized to the task of computing all closeness values. Furthermore, we derive heuristic modifications that perform well on real-world data sets and drastically reduce the running times. For the case that edge traversal takes an equal amount of time for all edges, we lift two approximation algorithms to the temporal domain. The algorithms approximate the transitive closure of a temporal graph (which is an essential ingredient for the top-kalgorithm) and the temporal closeness for all vertices, respectively, with high probability. We experimentally evaluate all our new approaches on real-world data sets and show that they lead to drastically reduced running times while keeping high quality in many cases. Moreover, we demonstrate that the top-ktemporal and static closeness vertex sets differ quite largely in the considered temporal networks.
- Open Access
Spatio-Temporal Top-k Similarity Search for Trajectories in Graphs
We study the problem of finding the $k$ most similar trajectories to a given query trajectory. Our work is inspired by the work of Grossi et al. [6] that considers trajectories as walks in a graph. Each visited vertex is accompanied by a time-interval. Grossi et al. define a similarity function that captures temporal and spatial aspects. We improve this similarity function to derive a new spatio-temporal distance function for which we can show that a specific type of triangle inequality is satisfied. This distance function is the basis for our index structures, which can be constructed efficiently, need only linear memory, and can quickly answer queries for the top-$k$ most similar trajectories. Our evaluation on real-world and synthetic data sets shows that our algorithms outperform the baselines with respect to indexing time by several orders of magnitude while achieving similar or better query time and quality of results.Open AccessSpatio-Temporal Top-k Similarity Search for Trajectories in Graphs
We study the problem of finding the $k$ most similar trajectories to a given query trajectory. Our work is inspired by the work of Grossi et al. [6] that considers trajectories as walks in a graph. Each visited vertex is accompanied by a time-interval. Grossi et al. define a similarity function that captures temporal and spatial aspects. We improve this similarity function to derive a new spatio-temporal distance function for which we can show that a specific type of triangle inequality is satisfied. This distance function is the basis for our index structures, which can be constructed efficiently, need only linear memory, and can quickly answer queries for the top-$k$ most similar trajectories. Our evaluation on real-world and synthetic data sets shows that our algorithms outperform the baselines with respect to indexing time by several orders of magnitude while achieving similar or better query time and quality of results. - 1 October 2020
- Published by SAGE Publications in Big Data
- Vol. 8 (5) , 363-378
Classifying Dissemination Processes in Temporal Graphs
Many real-world graphs are temporal, for example, in a social network, persons only interact at specific points in time. This temporal information directs dissemination processes on the graph, such as the spread of rumors, fake news, or diseases. However, the current state-of-the-art methods for supervised graph classification are mainly designed for static graphs and may not capture temporal information. Hence, they are not powerful enough to distinguish between graphs modeling different dissemination processes. We introduce a framework to lift standard graph kernels and graph-based neural networks to the temporal domain to address this. We explore three different approaches and investigate the trade-offs between loss of temporal information and efficiency. Moreover, to handle large-scale graphs, we propose stochastic variants of our kernels with provable approximation guarantees. We evaluate our methods, both kernel and neural architectures, on various real-world social networks to validate our theoretical findings. Our methods beat static approaches by a large margin in terms of accuracy while still being scalable to large graphs and data sets. Moreover, we show that our framework reaches high classification accuracy in scenarios where most of the dissemination process information is incomplete.
- 1 October 2020
- Published by SAGE Publications in Big Data
- Vol. 8 (5) , 363-378
Classifying Dissemination Processes in Temporal Graphs
Many real-world graphs are temporal, for example, in a social network, persons only interact at specific points in time. This temporal information directs dissemination processes on the graph, such as the spread of rumors, fake news, or diseases. However, the current state-of-the-art methods for supervised graph classification are mainly designed for static graphs and may not capture temporal information. Hence, they are not powerful enough to distinguish between graphs modeling different dissemination processes. We introduce a framework to lift standard graph kernels and graph-based neural networks to the temporal domain to address this. We explore three different approaches and investigate the trade-offs between loss of temporal information and efficiency. Moreover, to handle large-scale graphs, we propose stochastic variants of our kernels with provable approximation guarantees. We evaluate our methods, both kernel and neural architectures, on various real-world social networks to validate our theoretical findings. Our methods beat static approaches by a large margin in terms of accuracy while still being scalable to large graphs and data sets. Moreover, we show that our framework reaches high classification accuracy in scenarios where most of the dissemination process information is incomplete.
- Open Access
On the Enumeration and Counting of Bicriteria Temporal Paths
We discuss the complexity of path enumeration and counting in weighted temporal graphs. In a weighted temporal graph, each edge has an availability time, a traversal time and some real cost. We introduce two bicriteria temporal min-cost path problems in which we are interested in the set of all efficient paths with low cost and short duration or early arrival time, respectively. However, the number of efficient paths can be exponential in the size of the input. For the case of strictly positive edge costs we are able to provide algorithms that enumerate the set of efficient paths with polynomial time delay and polynomial space. If we are only interested in the set of Pareto-optimal solutions and not in the paths themselves, then these can be determined in polynomial time if all edge costs are nonnegative. In addition, for each Pareto-optimal solution, we are able to find an efficient path in polynomial time. On the negative side, we prove that counting the number of efficient paths is #P-complete, even in the non-weighted single criterion case.
Open AccessOn the Enumeration and Counting of Bicriteria Temporal Paths
We discuss the complexity of path enumeration and counting in weighted temporal graphs. In a weighted temporal graph, each edge has an availability time, a traversal time and some real cost. We introduce two bicriteria temporal min-cost path problems in which we are interested in the set of all efficient paths with low cost and short duration or early arrival time, respectively. However, the number of efficient paths can be exponential in the size of the input. For the case of strictly positive edge costs we are able to provide algorithms that enumerate the set of efficient paths with polynomial time delay and polynomial space. If we are only interested in the set of Pareto-optimal solutions and not in the paths themselves, then these can be determined in polynomial time if all edge costs are nonnegative. In addition, for each Pareto-optimal solution, we are able to find an efficient path in polynomial time. On the negative side, we prove that counting the number of efficient paths is #P-complete, even in the non-weighted single criterion case.