TempoGRAPHer: Aggregation-Based Temporal Graph Exploration

Abstract

Graphs offer a generic abstraction for modeling entities and the interactions and relationships between them. Most real-world graphs, such as social and cooperation networks, evolve over time, and exploring their evolution may reveal important information. In this paper, we present TempoGRAPHer, a system for analyzing and visualizing the evolution of temporal attributed graphs. TempoGRAPHer supports both temporal and attribute aggregation. It also allows graph exploration by identifying periods of significant growth, shrinkage, or stability. Temporal exploration is supported by two complementary strategies, namely skyline- and interaction-based exploration. Skyline-based exploration provides insights into the overall trends in the evolution, while interaction-based exploration offers a closer look at specific parts of the graph evolution history where significant changes occurred. We present experimental results demonstrating the efficiency of TempoGRAPHer. Additionally, we showcase the usefulness of our system in understanding graph evolution by presenting detailed scenarios, including exploring the evolution of a real contact network between primary school students and analyzing the collaborations in a co-authorship network between authors of the same gender over time.

1. Introduction

Graphs are ubiquitous as they provide a generic model for entities and their interactions or relationships. They are used in several real-world applications and problems. For example, graphs can successfully capture collaborations in a co-authorship network or interactions between people in a social network. Most real-world graphs change with time, and thus considering the time dimension is vital. An interesting problem in this context is studying the evolution of graphs over time and detecting important events in their history, such as time periods of significant stability, growth, or shrinkage.

When studying the evolution of a graph, we are more interested in detecting general patterns and trends in the evolution of the graph and not necessarily on updates that concern individual nodes or edges. Entities in real networks are usually described by attributes that represent characteristics of a node. We support graph aggregation, that is, grouping nodes based on their attribute values, while respecting network structure. We also support temporal aggregation, that is, aggregating graph updates in specific time intervals using appropriate temporal operators. Graph aggregation combined with temporal aggregation allows us to view graph evolution at a higher level, thus enabling us to focus on the evolution during specific time periods of the relationships between groups of nodes having attributes with specific values.

By combining graph and temporal aggregation, we may detect evolution patterns that can lead us to discover hidden associations with external factors. Conversely, if we are aware of external factors that potentially affect the evolution of the graph, we may direct our analysis to specific time periods and attributes.

As a motivating scenario, consider a face-to-face proximity network in a school, where nodes represent students and edges the physical interactions between them. We would like to study the evolution of this network to take preventive measures against the spread of infectious diseases. Detecting important events in the evolution of the network may reveal patterns that will allow us to build targeted mitigation strategies against disease spread. For such patterns to be effective, they should appear at a global level and not at the level of individual students. For example, reporting an increase in the interactions between students of different classes during breaks can be considered as a parameter affecting the spread of an infectious disease in the community. By taking advantage of such insights, we can plan appropriate strategies to reduce the risk of disease spread such as limiting the break time or having breaks at different times for each class.

As an alternative scenario, consider an academic conference interested in analyzing collaboration patterns among its attendees over multiple conference editions. Attendees are associated with attributes such as their gender, location, and research field. Suppose that the conference has adopted a policy aiming at fostering the contribution of women in research. By examining the growth of collaborations between women in the years prior to and after the adopted policy, the conference organizers can gain valuable insights to determine whether the initiative had the expected impact or further adjustments are necessary to enhance its effectiveness. Additionally, by considering the location of attendees, the conference can seek to promote collaborations between authors from specific geographical areas. This strategic approach can enhance networking opportunities and foster collaboration within targeted regions, contributing to a more diverse and interconnected academic community. Finally, the evolution of the research fields provides information into the dynamics of interdisciplinary collaboration within the conference community. This information can inform decisions related to program planning and support efforts to promote collaboration and knowledge exchange across diverse academic communities.

In this paper, we present TempoGRAPHer, a system that allows users to interactively explore the evolution of attributed graphs through time. TempoGRAPHer provides support for both temporal and graph aggregation. The interactive exploration of the graph evolution is guided by two complementary exploration strategies: skyline-based and interaction-based. Both strategies assist users in discovering important events in the evolution of the graph, where an event is defined as an interval of increased activity (shrinkage, growth), or lack thereof (stability).

Skylines are widely used in several domains to identify dominating entities in case of multi-criteria selection problems [1]. In our setting, we define skylines based on the significance of an event (i.e., number of affected graph elements) and the length of the associated interval. Skyline-based exploration provides an overview of the graph’s evolution, revealing trends associated with specific attribute values.

The interaction-based approach allows users to focus on distinctive parts of the graph’s evolution by setting a threshold on the significance of the event. This enables users to identify specific periods in the evolution where significant events occur, based on the threshold selected.

The two strategies can be applied independently or in combination. For example, by first performing skyline-based exploration, peaks in the graph evolution are found that inform users about the level of significance of the events through time. Then, by exploiting this output, users can determine an appropriate threshold value for the interaction-based approach so as to study in a more detailed level the corresponding time periods.

TempoGRAPHer builds on our theoretical models for exploring the evolution of temporal graphs [2,3]. Specifically, the theoretical formulation of the interaction-based exploration strategy was first introduced in [2], while the theoretical formulation of the skyline-based exploration was first introduced in [3]. A preliminary version of TempoGRAPHer without support for the skyline-based exploration was demonstrated in [4].

In this paper, we provide an in-depth analysis of the various components of the TempoGRAPHer system, which is extended with the skyline-based exploration strategy, and also, a detailed description of the exploration procedure that incorporates both the skyline-based and interaction-based approaches. Moreover, we propose ways of combining the two exploration approaches, allowing one strategy to leverage the results of the other to provide a more effective analysis of temporal graph evolution. Furthermore, we provide a complexity analysis of all our algorithms, as well as a series of additional experiments to evaluate their performance. Finally, we include two thorough case studies, where we showcase the applicability of our approach.

The real-world case studies include one using a proximity network between students in a primary school and another based on a collaboration network between scientists. These examples illustrate the diverse ways in which TempoGRAPHer can uncover valuable insights into the evolution of graphs.

The remainder of this paper is structured as follows. Section 2 summarizes related work. In Section 3, we introduce the necessary concepts and models that our system builds on. Section 4 provides details on the implementation of our algorithms, while Section 5 presents the TempoGRAPHer system and its functionality in detail. In Section 6, we report experimental results to evaluate the performance of our algorithms and present two case studies where we show how TempoGRAPHer highlights important aspects in the evolution of a graph. Finally, Section 7 offers conclusions and directions for future work.

2. Related Work

In the following section, we review a collection of related works, focusing specifically on research related to graph exploration, temporal graphs, skylines, and graph visualization.

• Graph exploration. Graph exploration is a generic term that can be viewed as supported by three tasks: (1) profiling and structural summarization, which refers to computing various statistical measures, e.g., [5], and providing a concise representation of the most interesting parts of the graph, for example, by extracting the schema of the graph, e.g., [6,7], or by mining frequent substructures, e.g., [8]; (2) exploratory search, which aims at helping a user that has vague information and needs to retrieve an output that is useful and relevant, often through an iterative process, for example, by searching by example, e.g., [9,10], or by exploiting query suggestion and refinement, e.g., [11,12]; and (3) exploratory analytics, which provides multi-dimensional analysis and statistical information about the graph, e.g., [13,14].

Although various approaches have been proposed for all three types of exploration, these approaches either assume static graphs or  model time as one of the node or edge features, thus offering no specific support for exploring the evolution of the graph over time. Our temporal exploration strategy based on skylines and interactions on aggregated evolution graphs provides a novel form of summarizing, analyzing, and searching the evolution of the graph.

• Temporal graphs. Regarding previous work on temporal graphs and their evolution, there is some previous research in defining temporal operators and time and attribute aggregation. T-GQL [15] is an extension of GQL with temporal operators to handle temporal paths; evolution is modeled through continuous paths. TGraph [16] uses temporal algebraic operators such as temporal selection for nodes and edges and traversal with temporal predicates on a temporal property graph. TGraph is extended with attribute and time aggregation, which allows viewing a graph in different resolutions [17], but only stability is studied. GRADOOP [18,19] introduces various extensions for supporting temporal property graphs such as temporal operators for grouping and pattern matching. The system provides different graph visualizations, i.e., the temporal graph view, the grouped graph view, and the difference graph view, which illustrates new, stable, and deleted elements between two graph snapshots. Unlike our work, which facilitates a complete exploration strategy that concerns the history of the graph, the system is driven by user queries and provides no exploration strategy.

Another approach is versioning (i.e., maintaining previous graph snapshots), which does not utilize temporal operators. In the EvOLAP graph [20], versioning is used both for attributes and graph structures to enable analytics on changing graphs. In [21], a conceptual model is presented with explicit labeling of graph elements to support analytical operations over evolving graphs, and particularly time-varying attributes, while in [22] a conceptual model is designed for capturing changes in the topology, the set of attributes, and the attribute values.

In addition to these approaches, other techniques such as stochastic actor-based models (SABMs) and parameter-evolution analysis are commonly used in analyzing temporal graphs. SABMs, as discussed by [23,24], define stochastic models for actor behaviors and interactions over time, providing insights into network dynamics, while parameter-evolution analysis, as explored by [25], tracks changes in network characteristics and tie strengths over time, shedding light on structural shifts within evolving networks.

