11institutetext: TU Wien, Vienna, Austria
11email<EMAIL_ADDRESS>
# On Time and Space: An Experimental Study on Graph Structural and Temporal
Encodings

Velitchko Filipov 11 0000-0001-9592-2179 Alessio Arleo 11 0000-0003-2008-3651
Markus Bögl 11 0000-0002-8337-4774 Silvia Miksch 11 0000-0003-4427-5703

###### Abstract

Dynamic networks reflect temporal changes occurring to the graph’s structure
and are used to model a wide variety of problems in many application fields.
We investigate the design space of dynamic graph visualization along two major
dimensions: the network structural and temporal representation. Significant
research has been conducted evaluating the benefits and drawbacks of different
structural representations for static graphs, however, few extend this
comparison to a dynamic network setting. We conduct a study where we assess
the participants’ response times, accuracy, and preferences for different
combinations of the graph’s structural and temporal representations on typical
dynamic network exploration tasks, with and without support of common
interaction methods. Our results suggest that matrices provide better support
for tasks on lower-level entities and basic interactions require longer
response times while increasing accuracy. Node-link with auto animation proved
to be the quickest and most accurate combination overall, while animation with
playback control the most preferred temporal encoding.

###### Keywords:

User Study Evaluation Time-oriented Data Graphs & Networks.

##  1 Introduction

The increased availability of time-dependent datasets contributed to the rise
of research interest toward dynamic network visualization, nowadays considered
a mature and thriving research field [12]. Kerracher et al. [40] define a two-
dimensional design space for dynamic network visualization: structural
representation (how the graph’s topology is represented) and temporal encoding
(how time and, consequently, the graph temporal dynamics are illustrated).
This two-dimensional design space is expressive enough to characterize the
majority of existing dynamic network visualization approaches.

There is extensive literature on studies designed to evaluate different graph
representations for typical exploration tasks on static networks. Similar
studies have been conducted for dynamic approaches, however mostly focused on
node-link diagrams coupled with different temporal encodings (see Section 2).
This also comes as a consequence of the limited number of dynamic network
visualization approaches that have matrices as their base graph representation
[12] (see, e.g., [38, 52]). Therefore, empirical evidence about the
performance and preference for different dynamic network visualization
approaches in our design space is still scattered between different studies,
experimental settings, procedures, and tasks. Similarly, existing user studies
in this context incorporate simple interaction methods to support the network
exploration (see, e.g., [6, 45]), however, their effect on the participants’
experience has not been fully investigated, thus motivating the need for
broader and rigorous experimentation.

Our Contribution. In this paper we design, conduct, and discuss the results of
an experimental study aimed at assessing and comparing different dynamic
visualization approaches centered around combinations of graph representation
(node-link and adjacency matrix), temporal encoding (juxtaposition,
superimposition, animation with playback control, and auto animation), and
interaction support for offline dynamic graph visualization. We conduct a
statistical analysis of the study results and condense our findings in a
concise discussion meant to support further studies and design of dynamic
network visualization techniques.

##  2 Related Work

We outline recent related studies conducted along the two dimensions of the
design space introduced by Kerracher et al. [40], focusing on user studies.

Structural Representations. In graph drawing literature, several studies
assess the readability, task performance, and effects of aesthetic criteria on
human cognition of different graph structural encodings (e.g., [14, 25, 50,
32, 45, 44, 48, 47]). Ghoniem et al. [32] evaluate, in a controlled
experiment, the readability of graphs when represented as node-link diagrams
compared to adjacency matrices on generic graph tasks. Their findings suggest
that the ability of either visualization to support typical exploration tasks
depends on the size and density of the network; the authors concluded how
matrix-based techniques were under-exploited, despite their proved potential
with larger and denser networks. Okoe et al. [45, 44] conduct further
comparative evaluations between node-link and matrix representations on a
large scale ($\sim 800$ participants). Their results show that node-link
diagrams better support memorability and connectivity tasks. Matrices have
quicker and more accurate results for tasks that involve finding common
neighbors and group tasks (i.e., involving clusters). Concurrently, Ren et al.
[50] conduct a large scale study ($\sim 600$ participants) comparing the
readability of node-link diagrams against two different sorting variants of
matrix representations on small to medium social networks ($\sim 50$ nodes).
Their findings do not differ significantly from the ones by Okoe et al. [45],
suggesting that node-link provided a better implicit understanding of the
network, with lower response times and higher accuracy than matrices. However,
the gap between the two tended to reduce as the size of the graph increased.

Temporal Encodings. One of the most studied problems concerning dynamic
network visualization, is the ability of participants to retain a “mental map”
of the graph while investigating its evolution [4, 5, 6, 7, 49]. Archambault
and Purchase investigate the effect of drawing stability on the node-link
graph representation coupled with animation and small multiples [6, 7].
Drawing stability proved to have a positive effect on task performance, with
animation able to improve over timeline in low stability scenarios. Ghani et
al. [31] investigate the perception of different visual graph metrics on
animated node-link diagrams. Results suggest that animation speed and target
separation have the most impact on performance for event sequencing tasks.
Linhares et al. [41] compare four different approaches for visualization of
dynamic networks, namely the Massive Sequence View [26] (timeline-based), the
Temporal Activity Map [42], and animated node-link and matrix diagrams. While
all techniques reached satisfactory results, the animated node-link was the
favorite choice of the participants. Even though matrix-based approaches are
included in this study, it does not exhaustively cover all the possible
combinations of our design space. Filipov et al. [29] conduct an exploratory
study comparing different combinations of structural and temporal
representations. The results suggest that tasks with matrices were completed
quicker and more accurately, the participants preferred matrices with
superimposition, and juxtaposition was among the least preferred approaches.
However, these results require further formal investigation. Overall, related
literature shows that the perception of different temporal encodings has been
mainly investigated on node-link diagrams, with few papers focusing on the
other combinations of structural and temporal encodings. In this sense, our
paper constitutes an effort in understanding whether the differences between
node-link and matrix representations still hold in a dynamic scenario, what is
the efficacy of the temporal representations, and how effective (and how
important) is it to include interactions when designing such approaches.

##  3 Dynamic Graph Visualization Design Space

