LOLutz Oettershagen

Lutz Oettershagen

*This is an algorithmically generated author record based on publicly available information.

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:


Latest Publications

  • Open Access

    An Edge-Based Decomposition Framework for Temporal Networks

    by Lutz Oettershagen, Athanasios L. Konstantinidis, Giuseppe F. Italiano

  • Open Access

    Mining Temporal Networks

    by Aristides Gionis, Lutz Oettershagen, Ilie Sarpe

    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

    Finding Densest Subgraphs with Edge-Color Constraints

    by Lutz Oettershagen, Honglian Wang, Aristides Gionis

    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

    A Higher-Order Temporal H-Index for Evolving Networks

    by Lutz Oettershagen, Nils M. Kriege, Petra Mutzel

    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.


  • Inferring Tie Strength in Temporal Networks

    by Lutz Oettershagen, Athanasios L. Konstantinidis, Giuseppe F. Italiano


  • Open Access

    A Temporal Graphlet Kernel for Classifying Dissemination in Evolving Networks

    by Lutz Oettershagen, Nils M. Kriege, Claude Jordan, Petra Mutzel

    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

    Computing top-k temporal closeness in temporal networks

    by Lutz Oettershagen, Petra Mutzel

    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

    by Lutz Oettershagen, Anne Driemel, Petra Mutzel

    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.

  • Classifying Dissemination Processes in Temporal Graphs

    by Lutz Oettershagen, Nils M. Kriege, Christopher Morris, Petra Mutzel

    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

    by Petra Mutzel, Lutz Oettershagen

    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.