• Skylines. In this paper, we have proposed exploration based on skylines for identifying time periods that dominate other time periods in terms of increased activity (shrinkage, growth) or lack thereof (stability). To the best of our knowledge, this is a novel application of skylines. There has been a lot of previous work on skylines. Since its introduction [26], the skyline operator has been utilized in several domains to identify dominating entities in multi-criteria selection problems [1]. Although skyline queries are very popular for multi-dimensional data, there is not much work on skylines over graphs. A domain where skylines were first used is road networks, where the best detours based on a given route [27] or the best places to visit [28] are detected using distances among other possible criteria. In [29], skylines of routes based on multiple criteria, such as distance, and cost, are also defined. The network is modeled as a multi-attribute graph and a vector of different optimization criteria is stored for each edge. In [30], the authors explore the concept of skyline path queries in the context of location-based services, where, given a pick-up point and a destination point, the system applies skyline queries based on a set of features so as to determine the most useful routes.

Besides road networks, skylines have been defined for graphs using the shortest path distances between nodes [31]. Specifically, given a set of query nodes, a node u dominates a node v if u is at least as close as v to all query points and u is closer than v to at least one query point. A different approach that does not rely on distances is defined in [32], where a skyline consists of subgraphs that best match a given user query, also represented as a subgraph. Matching relies on isomorphisms and uses appropriate encoding schemes that capture both structural and numeric features of the graph nodes. Finally, skylines on knowledge graphs are defined in [33]. The focus is on supporting skyline queries over entities in an RDF graph through SPARQL queries and the efficient evaluation of such queries, but while the data are modeled as a graph, skylines are defined on node attributes and do not take into account graph structure.

• Graph visualization. In this work, we use visualization to present the results of our skyline-based and interaction-based exploration. In general, there is a considerable amount of research related to graph visualization [34,35]. Many of these studies are specifically dedicated to temporal graphs. In the following, we position our work within the context of graph visualization taxonomies that identify time as the major distinguishing feature.

In [36], the authors provide a task taxonomy for temporal graph visualization by extending the generic Andrienko Task Framework [37], which distinguishes tasks based on data items, to include temporal graph data. Specifically, they create a design space that involves two dimensions. The first dimension includes task categories, that is, lookup, comparison, and relation seeking, and the second dimension refers to the data items that participate in the tasks, i.e., graph elements, graph subsets, time points, and time intervals. Our model aligns with the category of inverse lookup or pattern search on graph subsets and time intervals as we identify patterns occurring within parts of the graph defined using temporal operators. The authors in [38] provide a hierarchical taxonomy for dynamic graph visualizations that identifies time as the primary feature in distinguishing approaches. They assert two major categories: animation (time-to-time mapping), where dynamic graphs are represented as animated node–link diagrams, and timeline (time-to-space mapping), where visualizations correspond to static graphs based on a timeline. The methods described rely on user observation to detect evolution patterns, while our approach quantifies evolution using time and attribute aggregation, providing an automated view of the events unveiled in the graph.

There is also a substantial amount of research on graph visualization that does not explicitly focus on the temporal dimension but encompasses it or enables its integration into the discussed categories. In [39], the visualization of multilayer networks is studied, where time slices of dynamic graphs are interpreted as layers representing different temporal aspects. The authors in [40] offer a high-level categorization of faceted graph visualization and describe compositions of the graph layout with representations of the four common facets of partitions, attributes, time, and space. Our work can be regarded as a combination of graph structure, time, and attributes facets as it addresses the structural and semantic changes happening in the graph over time.

In addition, there are works that focus on different aspects within graph visualization. For example, ref. [41] tackles the issue of large graph sizes in graph visualization. To address this challenge in our work, we implement sampling, as well as aggregation, thus achieving a significant reduction in the number of nodes and edges. This strategy offers an effective and efficient visualization, ensuring graph readability. Another area of focus is addressed in [42], where an in-depth analysis of graph interpretation, summarization, and visualization (SIV) strategies employing graph-based learning methods is provided, with a particular emphasis on deep learning approaches. In our paper, we adopt a data-centric approach, performing summarization by aggregating time and attributes and interpreting evolution using skylines, providing visualization for various supported tasks.

3. The TempoGRAPHer Framework

In this section, we provide an overview of the underlying model of TempoGRAPHer that builds on the GraphTempo model [2,3].

3.1. Temporal Aggregation

We adopt an interval-based model of temporal graphs, where nodes and edges are associated with intervals of validity and each node is associated with a set of attributes.

We define a temporal attributed graph $G(V,E,\tau u,\tau e)$ in a time interval T, as a graph $G\left[T\right]$ where each node $u\in V$ and edge $e\in E$ is associated with timestamps $\tau u\left(u\right)\in T$ and $\tau e\left(e\right)\in T$, which are sets of intervals during which u and e are valid in G. For each node u and time instance $t\in \tau u\left(u\right)$, there is a n-dimensional tuple, $A(u,t)=\{A_1(u,t),A_2(u,t)\dots A_n(u,t)\}$, where $A_i(u,t)$ is the value of u at time t$\in \tau u\left(u\right)$ on the i-th attribute.

We collectively refer to graph nodes and edges as graph elements.

Our model supports both static attributes with values that remain the same through time and time-varying ones with values that may change. In the following examples, for ease of illustration, the nodes in the graphs only include static attributes. Figure 1a depicts an example of a temporal attributed graph defined in interval $T=[1,3]$. Both nodes and edges are annotated with timestamps corresponding to the time instances in T during which they are valid. Each node representing a student has two static attributes, $gender$, with values $\{f,m\}$, and $class$, with values $\{1A,1B,1C\}$. In the following, an interval that includes a single time point, e.g., $[1,1]$, is simply denoted as $\left[1\right]$.

We define a set of temporal operators, that, given a temporal attributed graph and time intervals, produces a new temporal attributed graph. First, we define union, where given a graph $G\left[T\right]$, and intervals $T_1,$ and $T_2$, the union (∪) operator $G\left[T_1\right]\cup G\left[T_2\right]$ generates a new temporal attributed graph with graph elements that appear either in $G\left[T_1\right]$ or $G\left[T_2\right]$. The intersection (∩) operator, denoted as $G\left[T_1\right]\cap G\left[T_2\right]$, where given a graph $G\left[T\right]$, and intervals $T_1,$ and $T_2$, produces a new temporal attributed graph, whose elements appear in both $G\left[T_1\right]$ and $G\left[T_2\right]$. Finally, the difference (−) operator $G\left[T_1\right]-G\left[T_2\right]$, where given a graph $G\left[T\right]$, and intervals $T_1,$ and $T_2$, outputs a temporal attributed graph that includes graph elements that appear in $G\left[T_1\right]$ but not in $G\left[T_2\right]$.

Given the temporal attributed graph in Figure 1a and time intervals $T_1=\left[1\right]$ and $T_2=\left[2\right]$, Figure 1b presents the union graph $G\left[1\right]\cup G\left[2\right]$, Figure 1c the intersection graph $G\left[1\right]\cap G\left[2\right]$, and Figure 1d the difference graph $G\left[1\right]-G\left[2\right]$.

3.2. Graph Evolution and Aggregation

We want to study the evolution of a graph between two consequent intervals $T_1$ and $T_2$ so as to capture important events. Specifically, we want to determine whether graph elements remained stable in both intervals (called the stability event), new graph elements appeared in the most recent interval (called the growth event), or existing graph elements disappeared in the most recent one (called the shrinkage event).

To model graph evolution with respect to these three types of events, we exploit the temporal operators to define the following three event graphs. For two time intervals $T_1$, $T_2$ where $T_2$ follows $T_1$: (a) the stability graph (s-graph), $G_s\left[(T_2,T_1)\right]$, is defined as $G\left[T_1\right]\cap G\left[T_2\right]$ and captures graph elements that appear in both $T_1$ and $T_2$, (b) the shrinkage graph (h-graph), $G_h\left[(T_2,T_1)\right]$, is defined as $G\left[T_1\right]-G\left[T_2\right]$ and captures elements that disappear from $T_1$ to $T_2$ and (c) the growth graph (g-graph), $G_g\left[(T_2,T_1)\right]$, is defined as $G\left[T_2\right]-G\left[T_1\right]$ and captures graph elements that are new to $T_2$. We use $\gamma$ to denote any of the three events.

Besides studying graph evolution at the individual node and edge level, we want to study the evolution of a graph at a higher granularity level. For example, instead of studying stable interactions between individuals, we also want to study stable interactions between individuals of the same gender or class. To this end, we use graph aggregation, where nodes are grouped based on one or more of their attribute values while respecting network structure.

Given a graph $G\left[T\right]$ and a subset C of its n attributes, the graph aggregated by C in T is a weighted graph $G[T,C]$, where there is a node $u^{\prime }$ in $G[T,C]$ for each value combination of the C attributes and the weight of $u^{\prime }$, $w\left(u^{\prime }\right)$ is equal to the number of distinct nodes u in $G\left[T\right]$ that have the specific attribute value combination. There is an edge $e^{\prime }$ between two nodes $u^{\prime }$ and $v^{\prime }$ in $G[T,C]$, if there is an edge between the corresponding nodes in $G\left[T\right]$ and its weight $w\left(e^{\prime }\right)$ is equal to the number of such edges. Figure 2a shows the graph aggregated by gender in time instance 3, $G\left[\right[3],\{gender\left\}\right]$, of the graph in Figure 1a. There are two nodes that represent male and female authors, with values m, f. The weight of the male nodes is 3 and denotes the number of nodes of the graph in time instance 3 with the attribute male. Similarly, female nodes have weight equal to 1, corresponding to the number of nodes with the attribute female for the graph in time instance 3. There is one edge between male nodes with weight 2 and one edge between male and female nodes with weight 2 that represent the number of collaborations between nodes having corresponding attributes.