We refer to a dynamic graph $\Gamma$ as a sequence of individual graphs each
one representing its state at a specific point in time:
$\Gamma=(G_{1},G_{2},...,G_{k})$; we denote the individual $G_{x}$ as a
dynamic graph timeslice. We now briefly describe the different structural and
temporal encodings, along with the interactions included in the scope of our
experiment, detailing their implementation.

###  3.1 Network Structural Encoding

The structural dimension focuses on the challenges of laying out a graph to
visually present the relationships between elements in an understandable,
accurate, and usable manner [40]. Node-Link (NL) diagrams present the
relational structure of the graph using lines to connect the entities that are
depicted using circles, whose coordinates on the plane are computed using
specialized algorithms. In our study, we compute the NL layouts using the
force-directed implementation of d3js [19] considering all the timeslices
simultaneously instead of on a per-frame basis. This process of aggregation
[22] is simple to implement and provides a stable layout throughout the
sequence of timeslices, at the expense of the quality of individual layouts.
We refer to the following for a broader discussion on dynamic network layout
algorithms [8, 11, 12, 21, 23, 24, 27, 28, 54]. Adjacency Matrices (M)
visualize the network as an $n\times n$ table. A non-zero value in the cell
indicates the presence of an edge between the nodes identified by the
corresponding row and column. In our study we order the rows and columns
alphabetically according to the node’s label. More advanced reordering methods
exist [13], however, matrix reordering is still under-investigated in a
dynamic context and we decided to exclude this aspect from the study design.

Figure 1: Network structural and temporal encodings: Juxtaposition (A,D),
Superimposition(B,E), and Animation with Playback Controls (C,F)

###  3.2 Network Temporal Encoding

In dynamic networks the temporal dimension plays an important role in the
analysis process and requires special attention to enable effective
exploration and better understand the behavior of the network [43].
Superimposition (SI) encodes the temporal dimension of the network in the same
screen space by overlaying the timeslices (see, e.g., [21, 28]) or making use
of explicit encoding (see., e.g., [33, 39]). In our study we represent the
temporal information in SI using colorblind-friendly color palettes [30]. In
NL, we generate multiple parallel edges between the nodes, one for each
timeslice where the edge is present, and color-code them individually. In M we
subdivide each cell uniformly into rectangles, each representing the existence
of that edge during that timeslice, which are colored similarly (see Figure 1
B-E). Juxtaposition (JP) represents the graph’s temporal dynamics as distinct
layouts, each with dedicated screen space, similar to the small multiples
approach by Tufte [55] (see Figure 1A,D). In our study we generate one diagram
per timeslice and arrange them adjacent to each other. Animation with Playback
Control (ANC) uses a time slider to control the state of the animation and
move to any of the available timeslices in no particular order (see Figure
1C,F). This enables for a more fine and controlled exploration and analysis
compared to animation, where speed and time progression is typically fixed.
Auto Animation (AN) depicts the change of the graph over time as smooth
transitions between subsequent timeslices. Differently from ANC, with AN it is
not possible to skip forward or navigate backward in time and it automatically
goes over each of the timeslices in a sequence.

###  3.3 Interactions

The interactions we implement are meant to support the network exploration.
The following apply regardless of the temporal encoding: (i) zooming and
panning (both for M and NL); (ii) hovering over a M cell highlights its
corresponding row and column; (iii) in NL, nodes can be moved by dragging in
order to de-clutter some denser areas of the drawing. Moreover, for AN only
and regardless of the structural representation, the time between consecutive
timeslices can be increased (7 sec maximum) or decreased (1 sec minimum). This
selection should not favor any specific combination of structural and temporal
encoding techniques over the others. Zooming, panning, and node rearrangement
are commonly available in graph exploration software, like Gephi [10]. M
mouse-over was also used by Okoe et al. [45]. AN speed could also be
manipulated in the study by Archambault and Purchase [5].

##  4 Study Design

In this section we present the study design, including our tasks, research
hypotheses, stimuli, and study procedure.

###  4.1 Tasks and Research Hypotheses

T |  Low-level |  High-level
---|---|---
T1 |  At which time step is the relationship between {source} and {target} introduced for the first time? |  At which time step does the clique between {nodes} appear for the first time?
T2 |  Sum up the changes (additions and removals) of {node}’s degree across all time steps. |  Calculate the change of the clique’s size between {nodes} across all time steps.
T3 |  At which time step does the node {node} have its highest degree? |  Consider the set of nodes {nodes}. Find the size of the largest maximal clique across all the time steps between the given nodes.
Table 1: The test questions (trials), per task (rows) and entity type
(columns).

Tasks. The tasks used in our experiment are available in Table 1.

Rationale. We picked one task for each category of temporal feature in the
taxonomy proposed by Ahn et al. [2], namely, Individual Temporal Features
(T1), Rate of changes (T2), and Shape of changes (T3). We selected the most
common tasks referenced in the taxonomy and included in our experiment these
tasks for both low- (nodes and links) and higher-level (cliques) entities.

H |  Research Hypothesis
---|---
H1 |  Matrices have lower response times and higher accuracy for all tasks compared to node-link diagrams, regardless of the temporal encoding.
H2 |  From all temporal encoding techniques, superimposition has the lowest response times and highest accuracy, regardless of the structural representation.
H3 |  Providing interaction techniques increases the response times but not the accuracy.
H4 |  Matrices have lower response times and higher accuracy for tasks on low-level entities and node-link diagrams have lower response times and higher accuracy for tasks on higher-level entities, regardless of the temporal encoding.
H5 |  The combination of matrices with superimposition results in the lowest response times and highest accuracy compared to other combinations of network structural and temporal encoding.
Table 2: The research hypotheses that were evaluated in our experiments.

Hypotheses. We base our research hypotheses on the proposed tasks and we
report them in Table 2.

Rationale. Hypotheses H1, H2, and H5 are derived from the results of a
previous exploratory study [29] (see also Section 2). While the focus of this
experiment is centered around the visual encoding combinations within our
design space, H3 is intended to investigate the effects of common interactions
techniques in this context. We argue that they might increase the response
times over visual inspection alone, but without significant impact on
accuracy. In H4 we conjecture that following the evolution of a cluster or
clique is more difficult with M compared to NL, as the participant must track
several elements at once. We assume this would be easier to achieve with NL as
the nodes are drawn closer together.

###  4.2 Experiment Setting

Stimuli. We generated 24 different scale-free random [15] graphs
($35\leq|V|\leq 45,46\leq|E|\leq 71$) with the NetworkX python library [35,
34]. We chose this category of networks as they resemble real-world data
examples of scientific interest (e.g., the world-wide-web, authors’ co-
citation networks [3]). We augmented each graph with 4 timeslices by randomly
deleting edges from the original input graph to simulate temporal dynamics (at
each subsequent timeslice the edges were added back and a new set was selected
for removal). Finally, we split the datasets into two different types: 12
graphs with cliques and 12 without. Cliques were artificially introduced in
the graphs by choosing 5 random nodes which were fully connected in one or
more of the graph timeslices. The size of the graphs is comparable with the
majority of empirical studies on graph visualization [50, 59].

Trials. Each of the tasks is applied to all combinations of structural and
temporal encodings of interest in our study (see Section 3) resulting in 48
unique trials: $3(task\ types)\times 2(entity\ types)\times 2(network\
encodings)\times 4(temporal\ encodings)$. The order of the trials during the
study is randomized in order to mitigate learning effects. The participants
take part in the online experiment by completing the trials prepared using
SurveyJS [1].

Study Design. Our experiment follows a between-subject arrangement: all
participants complete the same entire set of 48 trials on the same graphs, but
are exposed to one of two conditions, either without (Group A) or with (Group
B) the support of the interactions discussed in Section 3.3. Participants are
assigned to one of the two groups when they first access the online
experiment, with a 75% probability of being assigned to Group B. As only one
hypothesis (H3) deals with the group subdivision, we design the experiment to
have a higher number of participants with interaction support. For each trial
we ask the participant to provide a confidence score of their answer using a 5
point Likert scale (1 least confident - 5 most confident). At the end of the
experiment, the participants express their thoughts in text about the encoding
combinations they encountered and rank them on a 5 point Likert scale (1 least
preferred - 5 most preferred).

Participants. For our study, we enrolled students part of a graduate course on
information visualization design. To ensure that participants had a sufficient
level of knowledge on the topic, we gave an introductory lecture about the
visualizations and the experiment modalities. Participation was optional and
its performance did not impact the final grade of the students. The online
setting was necessary to guarantee a sufficient number of participants, while
ensuring a safe social-distancing protocol. However, this also meant giving up
control on the experiment environment.

##  5 Study Results

We received a total of 76 submissions from as many participants, of which we
removed 8 that were trying to game the experiment. This resulted in a final
set of 68 valid submissions that were used as the basis of our analysis.
Further information and the complete set of results can be found in the
Appendix.

###  5.1 Analysis Approach

For each question of our study, we collected the participants’ answers, their
corresponding response times, and confidence values. We ignored the group
subdivision (Group A and B) for hypotheses which did not focus on the presence
of interactions (all except H3, see Section 4.1), as ANOVA tables do not show
a statistically significant interaction effect between the independent
variables for H1, H2, H4, H5 (for more information we refer to the Appendix).

We conduct our analysis as follows, supported by Python libraries for
statistical analysis [36, 56, 57]. We consider the structural and temporal
encoding, the task type, entity type, and the groups (Group A and B) as
independent variables, the response times and accuracy are taken as dependent
variables. As the group subdivision is not even (25-75), we choose methods
that are robust against these unbalanced designs [9, 18, 37, 58]. For each of
the hypotheses, we grouped the data according to the hypothesis and visually
inspected response times and accuracy (number of correct answers $\div$ total
number of answers). To remove outliers from the data before the analysis we
employed the inter-quantile range (IQR) [51]. We set the IQR lower
($q_{1}-1.5\cdot\textrm{IQR}$) and upper ($q_{2}+1.5\cdot\textrm{IQR}$) bounds
at $q_{1}=0.25$ and $q_{2}=0.75$ as the outlier cut-off boundaries. This
resulted in 116 trials (or 3.43%) being detected as outliers and omitted from
the analysis.

Hypothesis | Groups | MWU | T-Test | Binomial
---|---|---|---|---
| (NL T1) vs (M T1) | 0.0104*b | <0.001***b | 0.0013*b
| (NL T2) vs (M T2) | 0.1579 | <0.001***b | 0.9313
H1 | (NL T3) vs (M T3) | <0.001***b | <0.001***b | 0.0022**b
| (SI) vs (JP) | <0.001***b | 0.1065 | 0.166
| (SI) vs (ANC) | 0.8662 | 0.1429 | 0.0883
H2 | (SI) vs (AN) | 0.2766 | 0.7751 | <0.001***b
H3 | (Grp A) vs (Grp B) | <0.001*** | <0.001*** | <0.001***
| (M Low) vs (NL Low) | <0.001***b | 0.1392 | <0.001***b
H4 | (M High) vs (NL High) | <0.001***b | <0.001***b | 0.4321
| (M+SI) vs (M+JP) | 0.0056** | 0.2567 | 0.2424
| (M+SI) vs (M+ANC) | 0.6301 | 0.2989 | 0.0261
| (M+SI) vs (M+AN) | 0.2766 | 0.6328 | 0.0646
| (M+SI) vs (NL+SI) | 0.0038**b | <0.001***b | 0.449
| (M+SI) vs (NL+JP) | <0.001***b | <0.001***b | 0.1389
| (M+SI) vs (NL+ANC) | 0.0088 | <0.001***b | <0.001***b
H5 | (M+SI) vs (NL+AN) | 0.0331 | <0.001***b | <0.001***b

Table 3: The results of the statistical test (p-values) for each hypothesis.
We mark the cells with * if $p<0.05$, ** if $p<0.01$, *** if $p<0.001$. If
multiple comparisons are performed, b indicates the Bonferroni correction
[17].