We provide two types of aggregation: distinct aggregation, where the weight of an aggregate node in $G[T,C]$ counts the distinct nodes in $G\left[T\right]$ that have the corresponding attribute value combination, and non-distinct aggregation, where each appearance of an attribute value combination is counted in the weight each time it appears either on the same or on different nodes.

Aggregation is also applied to event graphs. For example, Figure 2b–d shows the aggregated event graphs for the evolution of the graph of Figure 1a from time instance 2 to 3 when distinct aggregation by gender is applied.

To evaluate the significance of an event, we measure the number of affected graph elements. We focus on events regarding edges. Let c and $c^{\prime }$ be two attribute value combinations for the attributes C selected for the aggregation. For an event $\gamma$, we use $count(G_{\gamma }[(T_2,T_1),C],c,c^{\prime })$ to denote the number of edges from nodes labeled with c to nodes labeled with $c^{\prime }$ in the aggregated $\gamma$-graph $G_{\gamma }[(T_2,T_1),C]$, which is equal to the weight of such edges. For example, in Figure 2c, with respect to the growth event, $count(G_g[(\left[3\right],\left[2\right]),\left\{gender\right\}],f,m)=2$ measures the number of new edges between female and male nodes that appear in $G\left[3\right]$ with respect to $G\left[2\right]$.

3.3. Graph Exploration

We are interested in identifying time points in the history of the graph where the count of events is high, indicating interesting points in the evolution of the graph. Concretely, we want to determine time points, termed reference points, $t_r$, where the stability, shrinkage or growth counts, $count(G_{\gamma }[(t_r,T_r),C],c,c^{\prime })$, are high with respect to an immediate preceding interval $T_r$.

To locate such points, for each reference point $t_r$, we perform our search as follows. We initialize $T_r$ to be the time point immediately preceding $t_r$, and then we gradually extend $T_r$ to the past. We extend $T_r$ employing two types of semantics: (a) intersection-inspired strict (∩) semantics, where we want a graph element to appear in all time instances of the extended interval, and (b) union-inspired loose (∪) semantics, where we want a graph element to appear in at least one time instance in the extended interval. The strict semantics model includes persistent occurrences of graph elements, while loose semantics also includes transient changes.

In case of steep changes, such as growth or shrinkage, we are interested in finding the shortest interval $T_r$ with a high event count. In contrast, for stability, we are interested in the longest interval $T_r$ with a high event count so that we capture the longest period that the elements existed. Thus, we define minimal and maximal properties.

Given $G_{\gamma }[(t_r,T_r),C]$ and attribute value combinations c and $c^{\prime }$, we say that $T_r$ is: (i) minimal if ∄$T_r^{\prime }$ such that $T_r^{\prime }\subset T_r$ and $count(G_{\gamma }[(t_r,T_r^{\prime }),C],c,c^{\prime })\ge count(G_{\gamma }[(t_r,T_r),C],c,$$c^{\prime })$, and (ii) maximal if ∄$T_r^{\prime }$ such that $T_r\subset T_r^{\prime }$ and $count(G_{\gamma }[(t_r,T_r^{\prime }),C],c,c^{\prime })$ $\ge count(G_{\gamma }\left[\right(t_r,$$T_r\left)C\right],c,c^{\prime })$.

We say that a count for an event $\gamma$ is increasing if for any $T_r\subseteq T_r^{\prime }$, $count(G_{\gamma }[(t_r,T_r^{\prime }),C],c,$$c^{\prime })$≥$count(G_{\gamma }[(t_r,T_r),C],c,c^{\prime })$, for any set of attributes C, and any combination of attributes values c and $c^{\prime }$. Similarly, we define a decreasing count for an event $\gamma$ if for any $T_r\subseteq T_r^{\prime }$, $count(G_{\gamma }[(t_r,T_r^{\prime }),C],c,c^{\prime })$≤$count(G_{\gamma }[(t_r,T_r),C],c,c^{\prime })$, for any set of attributes C, and any combination of attributes values c and $c^{\prime }$.

For increasing counts, we are interested in minimal intervals, while for decreasing counts in maximal ones.

Next, we introduce two types of exploration, skyline-based and interaction-based.

3.3.1. Skyline-Based Exploration

Skylines are often used in multi-criteria optimization problems to retrieve the items that have the best value in at least one of the criteria, and  are not worse in the other criteria [33,43,44,45]. In particular, for multidimensional data, we say that an item x dominates another item $x^{\prime }$ if x is as good as $x^{\prime }$ in all dimensions and x is better that $x^{\prime }$ in at least one dimension. A skyline query returns all non-dominated items in a dataset.

We define two criteria to evaluate the interestingness of an event $\gamma$ in an aggregated graph $G_{\gamma }[(t_r,T_r),C]$ with respect to attribute value combinations c and $c^{\prime }$ of C: (1) the length $l_{T_r}$ of interval $T_r$ defined as the number of time instances in $T_r$ and (2) the event count, i.e., $count(G_{\gamma }[(t_r,T_r),C],c,c^{\prime })$.

Given an event $\gamma$, a graph $G[T,C]$ and pair of attribute values, c and $c^{\prime }$ of C, the evolution skyline is defined as the set of all non-dominated tuples $(t_r,T_r,w)$ where $t_r$∈T, $T_r$⊂T and w = $count(G_{\gamma }[(t_r,T_r),C]$, $c,c^{\prime })$.

For the case of an increasing count, we say that a tuple $(t_r,T_r,w)$ dominates a tuple $(t_r^{\prime },T_r^{\prime },w^{\prime })$, if it holds $(l_{T_r}<l_{T_r^{\prime }})$ and $(w\ge w^{\prime })$, or $(l_{T_r}\le l_{T_r^{\prime }})$ and $(w>w^{\prime })$. Respectively, for decreasing counts, we say that a tuple $(t_r,T_r,w)$ dominates a tuple $(t_r^{\prime },T_r^{\prime },w^{\prime })$, if it holds $(l_{T_r}>l_{T_r^{\prime }})$ and $(w\ge w^{\prime })$, or $(l_{T_r}\ge l_{T_r^{\prime }})$ and $(w>w^{\prime })$.

Skylines may include numerous results, especially in the case of graphs evolving over long periods of time. To address the potentially large size of the evolution skyline, we define the domination degree of a tuple $(t_r,T_r,w)$, $dod(t_r,T_r,w)$ to be the number of other tuples that this tuple dominates. We rank the $(t_r,T_r,w)$ tuples in the evolution skyline according to their domination degree and return only the top-k ones.

3.3.2. Interaction-Based Exploration

Skyline-based exploration provides a general overview of the evolution of the graph, which can help us identify trends in the evolution of the graph. When we need to focus on specific parts of the graph where at least a given number of changes have occurred, we employ the interaction-based exploration. In the interaction-based approach, we adopt a threshold-based technique and search for intervals where at least $\theta$ events occurred in terms of interactions; i.e., at least $\theta$ edges were stable, added or removed. The value of $\theta$ is a user-defined parameter.

In exploring the graph, given an event $\gamma$, a graph $G[T,C]$, a pair of attribute values, c and $c^{\prime }$ of C, and a threshold $\theta$, we are looking to identify pairs ($t_r,T_r$) where $t_r$ is the reference point and $T_r$ an interval preceding $t_r$ such that it holds: $count(G_{\gamma }[(t_r,T_r),C]$, $c,c^{\prime })$ ≥ $\theta$. Again, for increasing counts, we are interested in the minimal $T_r$, while for decreasing ones, we are interested in the maximal $T_r$.

For simplicity, in the rest of the paper we denote the event count as $count(G_{\gamma }[T_r,C],c,c^{\prime })$ identifying $t_r$ as the point in time next to the end point of $T_r$.

• Initialization of $\theta$. Our framework provides an interactive exploration strategy that enables users to adjust $\theta$ based on the output they receive for different values of $\theta$. We also offer a default strategy to establish an appropriate $\theta$. To this end, we leverage the skyline-based exploration strategy.

Specifically, to compute $\theta$ for an event $\gamma$, a graph $G[T,C]$, and pair of attribute values, c and $c^{\prime }$ of C, we first compute the corresponding skyline, R. Then, we obtain the minimum and the maximum values of the counts from the tuples in R and set $\theta$ equal to the average of these values. The rationale is that for an event to be considered interesting, it must have a count that is at the least equal to the estimated average. Subsequently, users can interactively fine-tune this value and find an appropriate $\theta$.

More formally, the estimated value of $\theta$ is formulated as follows:

$${\theta }_{est}={\displaystyle \frac{\underset{(t_r,T_r,w)\in R}{min}w+\underset{(t_r,T_r,w)\in R}{max}w}{2}}$$

4. Implementation

In this section, we present information about the implementation of our framework. First, we describe the basic data structures, then the algorithms for temporal and graph aggregation, and finally, the algorithms for graph evolution. Further details are provided in [2,3].

4.1. Data Structures