The task response times in our experiment are not normally distributed. To
mitigate this, we perform a Box-Cox transformation [20]. Visual inspection of
the quantile-quantile (Q-Q) plots confirmed a normal distribution of the
transformed data. This allows us to run parametric tests, specifically, ANOVA
(see Appendix for further information about the ANOVA tables) and T-tests [9,
18, 37, 58]. The standard ANOVA and T-tests are robust against such skewed
distributions [16, 46, 53], therefore, we rely on them for our analysis as
they both have more statistical power than non-parametric tests and detect
significant effects if they truly exist. In presence of statistically
significant difference ($p\textrm{-value}<0.05$), we check, with T- and Mann-
Whitney-U (MWU) tests, whether the significance held and visually explored the
corresponding box plots to come to a conclusion. To evaluate our hypotheses on
accuracy, we also perform Binomial tests to detect statistical significance
between the distributions.

###  5.2 Quantitative Results

Figure 2: H1: Box plot of response times for NL and M per task.

H1. We presume based on previous work [29] that M would perform better overall
compared to NL for all tasks. Figure 2 depicts differences in response times
between M and NL diagrams per task type. The results (see Table 3) indicate
that NL is generally faster and more accurate than M. However, when looking at
their differences per task we discover for T1 that NL is significantly faster
than M (NL: 73.49s, M: 97.93s), whereas M proves to be more accurate (NL:
74.9%, M: 80.7%). For T2 the T-Test detects a significant difference in
response times between NL and M (NL: 133.41s, M: 194.20s), however, in terms
of accuracy they both perform similarly (NL: 52.5%, M: 52.7%). For T3 NL
representations significantly outperform M in terms of response times (NL:
107.32s, M: 175.92s) as well as accuracy (NL: 65.7%, M: 59.4%). Summarizing,
the results suggest NL to generally have the lowest response times and higher
accuracy compared to M for the proposed tasks. Thus, our results do not
support H1.

Figure 3: H2: Box plot of response times for temporal and network
representations.

H2. We assume SI to have the lowest response times and highest accuracy out of
all the temporal encoding techniques. In our analysis, however, we do not
detect any statistical significance in the comparisons shown in Table 3, with
the only exception being JP, which has considerably lower response times than
SI (see Figure 3). Concerning response times, JP has the lowest (118.32s),
followed by AN (127.76s), SI (129.69s), and ANC (141.35s). We also run a
paired T-Test comparing the temporal encoding approaches to check for
statistical significance between pairs out of our initial hypothesis and
detect a significant difference between JP and ANC. In terms of accuracy, we
discover a significant difference between SI (62.1%) and AN (68.6%). Whereas,
between SI and JP (64.45%) or ANC (59.13%) there is no significant difference.
We conjecture these results to be due to the graph’s size and limited number
of structural changes over time, that might favor AN as it is possible for
participants to follow all changes the during animation. Our analysis shows no
evidence to support H2.

Figure 4: H3: Box plot of response times for interaction groups per task.

H3. We conjecture that providing interactions influences the response times
but not the accuracy. Our tests detect a significant difference (see Table 3)
in the response times between group A (no interactions; 114.76s) and group B
(interactions; 163.83s). As we initially assume, the group with interactions
is much slower in completing tasks than the group with no interactions (see
Figure 4), however, the difference in accuracy is unexpected. The group with
interactions is significantly more accurate than the one without (group A:
58%, group B: 65%). This suggests that interactions indeed increase response
times, but at the same time provide the participants with a much better
understanding of the visualized graphs and corresponding network dynamics
regardless of the temporal encoding, therefore, leading to more accurate
responses. The analysis shows that our results support H3 in terms of response
times, but not accuracy.

Figure 5: H4: Box plot of response times for (A) single entities and (B)
cliques.

H4. We formulate this hypothesis to evaluate whether the response times and
accuracy of M and NL representations is affected by the type of target entity
in a dynamic context (low-level \- individual nodes and links; or higher-level
\- cliques), regardless of the temporal representation. For low-level
entities, we do not detect any significant differences of the response times
between network representations (see Table 3), both NL and M diagrams perform
similarly with no clear winner. The results (see Figure 5) for tasks on low-
level entities indicate that M has lower response times (NL: 97.08s , M:
90.24s), whereas for higher-level entities NL has significantly lower response
times (NL: 146.66s, M: 245.2s). However, in terms of accuracy M is
significantly better than NL for lower-level entities (NL: 82.1%, M: 86.4%).
For the higher-level entities, NL and M representations perform quite
similarly in terms of accuracy (NL: 42.1%, M: 41.3%) Based on these findings,
the results suggest that H4 is partially supported.

Figure 6: H5: Box plot of response times for temporal and network
representations.

H5. Finally, we want to assess the response times and accuracy for all
possible combinations of network structural and temporal encodings. Our
assumption is that M representations with SI temporal encoding have the lowest
response times and highest accuracy. We compare M+SI to all other combinations
of network structural and temporal encodings (see Figure 6). The results of
the statistical tests yield significant differences in response times when
comparing M+SI (154.53s) with M+JP (140.13s), NL+SI (105.25s), NL+JP (99.54s),
NL+AN (108.8s), and NL+ANC (110.97s). Between M+SI (154.53s) and M+ANC
(168.87s) and M+AN (160.62s) there is no significant difference in response
times (see Table 3). In terms of accuracy we detect statistically significant
differences between M+SI (61.1%) and NL+ANC (51.8%) and NL+AN (71.4%).
Whereas, the other combinations do not differ enough to warrant significance:
M+JP (62.2%), M+ANC (66.4%), M+AN (65.5%), NL+JP (64.6%), and NL+SI (62.9%).
From these results, the most balanced combination in terms of response times
and accuracy is NL+AN followed by NL+JP. Therefore, we find no evidence
supporting H5.

###  5.3 Qualitative Results

We collect the participants’ ratings per combination of network structural and
temporal encoding along with textual feedback pertaining to their preferences
and experience during the experiment (see Figure 7). There are no major
differences in the preferences between the SI and JP encodings; ANC is the
most preferred temporal encoding when coupled with a NL base representation.
The NL representation is generally the most preferred approach, regardless of
the temporal encoding. In terms of the participants confidence, we observe
that most participants seemed to be fairly confident in their answers across
all approaches (see Figure 8). Most notably, the participants were most
confident with NL+JP, followed by M+ANC, M+JP, and NL+ANC. There is general
consensus that NL+SI was a very cluttered combination, whereas for M it
performed a lot better and was easier to understand (“SI was really confusing
for some of the NL tasks but really useful for many of the M tasks”). This is
presumably due to the clutter generated by parallel edges crossings that occur
in NL diagrams, which does not affect M. As in previous studies [29], the
feedback on JP outlines that it requires participants to split their attention
between multiple views in order to compare the temporal information. The ANC
approach was preferred by the study participants for its flexibility due to
the additional controls (i.e., time slider). AN was not considered to be a
very good temporal encoding technique with the feedback being consistent
across structural representations. Some participants commented that they
needed to “screenshot every timestamp to look at the different connections
between the nodes” and wait to watch the whole animation from the beginning.
NL+AN, therefore, appears to be the least practical of the approaches,
however, it also provides the best results. We conjecture this to be due to
the size of the graphs and the amount of structural changes occurring. M+AN is
the lowest rated by the participants. The general consensus for AN is that it
was difficult to keep track of the changes occurring between the nodes,
requiring the viewer to memorize node positions and labels incurring a high
cognitive effort to complete the tasks. Despite the aforementioned drawbacks,
AN scales better to a larger amount of timeslices compared to SI and JP.
Finally, the group with interactions had a better experience overall compared
to the group without. The majority of the members of this group explicitly
requested interactions to be implemented, supporting our findings concerning
H3.

Figure 7: Preferences per network and temporal encoding on a Likert scale
(1-5). Figure 8: Confidence per network and temporal encoding on a Likert
scale (1-5).

###  5.4 Limitations

This experiment’s limitations open potential future research directions.
First, the size of the graph was not considered. We chose small graphs as
stimuli for this study, both in the amount of nodes/links and number of
timeslices. M scales better to larger graphs than NL, while AN and ANC support
a greater number of timeslices compared to SI and JP. Future studies on
dynamic network visualizations might provide evidence on the scalability of
the different potential combinations. Second, we chose simple, custom
implementations for our structural and temporal encodings, disregarding more
advanced solutions in literature (see Section 3). While this was done with the
intention of testing the fundamental principles of the techniques in our
design space, evaluating more sophisticated approaches might have
significantly impacted the results. Finally, we focus on a selection of tasks
from a taxonomy on network evolution [2], other graph-based taxonomies could
present relevent benchmarks for the proposed techniques.

##  6 Conclusion

In this paper we presented an experimental study assessing the response times,
accuracy, and preferences of participants on different combinations of network
structural and temporal encodings, with and without interaction support for
the network exploration. Overall, the participants expressed a preference for
NL over M, specifically preferring the ANC temporal encoding over the other
options, despite AN being more accurate and having lower response times. We
also note that our results suggest that the use of M as base representation
proved to be more accurate for tasks on low-level entities and counting across
different temporal representations. The results of our experiment also suggest
a significant effect of interactions on participants’ performance. Therefore,
as directions for future work, we consider evaluating in more detail the
influence that interactions have on accuracy and response times for dynamic
network visualization, also considering the potential influence of the graph
size on the perception of different combinations of network and temporal
encodings.

Acknowledgements This work was conducted within the framework of the project
KnoVA (P31419-N31) and ArtVis (P35767) funded by the Austrian Science Fund
(FWF).