To store a temporal attributed graph $G\left[T\right]$, we maintain separate structures, V for the nodes in V, $\mathbf{E}$ for the edges in E, $\mathbf{S}$ for the static attributes S in A, and ${\mathbf{A}}_{\mathbf{i}}$ for the i-th time-varying attribute in A. Structure $\mathbf{V}$ is a labeled array with $\left|V\right|$ rows and $\left|T\right|$ columns, where each row is labeled with a node id, $v\in V$, and each column with a time point $t\in T$. $\mathbf{V}[v,t]$, is equal to 1 if v appears at t, and 0 otherwise. A similar structure is employed for the edges, where $\mathbf{E}$ has $\left|E\right|$ rows and $\left|T\right|$ columns. Each row is labeled with a pair of node ids corresponding to the edge end points and each column with time point $t\in T$.

Since static attributes remain constant over time, we maintain a dedicated structure, $\mathbf{S}$, that retains information for all available attributes without considering the dimension of time. This approach enhances the efficiency of our algorithms. $\mathbf{S}$ is a labeled array with $\left|V\right|$ rows labeled with the node id, and $\left|S\right|$ columns labeled by the corresponding attribute name $S_i\in S$. $\mathbf{V}[v,S_i]$ corresponds to the value of $S_i$ for v. For the i-th time-varying attribute, we maintain a labeled array ${\mathbf{A}}_{\mathbf{i}}$. Rows are labeled with node ids, and columns with the time point $t\in T$, and ${\mathbf{A}}_{\mathbf{i}}[v,t]$ is equal to the value of attribute $A_i$ of v at time point t.

4.2. Temporal Operators and Aggregation

• Temporal operators. We provide different algorithms for the union, intersection, and difference operators. We present here in detail the algorithm for intersection; the algorithms for union and difference are similar. Given a temporal attributed graph $G\left[T\right]$ and a pair of intervals $T_1,T_2$, the algorithm ensures that only nodes and edges that appear in every time point of $T_1,T_2$ are included in the resulting graph. The output graph corresponds to a temporal attributed graph.

As depicted in Algorithm 1, the algorithm takes as input graph $G\left[T\right]$, represented by the labeled arrays $\mathbf{V},\mathbf{E},\mathbf{S}, set\left({\mathbf{A}}_{\mathbf{i}}\right)$, and intervals $T_1,T_2$, and outputs labeled arrays ${\mathbf{V}}^{\prime },{\mathbf{E}}^{\prime },{\mathbf{S}}^{\prime },$ $set\left({\mathbf{A}}_{\mathbf{i}}^{\prime }\right)$, that maintain the information for the intersection graph. We initialize ${\mathbf{V}}^{\prime },{\mathbf{E}}^{\prime }, set\left({\mathbf{A}}_{\mathbf{i}}^{\prime }\right)$ as empty arrays with one column for each t in $T_1$ and $T_2$, and ${\mathbf{S}}^{\prime }$ as an empty array with one column for each static attribute (line 1). Next, we restrict the input graph $G\left[T\right]$, by filtering arrays $\mathbf{V},\mathbf{E},set\left({\mathbf{A}}_{\mathbf{i}}\right)$ to include only the columns associated to the given set of intervals $T_1,T_2$ (line 2). For each node $v\in V$, the corresponding row, $\mathbf{V}[v,:]$, is accessed and if all values in the $\mathbf{V}[v,:]$ are equal to 1 ($\mathbf{V}[v,t]=1,\forall t\in (T_1,T_2)$), $\mathbf{V}[v,:]$ is inserted into ${\mathbf{V}}^{\prime }$. The corresponding entries for the attributes of v are also updated. That is, the row corresponding to v in $\mathbf{S}$, $\mathbf{S}[v,:]$, and for time-varying attribute i the corresponding rows from arrays ${\mathbf{A}}_{\mathbf{i}}$, ${\mathbf{A}}_{\mathbf{i}}[v,:]$, are retrieved and copied in ${\mathbf{S}}^{\prime }$ and ${\mathbf{A}}_{\mathbf{i}}^{\prime }$ respectively (lines 3–7). Similarly, for each edge $e\in E$ the corresponding row $\mathbf{E}[e,:]$ is accessed, and if all values $\mathbf{E}[e,:]$ are equal to 1, $\mathbf{E}[e,:]$ is inserted into ${\mathbf{E}}^{\prime }$ (lines 8–10).

Algorithm 1 Temporal operator (intersection)

Input: $G\left[T\right]$ represented by $\mathbf{V},\mathbf{E},\mathbf{S},set\left({\mathbf{A}}_{\mathbf{i}}\right)$, intervals $T_1,T_2$  Output: Intersection graph $G^{\prime }=G\left[T_1\right]\cap G\left[T_2\right]$ 1: Initialize ${\mathbf{V}}^{\prime },{\mathbf{E}}^{\prime },set\left({\mathbf{A}}_{\mathbf{i}}^{\prime }\right)$ in $(T_1,T_2)$, and ${\mathbf{S}}^{\prime }$ 2: Restrict $\mathbf{V},\mathbf{E},set\left({\mathbf{A}}_{\mathbf{i}}\right)$ in $(T_1,T_2)$ 3: for each node v do 4:       if $\mathbf{V}[v,t]=1$ $\forall t$ then          ▹$t\in (T_1,T_2)$ 5:             ${\mathbf{V}}^{\prime }\leftarrow \mathbf{V}[v,:]$ 6:             ${\mathbf{S}}^{\prime }\leftarrow \mathbf{S}[v,:]$ 7:             ${\mathbf{A}}_{\mathbf{i}}^{\prime }\leftarrow {\mathbf{A}}_{\mathbf{i}}[v,:]$          ▹$\forall i$ attribute of v 8: for each edge e do 9:       if $\mathbf{E}[e,t]=1$ $\forall t$ then          ▹$t\in (T_1,T_2)$ 10:           ${\mathbf{E}}^{\prime }\leftarrow \mathbf{E}[e,:]$ 11: return  ${\mathbf{V}}^{\prime },{\mathbf{E}}^{\prime },{\mathbf{S}}^{\prime },set\left({\mathbf{A}}_{\mathbf{i}}^{\prime }\right)$

• Aggregation. Algorithm 2 presents distinct aggregation for static attributes. The algorithm takes as input a temporal attributed graph $G\left[T\right]$ represented by $\mathbf{V},\mathbf{E},\mathbf{S}$, and the set C of the aggregation attributes, and outputs the labeled vectors ${\mathbf{V}}^{\prime },{\mathbf{E}}^{\prime }$ representing the aggregated graph $G[T,C]$. First, we initialize ${\mathbf{V}}^{\prime },{\mathbf{E}}^{\prime }$ as empty arrays (line 1). For each attribute $S_i$ in C the corresponding column $\mathbf{S}[:,S_i]$, holding the values of $S_i$ for each node in $\mathbf{V}$, is accessed and inserted in ${\mathbf{V}}^{\prime }$. Next, columns in ${\mathbf{V}}^{\prime }$ are merged (lines 2–4). Therefore, ${\mathbf{V}}^{\prime }$ corresponds to a vector, where for each node v, the value ${\mathbf{V}}^{\prime }\left[v\right]$ corresponds to the combined attribute values of v. To build ${\mathbf{E}}^{\prime }$, we traverse $\mathbf{E}$ and for each edge $(u,v)$, we lookup the edge endpoints u and v in ${\mathbf{V}}^{\prime }$ to retrieve their values in attributes C. Each value pair is inserted into ${\mathbf{E}}^{\prime }$ (lines 5–8). Next, we group rows in ${\mathbf{V}}^{\prime }$ and ${\mathbf{E}}^{\prime }$ based on their values. We set these values as the group (i.e., produced row) labels, and we count their appearances to calculate the corresponding weights (lines 9–10). The algorithm returns ${\mathbf{V}}^{\prime }$ vector labeled with attribute value(s) that maintains the weight of the aggregated nodes and ${\mathbf{E}}^{\prime }$ labeled with pairs of attribute values that maintain the weight of the aggregated edges (line 11).

Algorithm 2 Aggregation (static attributes)

Input: $G\left[T\right]$ represented by $\mathbf{V},\mathbf{E},\mathbf{S}$, attributes set C  Output: Aggregate graph $G[T,C]$ represented by ${\mathbf{V}}^{\prime },{\mathbf{E}}^{\prime }$ 1: Initialize ${\mathbf{V}}^{\prime },{\mathbf{E}}^{\prime }$ 2: for each $S_i\in C$ do 3:       ${\mathbf{V}}^{\prime }\leftarrow \mathbf{S}[:,S_i]$ 4: Merge columns in ${\mathbf{V}}^{\prime }$ 5: for each $(u,v)\in E$ do 6:       $c\leftarrow$ lookup u in ${\mathbf{V}}^{\prime }$ 7:       $c^{\prime }\leftarrow$ lookup v in ${\mathbf{V}}^{\prime }$ 8:       $E^{\prime }\left[(u,v)\right]\leftarrow (c,c^{\prime })$ 9: ${\mathbf{V}}^{\prime }.Groupby\left(c\right).Count\left(weight\right)$ 10: ${\mathbf{E}}^{\prime }.Groupby\left((c,c^{\prime })\right).Count\left(weight\right)$ 11: return  ${\mathbf{V}}^{\prime },{\mathbf{E}}^{\prime }$

We also support non-distinct aggregation. In this case, instead of iterating in line 2 for each attribute, we iterate for each node and attribute so as to account for multiple node and edge appearances. To improve efficiency, static and time-varying attributes are treated differently. The algorithm for time-varying attributes follows a similar structure, but it is more involved.

4.3. Graph Exploration

We now present the algorithms for the skyline-based and the interaction-based exploration. Both algorithms use the data structures and algorithms for temporal operators and aggregation presented in the previous section. However, for notation simplicity, here we use a simplified graph representation.

• Skyline-based exploration. The algorithm takes as input an event $\gamma$, a temporal attributed graph $G\left[T\right]$, attribute(s) C, and attribute value combinations $c,c^{\prime }$ of C, and outputs the tuples that belong in the skyline, stored in R based on the length of the detected interval, along with their domination degree stored in D. In Algorithm 3, we present in detail the skyline-based computation process for the event of stability ∩.

We consider all reference points in T, denoted as $t_r$, and initially pair each of them with its corresponding past interval $T_r$ of maximum length. For each such $(t_r,T_r)$ pair, first we create the intersection graph and then we compute the aggregation for the requested C. Next, for the given values $c,c^{\prime }$, we retrieve the weight of the corresponding edges in the aggregate graph and form the corresponding tuple $p=(t_r,T_r,w_p)$ (lines 2–8). Each such tuple is then compared against the tuples already in the skyline to determine whether it should be added or not to R. To avoid redundant comparisons, we discern cases based on the length of the compared tuples. For each tuple $q=(t_r^{\prime },T_r^{\prime },w_q)$ in R with $l_{T_r}\le l_{T_r^{\prime }}$, we check the dominance relationship between p and q, by comparing both the intervals length $l_{T_r},l_{T_r^{\prime }}$ and the corresponding weights $w_p$ and $w_q$. If p dominates q, p replaces q in R and D is correspondingly updated with p’s domination degree. If q dominates p, then p is discarded and q’s domination degree is updated. Finally, if there is a tie, p is also inserted in R. For each tuple q with $l_{T_r}>l_{T_r^{\prime }}$, we only need to check if $w_p$ is at least equal to $w_q$. If this condition is met, q is dominated by p. Otherwise, a tie exists. Subsequently, R and D are updated accordingly (lines 9–23). At the end of this procedure, we reduce the inspected interval $T_r$ and update its length (lines 24–25) and repeat the described procedure for the new $T_r$ (and the same reference point). The procedure terminates when all reference points are considered against all corresponding past intervals.

Depending on the event’s counts, we adopt a different approach for selecting the initial interval for each reference point in our exploration so as to reduce comparisons and replacements in the skyline tuples. Thus, when considering events with decreasing counts, such as stability with strict semantics as presented here or growth with loose semantics, our algorithm begins with the $T_r$ with the greatest length and gradually reduces it. Respectively, for events with increasing counts, such as shrinkage with loose semantics, we search for minimal intervals, and thus we start our exploration with the $T_r$ with the smallest length and we gradually increase it.

Algorithm 3 Skyline-based exploration (stability (∩))

Input: $G\left[T\right]$, attribute(s) C, attribute values $c,c^{\prime }$  Output: Skyline set represented by R, dominance set represented by D 1: Initialize $R,D$  ▹$R:l_{T_r}\to set\left((t_r,T_r,w)\right),D:(t_r,T_r,w)\to \left|d\right|,d$: dominated tuples 2: for each reference point $t_r$ do 3:       $T_r=$ longest interval for $t_r$ 4:       while $l_{T_r}\ge 1$ do 5:            Compute intersection for $G\left[T\right]$ on $(t_r,T_r)$ (Algorithm 1) 6:            Compute aggregation on C (Algorithm 2) 7:            Get count $w_p$ for $c,c^{\prime }$ 8:            Current tuple $p=(t_r,T_r,w_p)$ 9:            for each tuple $q=(t_r^{\prime },T_r^{\prime },w_q)\in R$ do 10:                if $l_{T_r}\le l_{T_r^{\prime }}$ then 11:                    if $w_p>w_q$ and $l_{T_r}=l_{T_r^{\prime }}$ then   ▹p dominates q 12:                        Remove q from R 13:                        Insert p in R 14:                        Update $D\left[p\right]$ 15:                      else if $w_p<w_q$ then      ▹q dominates p 16:                        Update $D\left[q\right]$ 17:                      else                  ▹ tie 18:                        Insert p in R 19:                else if $l_{T_r}>l_{T_r^{\prime }}$ then 20:                      if $w_p\ge w_q$ then        ▹p dominates q 21:                        Execute lines 12–14 22:                      else                  ▹ tie 23:                        Execute line 18 24:            Reduce $T_r$ 25:            $l_{T_r}--$ 26: return  $R,D$

• Interaction-based exploration. The algorithm takes as input an event $\gamma$, a temporal attributed graph $G\left[T\right]$, attribute(s) C, attribute value combinations $c,c^{\prime }$ of C, and threshold $\theta$ and outputs a set Z with tuples corresponding to maximal or minimal intervals where at least $\theta$ events occur. We present the implementation of the interaction-based exploration for the event of stability (∩) as depicted in Algorithm 4. As stability has decreasing counts, the algorithm finds maximal intervals. In contrast to skyline-based exploration, here we consider first all reference points $t_r$, along with their corresponding shortest past interval $T_r$. We then, similarly to Algorithm 3, build the current tuple p (lines 2–9). Next, we check whether $w_p\ge \theta$, and if so, p is inserted in Z and $T_r$ is extended. If $w_p<\theta$, $t_r$ does not need to be considered with any other intervals and it is pruned. This is because the event counts are decreasing and therefore, extending $T_r$ will not increase the count of interest (lines 10–14). The process ends after examining all reference points.

For an event with increasing counts, we search for minimal intervals and begin with intervals of the greatest length and then reduce them gradually.

• Complexity. We now analyze the complexity of our algorithms. Specifically, for Algorithm 1, which constructs the stability (intersection) graph, complexity depends on the number of nodes, edges, attributes, and length $\tau$ of interval $(T_1,T_2)$. Thus, the cost of constructing the stability graph is $O\left(\right|V|\times |A|\times \tau +|V|\times |S|+|E|\times \tau )$, where the first two terms account for the processing of time-varying and static node attributes, respectively. Complexity for constructing the other event graphs is similar to that of stability.

Concerning Algorithm 2, which presents aggregation on static attributes, complexity depends on the number of nodes, attributes, edges, and merging, lookup, and group-by operations. The cost of merging is $O\left(V\right)$, the cost of each lookup $O\left(1\right)$, and the cost of group-by $O\left(\right|V|+|E\left|\right))$. Thus, the factor that dominates the construction of the aggregate graph is the processing of the node attributes, which amounts to $O\left(\right|V|\times |C|+|E\left|\right))$.

Algorithm 4 Interaction-based exploration (stability (∩))

Input: $G\left[T\right]$, attribute(s) C, attribute values $c,c^{\prime }$, threshold $\theta$  Output: Result set Z 1: Initialize Z 2: for each reference point $t_r$ do 3:       $T_r=$ shortest interval for $t_r$ 4:       $repeat=True$ 5:       while $repeat=True$ do 6:           Compute intersection for $G\left[T\right]$ on $(t_r,T_r)$ (Algorithm 1) 7:           Compute aggregation on C (Algorithm 2) 8:           Get count $w_p$ for $c,c^{\prime }$ 9:           Current tuple $p=(t_r,T_r,w_p)$ 10:           if $w_p\ge \theta$ then 11:                $Z\leftarrow p$ 12:                Extend $T_r$ 13:           else 14:                $repeat=False$ 15: return  Z

For the skyline-based exploration algorithm, Algorithm 3, we denote the length of interval T as $\tau$. For each reference point within the interval, we consider all immediately preceding intervals. Hence, for each of the $\tau$ reference points, we examine $\tau -1$ past intervals. The total number of pairwise intervals, and thus the number of graphs defined on them, is then $O\left({\tau }^2\right)$, since for each of the $\tau$ reference points, the algorithm considers $\tau -1$ intervals. We have already discussed the cost of constructing the stability (or any other event) and aggregate graphs. Each of the ${\tau }^2$ graphs produces one candidate skyline tuple that we need to check against all existing tuples in the skyline set R. Thus, each pair of intervals leads to an update of the skyline set R by at most one tuple at a time. Therefore, the complexity for skyline computation, excluding, for simplicity, the cost of constructing the graphs, is $O({\tau }^2\times |R\left|\right)$.

For the interaction-based exploration algorithm, Algorithm 4, the overall complexity is dominated by the number of reference points $\tau$ and the number of interval extensions. Each reference point may require up to $\tau -1$ interval extensions in the worst case (when the threshold is always met and no pruning is performed), resulting in a total of $O\left({\tau }^2\right)$ constructed stability and aggregate graphs and corresponding result tuples that are compared against the threshold. Thus, the overall complexity is $O\left({\tau }^2\right)$, where the complexity for stability and aggregate graph construction is omitted.

5. The TempoGRAPHer System

TempoGRAPHer supports three main functionalities: (1) an overview of the temporal graph at specific time points, (2) aggregation of the temporal graph on one or more of its attributes and at various time granularities, and (3) exploration of the history of the temporal graph for identifying intervals of significant changes with both skyline-based and interaction-based approaches.

The overall architecture of the TempoGRAPHer system is depicted in Figure 3. The system comprises three basic components that implement its three main functionalities, overview, aggregation, and exploration.

Next, we describe in detail each of the main components and the functionality they provide. To this end, we will use as case study the Primary School dataset [46,47], which is a contact network describing the face-to-face proximity of 232 students and 10 teachers in a primary school in Lyon, France. Each interaction denotes a 20-second contact between two individuals. Each individual has two static attributes, gender, and class. The school has five grades, 1 to 5, with two classes each (i.e., 1A, 1B, 2A, 2B, etc.), plus teachers, and three values for the gender attribute, female, male, and unspecified. Our dataset covers a period of 17 h.