## References

  * [1] Surveyjs - survey and form javascript libraries. https://surveyjs.io/, online, Accessed: 2022-08-09
  * [2] Ahn, J.w., Plaisant, C., Shneiderman, B.: A task taxonomy for network evolution analysis. IEEE Trans. on Visualization and Computer Graphics 20(3), 365–376 (2014)
  * [3] Albert, R., Barabási, A.L.: Statistical mechanics of complex networks. Reviews of modern physics 74(1), 47 (2002)
  * [4] Archambault, D., Purchase, H., Pinaud, B.: Animation, small multiples, and the effect of mental map preservation in dynamic graphs. IEEE Trans. on Visualization and Computer Graphics (2011)
  * [5] Archambault, D., Purchase, H.C.: Mental map preservation helps user orientation in dynamic graphs. In: Graph Drawing & Network Visualization. pp. 475–486. Springer (2013)
  * [6] Archambault, D., Purchase, H.C.: The “map” in the mental map: Experimental results in dynamic graph drawing. International Journal of Human-Computer Studies 71(11), 1044–1055 (2013)
  * [7] Archambault, D., Purchase, H.C.: Can animation support the visualisation of dynamic graphs? Information Sciences p. 495–509 (2016)
  * [8] Arleo, A., Miksch, S., Archambault, D.: Event-based dynamic graph drawing without the agonizing pain. In: Computer Graphics Forum. Wiley Online Library (2022)
  * [9] Backhaus, K., Erichson, B., Weiber, R.: Fortgeschrittene multivariate Analysemethoden: eine anwendungsorientierte Einführung. Springer-Verlag (2015)
  * [10] Bastian, M., Heymann, S., Jacomy, M.: Gephi: an open source software for exploring and manipulating networks. In: Proceedings of the international AAAI conference on web and social media. vol. 3, pp. 361–362 (2009)
  * [11] Baur, M., Benkert, M., Brandes, U., Cornelsen, S., Gaertler, M., Köpf, B., Lerner, J., Wagner, D.: Visone software for visual social network analysis. In: International Symposium on Graph Drawing. pp. 463–464. Springer (2001)
  * [12] Beck, F., Burch, M., Diehl, S., Weiskopf, D.: A taxonomy and survey of dynamic graph visualization. Computer Graphics Forum 36(1), 133–159 (2017)
  * [13] Behrisch, M., Bach, B., Henry Riche, N., Schreck, T., Fekete, J.D.: Matrix reordering methods for table and network visualization. In: Computer Graphics Forum. vol. 35, pp. 693–716. Wiley Online Library (2016)
  * [14] Bennett, C., Ryall, J., Spalteholz, L., Gooch, A.: The aesthetics of graph visualization. In: Proc. of the Eurographics Conference on Computational Aesthetics in Graphics, Visualization and Imaging. p. 57–64. The Eurographics Association (2007)
  * [15] Bollobás, B., Borgs, C., Chayes, J.T., Riordan, O.: Directed scale-free graphs. In: SODA. vol. 3, pp. 132–139 (2003)
  * [16] Boneau, C.A.: The effects of violations of assumptions underlying the t test. Psychological bulletin 57(1), 49 (1960)
  * [17] Bonferroni, C.: Teoria statistica delle classi e calcolo delle probabilita. Pubblicazioni del R Istituto Superiore di Scienze Economiche e Commericiali di Firenze 8, 3–62 (1936)
  * [18] Bortz, J.: Statistik: Für Sozialwissenschaftler. Springer-Verlag (2013)
  * [19] Bostock, M., Ogievetsky, V., Heer, J.: D3 data-driven documents. IEEE Trans. on Visualization and Computer Graphics 17(12), 2301–2309 (2011)
  * [20] Box, G.E., Cox, D.R.: An analysis of transformations. Journal of the Royal Statistical Society: Series B (Methodological) 26(2), 211–243 (1964)
  * [21] Brandes, U., Corman, S.R.: Visual unrolling of network evolution and the analysis of dynamic discourse. Information Visualization 2(1), 40–50 (2003)
  * [22] Brandes, U., Mader, M.: A quantitative comparison of stress-minimization approaches for offline dynamic graph drawing. In: International Symposium on Graph Drawing. pp. 99–110. Springer (2011)
  * [23] Collberg, C., Kobourov, S., Nagra, J., Pitts, J., Wampler, K.: A system for graph-based visualization of the evolution of software. In: Proceedings of the 2003 ACM symposium on Software visualization. pp. 77–ff (2003)
  * [24] Crnovrsanin, T., Chu, J., Ma, K.L.: An incremental layout method for visualizing online dynamic graphs. J. Graph Algorithms Appl. 21(1), 55–80 (2017)
  * [25] Di Giacomo, E., Didimo, W., Montecchiani, F., Tappini, A.: A user study on hybrid graph visualizations. In: International Symposium on Graph Drawing and Network Visualization. pp. 21–38. Springer (2021)
  * [26] van den Elzen, S., Holten, D., Blaas, J., van Wijk, J.J.: Dynamic network visualization withextended massive sequence views. IEEE transactions on visualization and computer graphics 20(8), 1087–1099 (2013)
  * [27] Erten, C., Harding, P.J., Kobourov, S.G., Wampler, K., Yee, G.: Graphael: Graph animations with evolving layouts. In: International Symposium on Graph Drawing. pp. 98–110. Springer (2003)
  * [28] Erten, C., Harding, P.J., Kobourov, S.G., Wampler, K., Yee, G.: Exploring the computing literature using temporal graph visualization. In: Visualization and Data Analysis 2004. vol. 5295, pp. 45–56. SPIE (2004)
  * [29] Filipov, V., Arleo, A., Miksch, S.: Exploratory user study on graph temporal encodings. In: 2021 IEEE 14th Pacific Visualization Symposium (PacificVis). pp. 131–135. IEEE (2021)
  * [30] Garnier, Simon, Ross, Noam, Rudis, Robert, Camargo, Pedro, A., Sciaini, Marco, Scherer, Cédric: viridis - Colorblind-Friendly Color Maps for R, r package version 0.6.2
  * [31] Ghani, S., Elmqvist, N., Yi, J.S.: Perception of Animated Node-Link Diagrams for Dynamic Graphs. Computer Graphics Forum (2012)
  * [32] Ghoniem, M., Fekete, J.., Castagliola, P.: A comparison of the readability of graphs using node-link and matrix-based representations. In: IEEE Sym. on Information Visualization. pp. 17–24 (2004)
  * [33] Gleicher, M., Albers, D., Walker, R., Jusufi, I., Hansen, C.D., Roberts, J.C.: Visual Comparison for Information Visualization. Information Visualization SAGE 10(4), 289–309 (Oct 2011)
  * [34] Hagberg, A., Conway, D.: Networkx: Network analysis with python (2020)
  * [35] Hagberg, A., Swart, P., S Chult, D.: Exploring network structure, dynamics, and function using networkx. Tech. rep., Los Alamos National Lab.(LANL), Los Alamos, NM (United States) (2008)
  * [36] Harris, C.R., Millman, K.J., van der Walt, S.J., Gommers, R., Virtanen, P., Cournapeau, D., Wieser, E., Taylor, J., Berg, S., Smith, N.J., Kern, R., Picus, M., Hoyer, S., van Kerkwijk, M.H., Brett, M., Haldane, A., del Río, J.F., Wiebe, M., Peterson, P., Gérard-Marchant, P., Sheppard, K., Reddy, T., Weckesser, W., Abbasi, H., Gohlke, C., Oliphant, T.E.: Array programming with NumPy. Nature 585(7825), 357–362 (Sep 2020)
  * [37] Hedderich, J., Sachs, L.: Angewandte Statistik. Springer (2016)
  * [38] Henry, N., Fekete, J.D.: Matlink: Enhanced matrix visualization for analyzing social networks. In: IFIP Conference on Human-Computer Interaction. pp. 288–302. Springer (2007)
  * [39] Javed, W., Elmqvist, N.: Exploring the design space of composite visualization. In: IEEE Pacific Visualization Symposium. pp. 1–8 (2012)
  * [40] Kerracher, N., Kennedy, J., Chalmers, K.: The Design Space of Temporal Graph Visualisation. In: Elmqvist, N., Hlawitschka, M., Kennedy, J. (eds.) EuroVis \- Short Papers. The Eurographics Association (2014)
  * [41] Linhares, C.D., Ponciano, J.R., Paiva, J.G.S., Travençolo, B.A., Rocha, L.E.: A comparative analysis for visualizing the temporal evolution of contact networks: a user study. Journal of Visualization 24(5), 1011–1031 (2021)
  * [42] Linhares, C.D., Travençolo, B.A., Paiva, J.G.S., Rocha, L.E.: Dynetvis: a system for visualization of dynamic networks. In: Proceedings of the symposium on applied computing. pp. 187–194 (2017)
  * [43] Miksch, S., Aigner, W.: A matter of time: Applying a data–users–tasks design triangle to visual analytics of time-oriented data. Computers & Graphics 38, 286 – 290 (2014)
  * [44] Okoe, M., Jianu, R., Kobourov, S.: Node-link or adjacency matrices: Old question, new insights. IEEE Trans. on Visualization and Computer Graphics 25(10), 2940–2952 (2019)
  * [45] Okoe, M., Jianu, R., Kobourov, S.: Revisited experimental comparison of node-link and matrix representations. In: Frati, F., Ma, K.L. (eds.) Graph Drawing & Network Visualization. pp. 287–302. Springer International Publishing (2018)
  * [46] Posten, H.O.: Robustness of the two-sample t-test. In: Robustness of statistical methods and nonparametric statistics, pp. 92–99. Springer (1984)
  * [47] Purchase, H., Carrington, D., Allder, J.A.: Empirical evaluation of aesthetics-based graph layout. Empirical Software Engineering 7 (2002)
  * [48] Purchase, H.C.: The effects of graph layout. In: Proc. of the Australasian Conference on Computer Human Interaction. p. 80. IEEE Computer Society (1998)
  * [49] Purchase, H.C., Hoggan, E., Görg, C.: How important is the “mental map”?–an empirical investigation of a dynamic graph layout algorithm. In: International Symposium on Graph Drawing. pp. 184–195. Springer (2006)
  * [50] Ren, D., Marusich, L.R., O’Donovan, J., Bakdash, J.Z., Schaffer, J.A., Cassenti, D.N., Kase, S.E., Roy, H.E., Lin, W.y.S., Höllerer, T.: Understanding node-link and matrix visualizations of networks: A large-scale online experiment. Network Science 7(2), 242–264 (2019)
  * [51] Rousseeuw, P.J., Croux, C.: Alternatives to the median absolute deviation. Journal of the American Statistical association 88(424), 1273–1283 (1993)
  * [52] Rufiange, S., Melançon, G.: Animatrix: A matrix-based visualization of software evolution. In: 2014 second IEEE working conference on software visualization. pp. 137–146. IEEE (2014)
  * [53] Schminder, E., Ziegler, M., Danay, E., Beyer, L., Bühner, M.: Is it really robust? reinvestigating the robustness of anova against violations of the normal distribution. Methodology – European Research Journal of Methods for the Behavioral and Social Sciences 6(4), 147–151 (2010)
  * [54] Simonetto, P., Archambault, D., Kobourov, S.: Event-based dynamic graph visualisation. IEEE Transactions on Visualization and Computer Graphics 26(7), 2373–2386 (2018)
  * [55] Tufte, E.R.: The visual display of quantitative information. Quantitative Information p. 13 (1983)
  * [56] Vallat, R.: Pingouin: statistics in python. Journal of Open Source Software 3, 1026 (2018)
  * [57] Virtanen, P., Gommers, R., Oliphant, T.E., Haberland, M., Reddy, T., Cournapeau, D., Burovski, E., Peterson, P., Weckesser, W., Bright, J., van der Walt, S.J., Brett, M., Wilson, J., Millman, K.J., Mayorov, N., Nelson, A.R.J., Jones, E., Kern, R., Larson, E., Carey, C.J., Polat, İ., Feng, Y., Moore, E.W., VanderPlas, J., Laxalde, D., Perktold, J., Cimrman, R., Henriksen, I., Quintero, E.A., Harris, C.R., Archibald, A.M., Ribeiro, A.H., Pedregosa, F., van Mulbregt, P., SciPy 1.0 Contributors: SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods 17, 261–272 (2020)
  * [58] Weiß, C., Weiß, C.: Basiswissen medizinische statistik, vol. 4. Springer (2005)
  * [59] Yoghourdjian, V., Archambault, D., Diehl, S., Dwyer, T., Klein, K., Purchase, H.C., Wu, H.Y.: Exploring the limits of complexity: A survey of empirical studies on graph visualisation. Visual Informatics 2(4), 264 – 282 (2018)