Table 1. Primary School graph.

	1	2	3	4	5	6
Nodes	228	231	233	220	118	217
Edges	857	2124	1765	1890	1253	1560
Density	0.0331	0.0800	0.0653	0.0785	0.1815	0.0666
	7	8	9	10	11	12
Nodes	215	232	238	235	235	236
Edges	1051	1971	1170	1230	2039	1556
Density	0.0457	0.0736	0.0415	0.0447	0.0742	0.0561
	13	14	15	16	17
Nodes	147	119	211	175	187
Edges	1654	1336	1457	1065	1767
Density	0.1541	0.1903	0.0658	0.0700	0.1016

shows the total number of nodes and edges and the density for each time point for the graph of Primary School.

• Graph Overview. The main input for all system components is a temporal attributed graph. The overview component, as its name indicates, provides a general overview of the given graph by illustrating at specific time points the maximum connected component of the graph colored based on a selected attribute. This allows the user to derive insights on the distribution of this attribute among the nodes of the graph at the selected time point. If the original graph is too large to display (more than 100 nodes), graph sampling is first applied utilizing the Snowball sampler [48].

First, the system enables users to load their own graph or choose among existing graphs that are preloaded in the system, such as Primary School. Then, the user selects the preferred time point and a single attribute, and in the graph displayed, each node is assigned a color based on the value of the selected attribute. By hovering the mouse over a node, the user can be informed about the id of the node. Figure 4 depicts the graph overview for Primary School for the first time point. Nodes are colored based on the class attribute. The system also provides some general statistics, showing the number of nodes in the graph and the number of distinct values of the attribute at the given time point.

• Graph Aggregation. TempoGRAPHer facilitates the aggregation of the original graph on both the time and the attribute dimensions. As illustrated in Figure 3, given a time interval and a temporal operator (i.e., project, union, intersection, difference, or evolution), first temporal aggregation is performed. The derived graph is then aggregated based on a set of specified attributes either using distinct or non-distinct aggregation, and the produced weighted graph is then visualized.

The system interface allows the user to select all required parameters, that is, the preferred time period of interest, the temporal operator of interest, the type of aggregation, distinct/non-distinct, and the set of attributes based on which graph aggregation is performed. For example, Figure 5 shows the distinct aggregation of the gender and class attributes on the intersection graph for intervals [1, 2] and [3, 4]. Each attribute value combination is colored using a different color and the weights of both nodes and edges are displayed. Furthermore, the attribute value combination of each node is shown by hovering over the node.

• Graph Exploration. The third functionality of TempoGRAPHer is exploration, which enables users to visually discover parts of the graph where significant events have occurred. TempoGRAPHer explores stability using strict semantics, and growth and shrinkage utilizing loose semantics.

The exploration component provides the two exploration strategies, both skyline- and interaction-based exploration. For both exploration strategies, all pairs of reference point and interval need to be considered iteratively. Thus, given an event type, i.e., stability, growth, or shrinkage, at each iteration, i.e, for the current reference point and interval pair, the corresponding event graph is first constructed. Then, the event graph is aggregated based on a set of selected attributes. The event counts are then derived from the aggregate event graph for the specified values of the selected attributes. The output of this procedure is a tuple consisting of an interval, a reference point, and the computed count. These three steps are repeated for all pairs of reference point and interval as we mentioned above and each derived tuple is sequentially forwarded according to the strategy used to the corresponding subcomponent as shown in Figure 3.

In particular, for skyline-based exploration, the system computes the skyline result by checking if each derived tuple is dominated by any other or whether it should be added in the skyline. The output depicts the most important pairs of intervals for the specified event considering the length of the interval and the number of interactions for the requested attribute values. The user can visualize the output in two formats, a 3D plot and a 2D plot. In the 3D plot, the x-axis represents the past interval, the y-axis depicts the reference point, and the z-axis displays the counts. Additionally, the plot depicts the top three results, which are colored in blue. The 2D plot offers a distinct representation for each reference point. The x-axis represents the past interval and the y-axis displays the counts.

If the interaction-based exploration is selected, the system compares the count of each derived tuple against the specified threshold $\theta$ and eliminates all tuples that do not satisfy the given constraint. Pruning is applied to make the procedure more efficient. The output is then visualized as a plot, illustrating for each reference point all maximal or minimal interval pairs, depending on the type of the event.

Figure 6 shows the visualization of the results for the skyline-based exploration for stability of interactions among female students. The user specifies the event of interest, stability in this example; the attributes for graph aggregation; gender; and the specific attribute value combination, i.e., F-F edges. The skyline includes long periods of stability and periods of high stability. Pair ([12], [11]) represents the most important result considering the number of interactions, while pair ([17], [2, 16]) is the most important result from the interval length perspective. Figure 6a depicts the 3D visualization of the skyline. The bars colored with blue depict the top three derived results according to the domination degree. Figure 6b depicts the 2D visualization for the same settings. The results for each reference point are represented individually. By hovering over a line, the corresponding count appears.

Similarly, Figure 7 depicts the visualization results for stability among female student interactions using interaction-based exploration. In addition to the parameters specified for skyline-based exploration, the user also specifies the threshold value $\theta$ equal to 30 in the presented example. The result includes all maximal intervals where at least $\theta =30$ stable interactions have persisted between girls (F-F edges). The highest stability is observed for reference point 12 with the maximal interval pair being ([12], [7, 11]).

6. Evaluation

For our experiments, besides Primary School (described in Section 5), we use two additional real-world datasets, namely DBLP, and MovieLens.

DBLP is a collaboration network extracted from DBLP [49]. The dataset covers a period of 21 years from 2000 to 2020, where each year denotes a time point. There is an edge when two authors co-author a paper. There are two attributes for the authors, one static, gender with two values, and one time-varying, #publications per year with three categorical values (low, average, high). Gender is determined utilizing an appropriate tool [50].

MovieLens is a movie ratings dataset that builds on the benchmark MovieLens [51]. The dataset covers a period of 6 months from 1 May to 31 October 2000, and each month represents a time point. There is an edge between two users when they have both rated the same movie. Each user has three static attributes, gender with 2 values, age with 7 categorical values, occupation with 21 values, and one time-varying, average rating of the user per month with 38 values.

Table 2. DBLP graph.

	2000	2001	2002	2003	2004	2005	2006
Nodes	1708	2165	1761	2827	3278	4466	4730
Edges	2036	2565	2004	3485	4070	6031	6156
Density	0.0014	0.0011	0.0013	0.0009	0.0008	0.0006	0.0006
	2007	2008	2009	2010	2011	2012	2013
Nodes	5193	5501	5363	6236	6535	6769	7457
Edges	6391	7160	7331	8627	8530	10,185	11,083
Density	0.0005	0.0005	0.0005	0.0004	0.0004	0.0004	0.0004
	2014	2015	2016	2017	2018	2019	2020
Nodes	7035	8581	8966	9660	11,037	12,377	12,996
Edges	10,292	13,782	14,787	16,312	18,806	24,790	26,404
Density	0.0004	0.0004	0.0004	0.0003	0.0003	0.0003	0.0003

and

Table 3. MovieLens graph.

	May	Jun	Jul	Aug	Sep	Oct
Nodes	486	508	778	1309	575	498
Edges	87,969	76,883	176,715	530,862	65,570	42,793
Density	0.7464	0.5970	0.5847	0.6201	0.3973	0.3458

depict, respectively, the size and the density of the DBLP and MovieLens graphs per time point.

Our methods are implemented in Python 3.11 and our experiments are conducted on a macOS 14.2.1 M2 with 16 GB RAM. Our code and data are publicly available [52]. TempoGRAPHer can be accessed online [53].

6.1. Performance Evaluation

We perform experiments across various graph sizes to study the performance behavior and scalability of our algorithms. We use strict semantics for the operator of intersection, and loose semantics for the operators of growth and shrinkage. We report the execution time for each of our algorithms for graphs defined on increasing intervals, depicted on the y-axis for all cases. The time presented corresponds to the average time based on five iterations.

First, we study the performance behavior of our temporal operators. In Figure 8, we present the execution time for building the intersection, union, and difference graphs of DBLP, MovieLens, and Primary School. The x-axis represents a pair of intervals within the specified period. For instance, “up to 2005” refers to the pair [2000, 2004], [2005]. Since strict semantics are used for the intersection operator, the graph on [2000, 2004], [2005] is computed by directly applying intersection on the graph defined on [2000, 2005] and outputs a graph with nodes and edges that are present on each year within [2000, 2005]. Similarly to intersection, for union and loose semantics, the union operator is applied for [2000, 2005], resulting in a graph with elements being present in any of the years in the interval. For difference, first we need to compute the graph on [2000, 2004] employing the union operator (loose semantics) and then apply the difference operator. Difference captures nodes and edges existing in 2005 that are not present in any of the past years in [2000, 2004]. We observe that intersection is the fastest to complete, while difference is the most costly overall due to the fact that the difference operator involves union and, consequently, corresponds to two distinct operations.

In particular, for DBLP, we report a linear increase in execution time as the graph size increases. We observe a steady increase in the execution time of all three operators. For instance, the difference operator needs 0.01 s to complete for the smallest input graph of size 4 K and reaches up to 0.09 s for the largest input graph of size 250 K. For MovieLens, which has only six time points, the difference operator shows a significant spike in August, with an execution time of 0.5 s. This spike is due to a sharp increase in the number of nodes and edges (and density, which is the second highest across all time points) in August compared to the previous interval. For the union and intersection operators, the execution times remain close to constant despite the input graph reaching 1 M nodes and edges. All three operators perform the fastest for the Primary School graph, with the most time-consuming operator requiring only 0.002 s. Despite the rather high number of time points, the small number of nodes and edges (about 9 K) for the input graph results in almost constant execution times. In general, we can safely deduce that execution time depends on both the size of the input graphs and the size of the output graph.

Next, we analyze the performance characteristics of our algorithm for aggregation. Figure 9 illustrates the execution time for applying aggregation on the intersection graph for various attribute combinations. The x-axis represents an interval, e.g., [2000, 2005] corresponds to “up to 2005”, and the input of the algorithm is the resulting graph when applying the intersection operator on this interval. Concerning the static attributes, G is present across all graphs and denotes gender, and Cl denotes the class of Primary School. Regarding the time-varying attributes, P represents #publications of DBLP, and R represents rating for MovieLens. Static attributes are the fastest to complete requiring at most 0.002 s, while time-varying attributes and combination of attributes take up to 0.007 s to execute. This is due to the dynamic nature of time-varying attributes, where capturing all attribute value appearances in the interval impacts the performance. We observe a constant drop in the execution time when considering longer periods of time, which can be attributed to the decrease in the input graph, that is, the intersection graph. We derive that execution time for aggregation on the intersection graph mainly depends on the size of the input graph and the type of attribute.

In the following, we analyze the aggregation performance given as input the corresponding union graph. The aggregation on the union graph is expected to exhibit an inverse behavior compared to that of intersection, as by considering longer periods, the union graph increases. In Figure 10, we present the execution time for aggregation on the union graph for various attribute combinations. The x-axis represents an interval, e.g., [2000, 2005] corresponds to “up to 2005”, and the input of the algorithm is the graph generated when applying the union operator on this interval. We notice a general pattern of time increase as the interval increases. Also, aggregation on static attributes is the fastest to compute. When considering combinations of attributes, we observe that they are the most time-consuming for the graphs of DBLP and Primary School. However, MovieLens exhibits a different behavior with aggregation on rating proving faster than that on the combination of gender and rating. For the “up to oct” scenario, applying the union operator results in about 980 k edges to be aggregated. When aggregating on rating alone, the graph consists of 660 aggregate edges, while the combination of gender and rating yields about 2 k aggregate edges. This indicates that in the former case, there are fewer groups but a higher number of grouped edges, whereas in the latter case, there are more groups but fewer grouped edges, which apparently affects the execution time. Additionally, we observe that our algorithm achieves constant execution time for the union aggregation of static attributes, suggesting that the runtime remains stable regardless of the size of the input graph. For the cases of time-varying and combined attributes, the performance of our algorithm scales proportionally with the size of the input graph.

Next, we evaluate the performance for our skyline-based exploration algorithm. Figure 11 illustrates the skyline execution time on exploring the stable connections between females, between female and male, and between males. Female is denoted as F and male is denoted as M. The x-axis denotes a reference point, defining the exploration space where the pairs of (reference point, interval) are formed. For example, for “2005” we form the pair [2000, 2004], [2005], and all the pairs that derive by gradually reducing [2000, 2004], that is, pair [2001, 2004], [2005], continuing up to pair [2004], [2005]. The graphs generated for these pairs serve as input to the algorithm. We report high performance across all graphs, with MovieLens exhibiting the best overall, needing at most 0.14 s to complete the exploration. Despite the significant imbalance in the number of (F, F), (F, M), (M, M) edges across all graphs, we observe that execution time remains unaffected. Additionally, exploration takes the longest time to complete for DBLP, requiring up to 1.8 s. This is due to DBLP having the highest number of time points among the three graphs, as well as more edges than Primary School though fewer than MovieLens. This indicates that skyline-based exploration time primarily depends on the number of time points and then on the number of the nodes and edges in the graph. In conclusion, skyline exploration demonstrates effective performance, with execution time increasing linearly with the size of the input graph, while the number of the edges matching the pairs of attribute values requested for exploration has no significant impact on performance.

Finally, we analyze the second type of exploration, which is based on the number of interactions. Figure 12 depicts the execution time of the interaction-based exploration for stable edges between females, between female and male, and between males. The x-axis shares the same notation as the skyline-based approach. However, the pairs defined for each reference point are derived in reverse, starting from the minimum interval and gradually increasing it. We implement the default strategy to determine $\theta$ as the average of the minimum and maximum counts recorded during skyline exploration. For each type of edge, we have a different $\theta$ value. For example, in DBLP, $\theta$ is 16 for (F, F), 232 for (F, M), and 880 for (M, M) for the case “up to 2020”. Our algorithm achieves high performance for any of the graphs, with MovieLens exploration being the fastest to complete, requiring at most 0.07 s. Time appears to increase linearly, while the number of the edges being explored does not affect the performance. Undoubtedly, pruning plays a crucial role in efficiently computing the exploration result by enabling us to skip exploring intervals that do not meet our criteria. Moreover, it is important to set an appropriate $\theta$ threshold as it can potentially eliminate unnecessary computations and further enhance the performance of our algorithm.

Overall, both approaches demonstrate high performance, with the interaction-based exploration being particularly efficient due to its reliance on pruning and the ability to appropriately select a $\theta$ threshold. These approaches can function independently or complementarily. Users can start with the skyline-based approach to gain a general overview of the graph evolution. Subsequently, they can utilize the skyline output to focus on specific intervals using the interaction-based approach, setting a suitable threshold.

Our experimental results confirm the theoretical complexity of our algorithms. Specifically, the observed performance aligns with the expected scaling behavior based on the number of nodes, edges, attributes, and the length of the intervals, as outlined in the complexity analysis.

6.2. Qualitative Evaluation

In this section, we present two case studies to showcase how the TempoGRAPHer system helps users reveal underlying information and discover interesting aspects in the history of a graph.

6.2.1. Case Study: Targeting Transmission Pathways in Primary School

Our first case study uses the Primary School graph as described in Section 5.

Suppose that we want to design a policy for containing disease spread. Thus, we need to study the school’s evolution graph to identify factors that influence disease spread. In particular, we need to detect groups of students that are more active or have less stable interactions and are therefore more likely to facilitate disease spread. Also, we need to detect time periods in which disease spread is more likely to happen. In the following, we only show our results as the system interfaces are described in the previous section through Figure 4, Figure 5, Figure 6 and Figure 7.

To gain a first understanding about the attributes of the input graph and its evolution, we first deploy a graph overview to visualize the graph on various time points and gain an idea of how the graph changes through time. Figure 13a depicts the 12th time point and the gender attribute, where girls are colored with light blue, boys with orange, and unspecified gender with green. At least three well-separated clusters are formed in the illustrated graph showing student interactions. However, the clusters do not seem to depend on gender. To determine whether the clusters depend on the other attribute of the nodes, in Figure 13b we use the graph overview again for the same time point but select the class attribute this time. As we can see, there are six distinct class values at this time point, 1A, 1B, 4A, 4B, 5A, and 5B classes and teachers. By selecting class for coloring our graph, we can clearly notice that actually there are five clusters formed based on this attribute, which is a first indication that student interactions depend on their class.

We continue with the next time point and notice a change at the 13th time point, shown in Figure 14. Compared to the 12th time point, here we notice a more complex view, with students interacting with each other regardless of gender (Figure 14a) or class (Figure 14b). Thus, we can assume that the 12th time point corresponds to interactions during lessons held at the 12th hour of school, while the 13th time point shows break time, in which classes are not separated and students interact regardless of the class they belong to. Viewing the graphs at specific time points helps us recognize lessons and breaks and showcases that during class time, as expected, interactions are mostly limited among members of the same class, while during breaks interactions, they are not contained within class limits. However, this first analysis provides limited information about the volume or the duration of student interactions.

Thus, we proceed with distinct aggregation so as to quantify student interactions at lessons and breaks depending on different attribute values. Figure 15a and Figure 16b show the aggregate graphs on gender at the 12th and 13th time point respectively. Firstly, in none of the graphs can we infer any clear dependence of the interactions on the gender of the students. However, when comparing the two, we observe that boys are much more active during breaks compared to girls, while during class, both genders exhibit similar behavior. Furthermore, we can see that while fewer people interact during breaks, the interactions per person are significantly increased compared to class time. Thus, we deduce that the students that do interact during breaks are much more active compared to class time independent of their gender, as we expected based on our finding from the graph overview.

Aggregating by class for the 12th time point, we notice in Figure 15b that most interactions are confined within students of the same class. For the 13th time point, in Figure 16b, we observe that in most cases students have more interactions with students of other classes rather than with students of their own class. For instance, students from class 5A depicted with yellow-green have 41 interactions with students of the same class and 244 interactions in total with students of other classes. Consequently, unsurprisingly we again may deduce that breaks during school time pose a risk for an increase in disease spread.

To gain further insights on the nature of the interactions between the students, we use exploration to investigate their stability and see whether we can rely on this fact to limit disease spread.