## Appendix

In this Appendix we include supplemental results which complement our
discussion in the paper. The study and downloadable material is accessible
online: https://graph-survey.herokuapp.com/.

The study initially received 76 submissions. We introduced a control question
every 12 the filter out participants trying to game the study, resulting in 8
being removed.

| Low-level | High-level
---|---|---
T1 |  At which time step is the relationship between {source} and {target} introduced for the first time? |  At which time step does the clique between {nodes} appear for the first time?
T2 |  Sum up the changes (additions and removals) of {node}’s degree across all time steps. |  Calculate change of the clique’s size between {nodes} across all time steps.
T3 |  At which time step does the node {node} have its highest degree? |  Consider the set of nodes {nodes}. Find the size of the largest maximal clique across all the time steps between the given nodes.
Table 1: Example questions, per task (rows) and entity type (columns). Target
nodes for low-level tasks were chosen randomly during the study design;
cliques were also introduced artificially as explained in Section 4.2 of the
paper.

(a) Differences in response times between node-link and matrix network
encodings per task.

(b) Accuracy (in percent) for node-link and matrix representations per task.

Figure 1: Response times and correct responses between network encodings and
tasks for H1: Matrices have lower response times and higher accuracy for all
tasks compared to node-link diagrams, regardless of the temporal encoding.

(a) Differences in response times between temporal encodings per task.

(b) Accuracy (in percent) for temporal encodings per task.

Figure 2: Response times and accuracy between network encodings and tasks for
H2: From all temporal encoding techniques, superimposition has the lowest
response times and highest accuracy, regardless of the structural
representation.

(a) Differences in response times between interaction groups per task.

(b) Accuracy (in percent) for interaction groups per task.

Figure 3: Response times and accuracy between groups (A - no interaction; B -
interaction) and tasks for H3: Providing interaction techniques increases the
response times but not the accuracy.

(a) Differences in response times between network encodings and entity type
per task.

(b) Accuracy (in percent) for adjacency matrices and entity type per task.

Figure 4: Response times and accuracy between network representations and
entity types (single - low-level; clique - high-level) and tasks for
H4:Matrices have lower response times and higher accuracy for tasks on low-
level entities and node-link diagrams have lower response times and higher
accuracy for tasks on higher-level entities, regardless oft he temporal
encoding. Matrices have lower response times and higher accuracy for tasks on
low-level entities and node-link diagrams have lower response times and higher
accuracy for tasks on higher-level entities, regardless oft he temporal
encoding.