We start by studying the stability of interactions between the students of the same gender using skyline-based exploration. Comparing the interactions between girls in Figure 17a and boys in Figure 17b, we report 10 results for the girls’ and 13 results for the boys’ contacts. We observe that periods with high stability have a rather limited length, while there are shorter periods in which a very high degree of stable interactions is observed. In the skylines for both girls and boys, intervals with length longer than seven maintain at most nine stable interactions, which can be seen as a bound on the duration and size of isolation bubbles. On the other hand, we observe an interval of duration four on ([12], [7, 11]) with stability of at least 32 for both girls and boys, indicating a potential lower risk zone for disease spread. Also, as both figures illustrate, most skyline results for both boys and girls are reported on the 12th time point, which indicates that 12 is the reference point with the highest stability.

Based on the first conclusions drawn from the skyline-based exploration, we next deploy interaction-based exploration for the interactions between students of the same gender. To set $\theta$, we start by initializing it using the default strategy and then fine-tune and obtain $\theta =35$. Figure 18 depicts the interaction-based exploration results with $\theta =35$ for girls (Figure 18a) and boys (Figure 18b). We notice longer intervals of stability for boys’ contacts with an average length of $1.88$ compared to those for girls, where the average length of the stable intervals is $1.19$. The longest stability period reported for boys is on ([12], [7, 11]) with interval length four, a result that is also included in the skyline of the stable interactions between boys. On the other hand, for girls, the highest stability is on ([12], [8, 11]) and ([11], [7, 10]) with interval length three. While ([12], [8, 11]) was also discovered through the skyline exploration, ([11], [7, 10]) is not part of the skyline. Thus, we can see in this example how the interaction-based exploration allows us to discover more results of significant stability, where significance is determined through the user-defined threshold $\theta$.

After exploring the interactions based on gender, we focus on the class attribute and first present the results of the exploration of stable contacts between students of junior class 1A and between students of senior class 5A. First, we run the skyline-based exploration, where we report 10 results for the stable contacts between students of class 1A, as shown in Figure 19a, while for students of class 5A we report 14 results (Figure 19b). In general, the results for the senior class also exhibit longer intervals and higher counts compared to the results for the junior class, indicating that senior students build more stable connections compared to junior ones.

Using a similar approach to the one we used with same-gender interactions, we apply the interaction-based exploration with $\theta =15$. We report 14 results for the students of class 1A, as shown in Figure 20a, with the longest stability periods on ([4], [1, 3]), ([9], [6, 8]), ([11], [8, 10]) and ([12], [9, 11]) with interval length two, while Figure 20b reports 16 results for the students of class 5A, where ([12], [6, 11]) corresponds to the longest stability period with length five. We can see that the interaction-based exploration is again able to reveal more results compared to the skyline-based approach that satisfy a minimum user-defined threshold of stability, giving us more opportunities to detect periods that seem of lower risk with respect to disease spread.

To conclude our investigation, we contrast our results of interactions between students of the same class, with an analysis of the relationships of students between students of different classes but the same grade using skyline-based exploration. In particular, we explore the contacts of students of two different classes that belong to the same junior grade as depicted in Figure 21a for students of 1A and 1B and also to the same senior grade as shown in Figure 21b for students of 5A and 5B. Despite selecting students of the same grade, as we expect students of the same age to interact more among themselves, we still observe that the skyline output is rather poor with only two and four results, respectively, and we observe no significantly high stability counts nor long stability periods. For the junior students, the longest stable interval only reaches length two. Consequently, we may safely deduce that the class attribute seems to be the most important attribute that determines the stable interactions between students, showing us opportunities for limiting disease spread by creating isolation bubbles within the limits of each class at least.

In summary, our analysis indicates that while gender does not seem to be a significant factor governing student interactions, boys still show greater stability on their relationships at school compared to girls. Boys are also much more active than girls during breaks. Regarding the class attribute, we observe that most stable interactions remain within the limits of a class, and older students seem to have established more stable contacts compared to younger ones. Finally, while during lessons most of the interactions are between students of the same class, during breaks, a large number of interactions are between students of different classes showing us that in order to limit disease spread, breaks should be limited or at different times among classes.

The Primary School dataset was originally created to study important properties on the contact patterns and the relevance of these patterns on modeling propagation of a disease [47]. Our results confirm the findings of this work about the importance of age and class in shaping student contact patterns. Furthermore, our findings indicate that gender is a factor that can affect interactions, and also, we identify cases of significant stability in the student contacts, corresponding to potential safety zones.

6.2.2. Case Study: Growth of Same Gender Collaborations in DBLP

In this case study, we investigate the evolution over the years of collaborations in DBLP between authors of the same gender, focusing on the growth event. To this end, we apply graph exploration using the skyline-based method.

In Figure 22a, we report the skyline result for new collaborations between female authors. Recall that the skyline includes the most important intervals with respect to the duration and volume of new collaborations. Notably, seven out of eight results appear in 2019, with at least 640 collaborations reported in any of the intervals. The highest count is 669 new collaborations in 2019 that did not exist in 2018. The longest period is [2000, 2018] with a count of 640, meaning that there are 640 new collaborations in 2019 that did not exist in any of the previous years. Only one result is reported for 2020, with 629 new collaborations and period [2000, 2019], meaning that none of them existed in any of the previous years. As the majority of the results are concentrated in 2019, we consider 2019 as the most important reference point, signifying the greatest growth for female collaborations.

In Figure 22b, we report the skyline result for new collaborations between male authors. We notice results are reported only for 2020, indicating it as the most important year for new collaborations between male authors, with more than 17 K new collaborations. Specifically, the highest count reported is 18,370 new collaborations that did not exist in 2019, and the longest interval reported is [2000, 2018] with a count of 17,400, which means there are 17,400 new male collaborations that did not exist before.

The results show a significant difference in the number of new collaborations between female and male authors, reflecting a significant gender gap in research. Although this is an important indicator, it would be useful to investigate a different aspect, focusing on the percentage of new collaborations in relation to the total collaborations reported.

We focus on the important reference points for growth, i.e., years 2019 and 2020, to study how the overall collaborations that appear in these years are related to growth. Thus, we apply distinct aggregation by gender. Figure 23a,b report the results. Orange nodes represent male authors and blue nodes female authors. For the year 2019, which is the most important year in terms of growth of female collaborations, there are overall 706 F-F collaborations. Among these collaborations, 640 appear for the first time, meaning that about 90% of the female collaborations appearing in 2019 are new ones. For the year 2020, which is the most important year in terms of growth of male collaborations, there are 20130 M-M collaborations in total, of which 17400 appear for the first time, that is, the percentage of new male collaborations in 2020 is 86%. This means that we see a slightly higher percentage of growth for female collaborations. Additionally, in 2019 we report 6164 collaborations involving female authors (F-F, F-M), indicating that only 11% of these collaborations consist exclusively of female authors, while 77% of collaborations involving male authors (M-M, F-M) are exclusively male collaborations. For 2020, the ratio remains 11% for collaborations involving female authors, while for male authors it slightly increases to 78%. It should be noted that this significant disparity in collaborations between female authors and male authors mainly derives from the lower number of female authors compared to male authors. Nevertheless, it confirms the overall findings that underscore the limited representation of women in research.

In conclusion, our analysis underscores gender inequality in research. Furthermore, incorporating additional attributes, such as the author affiliation or research field, relevant analyses can be applied to identify trends in collaborations, focusing for example, on interdisciplinary research. By carefully analyzing the evolution of collaborations, policymakers can identify patterns to facilitate proactive actions. For example, identifying the years of important growth or shrinkage in specific types of collaborations, targeted actions may be undertaken.

Our case study aligns with research on the temporal evolution of academic collaboration networks, particularly regarding gender disparities. A steady increase in female participation in the INFORMS network since 1980 is reported in [54], though women still represent a smaller proportion of high-publication authors. Gender dynamics are also explored within the software engineering academic community in [55], revealing significant gender biases in academic promotions, with women tending to form less tightly knit co-authorship clusters than men.

7. Conclusions

In this paper, we described the TempoGRAPHer system for visualizing, aggregating, and exploring temporal graphs. TempoGRAPHer offers two complementary strategies for exploring the evolution of a graph, namely skyline-based and interaction-based exploration. Skyline-based exploration identifies the peaks in the evolution of the graph, while interaction-based exploration offers a closer look at the time intervals of significant change, where significant change is determined by the number $\theta$ of events (stable, new or disappeared interactions) as specified by the user.

As future work, we plan to extend the skyline-based and the interaction-based exploration to consider several types of interactions (i.e., value combinations) for each attribute at the same time. For instance, in our running example, exploration will be supported for not just one value combination for gender (e.g., girl–girl) at a time but for all possible ones. In this case, besides the temporal interval dimension, our skylines will have as many dimensions as the possible value combinations for the attribute. Analogously, the user will provide multiple thresholds, one for each type of interaction.

Additionally, we will explore techniques for identifying the most important attributes and attribute values and direct our exploration on them. In terms of user friendliness, we aim to conduct user studies to further enhance the usability of our system. We also plan to explore alternative, more scalable visualization techniques to improve the user experience.

We also plan to extend TempoGRAPHer to handle streaming temporal data, enabling the system to process and visualize dynamically evolving graphs in real time. This extension will improve TempoGRAPHer’s applicability to time-sensitive applications, such as monitoring rapidly changing networks. By including dynamic exploration, where exploration results are automatically refreshed as new data arrive, the system will be able to provide continuous insights into a graph’s evolution. To achieve this, we will explore performance optimization techniques, such as incremental graph updates and parallel processing, to handle the increased computational load efficiently.

Finally, we aim to expand our interest to various applications of temporal graph analysis, such as social influence dynamics and rumor propagation [56,57], by integrating learning-based approaches, such as graph embedding techniques [58,59].