(a) Differences in response times between network representations and temporal
encodings.

(b) Accuracy (in percent) for different combinations of network
representations and temporal encodings.

Figure 5: Response times and accuracy between network representations and
temporal encodings for H5: The combination of matrices with superimposition
results in the lowest response times and highest accuracy compared to other
combinations of network structural and temporal encoding.

In the following we provide the results of our Analysis of Variance (ANOVA
tests for each hypothesis investigating the influence of the independent
variables in our study (task type, network and temporal encoding, and group)
on the dependent variable time, outlining the significance levels for each.
Column “Df” refers to the degrees of freedom for the independent variable
(number of levels in the variable minus 1); “Sum Sq” displays the sum of
squares (a.k.a. the total variation between the group means and the overall
mean); “Mean Sq” is the mean of the sum of the squares, calculated by dividing
the sum of squares by the degrees of freedom for each parameter; “F Value”
column is the test statistic from the F-test. It is the mean square of each
independent variable divided by the mean square of the residuals: the larger
the value, the more likely it is that the variation caused by the independent
variable is real and not due to chance. Finally, “Pr($>$F)” is the p-value of
the F-test statistics, and the “Significance” column reports a symbol for
quick visual reference about statistical significance.

Response Time | Df | Sum Sq | Mean Sq | F value | Pr(>F) | Significance
---|---|---|---|---|---|---
network_enc | 1 | 2138106 | 2138106 | 98.0501 | <2.2e-16 | ***
task_type | 2 | 3523697 | 1761849 | 80.7955 | <2.2e-16 | ***
group | 1 | 338934 | 338934 | 15.543 | 8.24E-05 | ***
network_enc:task_type | 2 | 303223 | 151612 | 6.9527 | 0.0009704 | ***
network_enc:group | 1 | 30489 | 30489 | 1.3982 | 0.2371122 |
task_type:group | 2 | 26350 | 13175 | 0.6042 | 0.5465832 |
network_enc:task_type:group | 2 | 9345 | 4672 | 0.2143 | 0.807143 |
Residuals | 3250 | 70870339 | 21806 |  |  |
Signif. codes: 0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1
Table 2: ANOVA table for H1 showing the influence of the independent variables on the dependent variable “time” together with their interaction effects. Response Time | Df | Sum Sq | Mean Sq | F value | Pr(>F) | Significance
---|---|---|---|---|---|---
network_enc | 1 | 1357060 | 1357060 | 61.7501 | 5.25E-15 | ***
task_type | 3 | 213354 | 71118 | 3.2361 | 0.02134 | *
group | 1 | 346104 | 346104 | 15.7487 | 7.39E-05 | ***
network_enc:task_type | 3 | 75322 | 25107 | 1.1425 | 0.33047 |
network_enc:group | 1 | 2920 | 2920 | 0.1329 | 0.7155 |
task_type:group | 3 | 5082 | 1694 | 0.0771 | 0.97239 |
network_enc:task_type:group | 3 | 36402 | 12134 | 0.5521 | 0.64671 |
Residuals | 3262 | 71687780 | 21977 |  |  |
Signif. codes: 0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1
Table 3: ANOVA table for H2 showing the influence of the independent variables on the dependent variable “time” together with their interaction effects. Response Time | Df | Sum Sq | Mean Sq | F value | Pr(>F) | Significance
---|---|---|---|---|---|---
network_enc | 1 | 867172 | 867172 | 9.1825 | 2.46E-03 | **
task_type | 3 | 219958 | 73319 | 0.7764 | 0.507051 |
group | 1 | 1537636 | 1537636 | 16.282 | 5.58E-05 | ***
network_enc:task_type | 3 | 65818 | 21939 | 0.2323 | 0.873916 |
network_enc:group | 1 | 255 | 255 | 0.0027 | 0.958563 |
task_type:group | 3 | 44034 | 14678 | 0.1554 | 0.926229 |
network_enc:task_type:group | 3 | 126840 | 42280 | 0.4477 | 0.718939 |
Residuals | 3365 | 317783541 | 94438 |  |  |
Signif. codes: 0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1
Table 4: ANOVA table for H3 showing the influence of the independent variables on the dependent variable “time” together with their interaction effects. Response Time | Df | Sum Sq | Mean Sq | F value | Pr(>F) | Significance
---|---|---|---|---|---|---
network_enc | 1 | 1731835 | 1731835 | 30.8822 | 2.95E-08 | ***
task_type | 1 | 8841140 | 8841140 | 157.656 | <2.2E-16 | ***
group | 1 | 1036281 | 1036281 | 18.4791 | 1.77E-05 | ***
network_enc:task_type | 1 | 2355561 | 2355561 | 42.0046 | 1.04E-10 | ***
network_enc:group | 1 | 67782 | 67782 | 1.2087 | 2.72E-01 |
task_type:group | 1 | 342754 | 342754 | 6.112 | 0.01348 | *
network_enc:task_type:group | 1 | 15681 | 15681 | 0.2796 | 0.59698 |
Residuals | 3377 | 189377703 | 56079 |  |  |
Signif. codes: 0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1
Table 5: ANOVA table for H4 showing the influence of the independent variables on the dependent variable “time” together with their interaction effects. Response Time | Df | Sum Sq | Mean Sq | F value | Pr(>F) | Significance
---|---|---|---|---|---|---
network_enc | 1 | 1357060 | 1357060 | 61.7501 | 5.25E-15 | ***
task_type | 3 | 213354 | 71118 | 3.2361 | 0.02134 | *
group | 1 | 346104 | 346104 | 15.7487 | 7.39E-05 | ***
network_enc:task_type | 3 | 75322 | 25107 | 1.1425 | 3.30E-01 |
network_enc:group | 1 | 2920 | 2920 | 0.1329 | 7.16E-01 |
task_type:group | 3 | 5082 | 1694 | 0.0771 | 0.97239 |
network_enc:task_type:group | 3 | 36402 | 12134 | 0.5521 | 0.64671 |
Residuals | 3262 | 71687780 | 21977 |  |  |
Signif. codes: 0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1
Table 6: ANOVA table for H5 showing the influence of the independent variables
on the dependent variable “time” together with their interaction effects.