11institutetext:  Department of Engineering, University of Perugia, Italy
11email:  {emilio.digiacomo,walter.didimo,fabrizio.montecchiani,
<EMAIL_ADDRESS>
# A User Study on Hybrid Graph Visualizations††thanks: This work is partially
supported by: $(i)$ MIUR, grant 20174LF3T8 “AHeAD: efficient Algorithms for
HArnessing networked Data”, $(ii)$ Dipartimento di Ingegneria - Università
degli Studi di Perugia, grants RICBA19FM: “Modelli, algoritmi e sistemi per la
visualizzazione di grafi e reti” and RICBA20EDG: “Algoritmi e modelli per la
rappresentazione visuale di reti”.

Emilio Di Giacomo  Walter Didimo
Fabrizio Montecchiani  Alessandra Tappini  (🖂)

###### Abstract

Hybrid visualizations mix different metaphors in a single layout of a network.
In particular, the popular NodeTrix model, introduced by Henry, Fekete, and
McGuffin in 2007, combines node-link diagrams and matrix-based representations
to support the analysis of real-world networks that are globally sparse but
locally dense. That idea inspired a series of works, proposing variants or
alternatives to NodeTrix. We present a user study that compares the classical
node-link model and three hybrid visualization models designed to work on the
same types of networks. The results of our study provide interesting
indications about advantages/drawbacks of the considered models on performing
classical tasks of analysis. At the same time, our experiment has some
limitations and opens up to further research on the subject.

##  1 Introduction

Many real-world networks, in a variety of application domains, exhibit a
heterogeneous structure with a double nature: they are globally sparse but
locally dense, i.e., they contain _clusters_ of highly connected nodes (also
called _communities_ in social network analysis) that are loosely connected to
each other (see, e.g., [29, 31, 50]). Examples include social and financial
networks [16, 26, 49, 58], as well as biological and information networks [28,
43].

(a) NodeLink

(b) ChordLink

(c) NodeTrix

(d) RCI-NodeTrix

Figure 1: The same clustered network with our four visualization models.

The visualization of such networks through classical node-link diagrams is
often unsatisfactory, due to the visual clutter caused by the high number of
edges in the dense portions of the network (Fig. 1(a)). To overcome this
limit, _hybrid visualizations_ have been proposed. A hybrid visualization
combines different graph visualization models in a unique drawing, with the
aim of conveying the high-level cluster structure of the network and, at the
same time, facilitating in the analysis of its communities. One of the seminal
ideas in this regard is the NodeTrix model, introduced by Henry, Fekete, and
McGuffin [35], which adopts a node-link diagram to represent the (sparse)
global structure of the network, and a matrix representation for denser
subgraphs identified and selected by the user (Fig. 1(c)). After the
introduction of NodeTrix, hybrid visualizations have become an emerging topic
in graph drawing and network visualization, and inspired an array of both
theoretical and application results (see, e.g., [7, 8, 9, 11, 14, 22, 23, 24,
33, 39, 41, 59]).

Contribution. Motivated by the growing interest in hybrid visualizations, this
paper focuses on network layouts with a given set of clusters, and addresses
two broad research questions: RQ1 – “Are hybrid visualizations more effective
than node-link diagrams for the visual analysis of clustered networks?”; RQ2 –
“When considering specific tasks of analysis, are there differences in terms
of response time or accuracy among different hybrid visualization models?”

To investigate these questions, we designed a user study that compares three
hybrid visualization models and the classical node-link model. Namely, we
considered two hybrid models that are designed to work on similar types of
networks: the aforementioned NodeTrix model [35] and the ChordLink model [9],
which represents clusters as chord diagrams instead of adjacency matrices
(Fig. 1(b)). Additionally, we considered the RCI-NodeTrix model [41], a
variant of NodeTrix that adopts independent orderings for the matrix rows and
columns so to reduce crossings between inter-cluster edges (Fig. 1(d)).

To the best of our knowledge, our study is the first that addresses research
question RQ1, and that considers RQ2 for hybrid visualizations that adopt
different styles to represent clusters. Our work is also motivated by open
questions from [9, 41], namely: [9] suggests to perform a user study to
compare ChordLink and other hybrid visualizations; [41] asks what is the
impact of reducing crossings between inter-cluster edges at the expenses of
independent row/column orderings in NodeTrix. The results of our study provide
some hints about the usefulness of hybrid visualizations in the execution of
topology-based tasks with respect to node-link diagrams. At the same time, our
experiment has some limitations and opens up to new research to further
investigate the subject.

The paper is structured as follows. Section 2 briefly surveys the scientific
literature related to our work. Section 3 explains in detail the design of our
user study and describes the rationale behind each of our choices. Section 4
discusses both the quantitative and qualitative results of our experiment, as
well as its limitations. Section 5 lists some future research directions. All
the experimental data are available at
http://mozart.diei.unipg.it/tappini/hybridUserStudy/.

##  2 Related Work

The focus of our work is on hybrid graph representations that mix different
visual metaphors to visually convey both the global structure of a sparse
network and its locally dense subgraphs. In this direction, Henry et al. [35]
introduce the NodeTrix model for social network analysis in one of the most
cited papers of the InfoVis conference [1]; the model is implemented in a
system where the user can select (dense) portions of a node-link diagram to be
represented as adjaceny matrices. NodeTrix visualizations have also been
exploited to analyze other real-world graphs, such as ontology graphs [11] and
brain networks [59].

Angori et al. [9] introduce the ChordLink model. Similarly to NodeTrix, this
model is designed to work in a system where the user can visually identify and
select clusters on a node-link diagram; differently from NodeTrix, the
selected cluster regions are represented as chord diagrams. ChordLink aims to
represent all edges as geometric links and to preserve the drawing outside
clusters by possibly duplicating nodes within a cluster (but each node can
only appear in at most one cluster, as for NodeTrix).

Our study focuses on comparing NodeTrix and ChordLink, as they are conceived
to work on networks with similar structure and within systems with similar
characteristics. Our study also considers the RCI-NodeTrix model [41], a
variant of NodeTrix that allows independent orderings of the rows and columns
in a matrix, to possibly reduce crossings between inter-cluster edges.

For social network analysis, the NodeTrix model has also been proposed with a
variant that considers “overlapping clusters”, i.e., where a node can occur in
multiple clusters at the same time [33]. This kind of node duplication may
help in the execution of community-related tasks, but sometimes interferes
with other graph readability tasks.

Batagelj et al. [14] propose a system where the user can choose to represent
each cluster according to a desired drawing style. Differently from NodeTrix
and ChordLink, this system is designed to automatically compute a set of
clusters that guarantees desired properties (e.g., planarity) for the graph of
clusters and adopts an orthogonal drawing convention (instead of a straight-
line node-link diagram) to represent the outside of the clusters. Hybrid
visualizations have also been exploited in the context of dynamic network
analysis (see, e.g., [15, 32, 55]). We finally mention several theoretical
results on hybrid visualizations that concentrate on the complexity of
minimizing the number of inter-cluster edge crossings (see, e.g., [6, 7, 8,
17, 22, 23, 24, 39, 41]).

Our work falls into the research line devoted to the design of user
experiments in graph drawing and network visualization. We recall here the
contributions that are mainly related to our study; refer to [19] for a
comprehensive survey on the subject. There is a series of works that compare
node-link diagrams with matrix-based representations (see, e.g., [3, 4, 20,
25, 30, 36, 47, 48]). An insight that seems to emerge from these studies is
that node-link diagrams have usually better performance on topology and
connectivity tasks when graphs are not too large and dense, while matrices
perform better on group tasks. Our study does not aim to further compare node-
link and matrix representations, but rather to investigate hybrid
visualizations that mix these two, or others, drawing conventions.

In the context of hybrid graph visualizations, Henry and Fekete [34] conduct a
user study on MatLink, a model that combines adjacency matrices overlaid with
node-link diagrams using curvature for the links. They find that MatLink
outperforms the two individual metaphors (node-link diagrams and adjacency
matrices) for most of the considered tasks, including path-related tasks,
where matrices are usually worse than node-link. However, differently from our
study, [34] does not focus on the visualization of clustered networks. Henry
et al. [33] present a user study aimed to understand whether node duplication
for non-disjoint clusters improves the performance of NodeTrix for some types
of tasks. Since the majority of hybrid visualizations are designed to deal
with disjoint clusters, our study focuses on this setting; moreover, we
consider tasks that are mostly different from those addressed in [33].

##  3 Study Design

This section describes in detail the design of our user study. Our target
population are researchers and analysts (including practitioners, academics,
and students) that make use of network visualization to accomplish tasks of
analysis on real-world networks. In the following we discuss the visualization
models, the tasks and the hypothesis, the stimuli, and the experimental
procedure.

###  3.1 Visualization Models

The conditions compared in our study are four different models for the
visualization of undirected clustered networks, where subsets of nodes are
grouped into clusters (see Fig. 1 for an illustration). We consider networks
with neither self-loops nor multiple edges. An edge connecting two nodes in
the same cluster is an _intra-cluster edge_ ; every other edge is an _inter-
cluster edge_. The models are:

– NodeLink (NL). This is the classical node-link model, where nodes are
represented as small disks and edges are straight-line segments connecting
their end-nodes. In this model, we visually highlight each cluster through a
colored convex region that includes all the nodes in the cluster.

– ChordLink (CL). This model has been introduced in [9, 10]. Nodes outside
clusters and inter-cluster edges are drawn as in the NodeLink model. Clusters
are represented as chord diagrams. A node in a cluster may have multiple
copies, each represented as a colored circular arc along the circumference of
the chord diagram; all copies of the same node have the same color. An intra-
cluster edge is drawn as a “ribbon” connecting two of the copies representing
its end-nodes.

– NodeTrix (NT). This is the model introduced in [35]; each cluster $C$ of
size $n$ is represented by a (symmetric) $n\times n$ adjacency matrix. Nodes
outside clusters, and edges between them, are drawn as in NodeLink. An inter-
cluster edge having an end-node $v$ in a cluster $C$ is drawn as a curve
incident to the row or to the column associated with $v$, on one of the sides
of the matrix representing $C$.

– RCI-NodeTrix (RC). This is a variant of the NodeTrix model, introduced in
[40, 41]. The difference with the NodeTrix model is that in each adjacency
matrix, the row and the column associated with the same node may have
different indices, in order to save some crossings between inter-cluster
edges. As a consequence the matrices may not be symmetric.

Rationale. Among the various types of hybrid visualizations described in the
literature, we selected NT and CL as they are designed to work similarly
within visualization systems for the analysis of real-world networks. In
particular, we exploited the system in [9], which implements both these models
in a unique interface, where the implementation of NT reflects that given in
[2] by the authors of [35]. The system in [9] allows direct support for
clustered drawings in the NL model and makes it possible to create drawings in
all the supported models by defining the same set of clusters on the same
node-link diagram. For the purposes of our experiment, we enriched the system
with the RC model.

###  3.2 Tasks

We defined six different tasks, listed in Table 1. We classify each task
according to the taxonomy by Lee et al. [37], which we refer to as LeeTax.
Moreover, following the taxonomy by Amar et al. [5], which we refer to as
AmarTax, we indicate the low-level visual analytics operations needed to
execute each task.

Task |  LeeTax |  AmarTax
---|---|---
T1. Is there an edge that links the two highlighted nodes? |  topology-based (adjacency) |  retrieve value
T2. Which of the two highlighted nodes has higher degree? |  topology-based (adjacency) |  retrieve value; sort
T3. Is there a path of length at most $k$ that connects the two highlighted nodes? |  topology-based (connectivity) |  retrieve value; compute derived value; filter
T4. Which of the following three node labels appear in the highlighted portion of the network? |  attribute-based (on the nodes) |  retrieve value; filter
T5. What is the denser∗ cluster between the two highlighted? |  overview |  filter; compute derived value; sort
T6. How many edges directly connect the two highlighted parts of the drawing? |  overview |  filter; compute derived value
∗The cluster density is the ratio between the number of edges and the number
nodes in a cluster
Table 1: Tasks used in our study.

Rationale. We designed the user study with a set of tasks that requires to
explore the drawing locally and globally. Moreover, each task is easy to
explain, it can be executed in a reasonably short time, and it can be easily
measured. Concentrating on representative tasks is a common approach for this
kind of experiments (e.g., [52]), which supports generalizability to more
complex tasks that include these representatives as subroutines. Most of our
tasks have already been used in previous graph visualization user studies
(e.g., [48, 51, 53, 56]) and they cover all task categories in the taxonomy of
Lee et al. [37], with the exception of the browsing category. We excluded the
latter because it requires the users to interact with the visualization and we
decided to avoid interaction to keep the test execution as simple as possible
and avoid possible confounding factors. According to the top-level task
classification by Burch et al. [19], all our tasks are _interpretation tasks_
, as our goal is to evaluate the differences of the considered visualization
models in terms of readability, understandability, and effectiveness. About
task T5, we point out that there are two commonly used definitions for the
density of a graph with $n$ nodes and $m$ edges: $d_{1}=\frac{m}{n}$ and
$d_{2}=\frac{2m}{n(n-1)}$. We adopted definition $d_{1}$ for two reasons: (a)
it is simpler to explain to a user; (b) according to previous research work
[46], $d_{1}$ is a better descriptor of the complexity of real-world networks.
Indeed, the visual perception of the density of a cluster region is affected
by the number of nodes in the cluster; if a drawing contains two clusters with
different sizes, the largest one may be perceived as a denser portion of the
drawing, even if it has lower density according to $d_{2}$.

###  3.3 Hypotheses

Similarly to previous works (e.g., [33, 48]), we define our hypotheses based
on tasks, structuring them according to the task categories of LeeTax.

H1: On topology-based tasks (T1, T2, T3), we expect that NodeLink outperforms
hybrid visualizations in terms of response time. On the other hand, we expect
hybrid visualizations to have a lower error rate than NodeLink, and ChordLink
to behave better than NodeTrix and RCI-NodeTrix.

H2: On attribute-based tasks (T4), we expect NodeTrix and RCI-NodeTrix to
outperform the other two models in terms of response time and error rate.

H3: On overview tasks (T5, T6), we expect hybrid visualizations to perform
better than NodeLink in terms of both response time and error rate. Among the
hybrid visualizations, we expect NodeTrix and RCI-NodeTrix to be better than
ChordLink, especially when one needs to estimate cluster density.

Rationale. About H1, our expectations in terms of response time are motivated
by the fact that NodeLink is quite intuitive and widely used. Moreover, hybrid
visualizations intrinsically require to switch from a visualization metaphor
to another during the visual exploration, which may represent a cognitive
effort. Concerning the error rate, we think that, by reducing the visual
clutter, hybrid visualizations may be able to avoid visual ambiguities (such
as edges that are almost collinear) and therefore may better support topology-
based tasks. Also, since topology-based tasks are known to be harder when
dealing with matrices, we expect ChordLink to have better performance than
NodeTrix and RCI-NodeTrix in terms of error rate. About H2, we believe that
placing labels on a matrix side is more effective than placing them around
chord diagrams or near nodes in a node-link diagram. In chord diagrams labels
may be harder to read due to their rotation, while in node-link diagrams they
may be hidden by edges. About H3, we expect hybrid visualizations to behave
better than NodeLink due to their capability to represent clusters more
clearly. For tasks that require to estimate cluster density, both NodeTrix and
RCI-NodeTrix have the advantage that the proportion between black (edges) and
white (non-edges) cells immediately conveys the density of a cluster; the same
estimation in ChordLink is more difficult due to node duplication, which may
give the impression that a cluster is sparser than it actually is.

###  3.4 Stimuli

Our experimental objects are three real-word networks of small/medium size.
The first one, weavers, is an animal social network with 64 nodes and 177
edges, describing the interactions of a colony of weavers in the usage of
nests [27, 54]. The second one, e.coli, is a biological network with 97 nodes
and 212 edges that describes transcriptional interactions in the Escherichia
coli bacterium [44]. The third one, dblp, is a co-authorship network obtained
from the DBLP repository [38] by searching for the keyword “network
visualization” and considering only the largest connected component, which has
118 nodes and 322 edges.

For each of the four visualization models described in Section 3.1, we
produced a diagram of the three networks above. The diagrams for the NodeLink
model are computed through the force-directed algorithm available in the D3
library [18]. Starting from these drawings, we defined some geometric clusters
with the technique based on the $K$-means algorithm [42] described in [9]. As
explained in Section 3.1, the system presented in [9] is then used to compute
the diagrams in the ChordLink, NodeTrix, and RCI-NodeTrix models with the same
sets of clusters. Further details about the stimuli creation are in Section
0.A.1.

Each of the $12$ stimuli obtained by applying each of the $4$ conditions
(models) to the $3$ experimental objects (networks) is used in all of the $6$
tasks described in Section 3.2, for a total of $4\times 3\times 6=72$ trials.
For T1, T2, and T3, we highlighted the node labels with a yellow background;
to help the user to locate the nodes, we also put a red cross close to the
clusters containing them. For T4 and T6, we highlighted the regions of
interest by enclosing them inside a colored polygonal area. Finally, for T5 we
indicated the two clusters of interest with large red labels. The trials for
the network weavers are shown in Section 0.A.3.

Rationale. The visualization models that we compare are suitable for networks
with up to few thousand nodes and edges, while for significantly larger
networks ad-hoc techniques are required that typically reduce the amount of
displayed information. The choice of using networks with few hundred elements
avoids an excessive burden for the participants. Namely, we wanted that each
trial could be executed in a reasonable amount of time without an excessive
fatigue and that the whole test could be completed in about 30 minutes.
Further, since we decided to show static images (without zoom), the whole
picture of the network should be displayed with a level of zoom that keeps the
labels readable. Since hybrid visualizations are mainly used to visualize
networks that are globally sparse but locally dense, we selected three
networks that exhibit this structure. Moreover, we designed the specific
trials so that the user was required to explore both the sparse parts of the
network, represented by the node-link metaphor, and the dense parts,
represented in different ways depending on the model.

###  3.5 Experimental Setting and Procedure

We designed a between-subject experiment where each participant was exposed to
one of the four conditions and hence to $18$ trials. The users executed the
test fully on-line. The questionnaire was prepared using the LimeSurvey tool
(https://www.limesurvey.org/) and is structured as follows. First, some
information about the user are collected, namely: gender, age, educational
level, expertise in graph visualization, screen size, and possible color
vision deficiency. Then, the visualization model to be assigned to the user is
decided in a round robin fashion. Based on this assignment, a video tutorial
is presented, followed by a training phase in which the user has to answer a
trial for each task with an explanatory feedback in case of wrong answer.
Next, the $18$ trials are presented in random order. Finally, the user is
asked for some qualitative feedback: two Likert scale questions about the
aesthetic quality of the drawings and about the easiness of the questions,
plus an optional free comment. While no time limit was given to complete the
test, the participants were asked to answer each question as fast as they
could but, at the same time, trying to be accurate. For each user, we
collected the answers and the time spent on each question. We recruited the
participants with announcements to the gdnet, ieee_vis, infovis mailing lists
and to the computer engineering students of the universities of Perugia and
Roma Tre. The actual experiment was preceded by a pilot study (see Section
0.A.2).

Rationale. As previously explained, exposing the users to all four conditions
would imply each user solving $72$ trials. We believe that keeping the same
level of attention in such a long experiment is difficult, and may cause many
participants prematurely quitting the test. Besides such undesired fatigue
effect, a within-subject design would also imply that each user sees the same
experimental object $24$ times, which makes it difficult to avoid the learning
effect. Hence, we adopted a between-subject design, where each participant is
exposed to only one condition. This choice limited the number of trials per
user to $18$, thus mitigating both the fatigue and the learning effect, which
is further counteracted by presenting the trials in a random order. Finally,
since the test also includes a video tutorial and a training phase to make the
user familiar with the given visualization model, an additional advantage of
the between-subject design is that these phases can be focused on one model
only. About the execution of the experiment, we opted for a fully on-line test
for two reasons: (i) the difficulties to perform a controlled in-person
experiment due to the COVID-19 pandemic; (ii) the possibility of recruiting a
larger number of participants that better represent our target population,
through announcements on the aforementioned mailing lists.

##  4 Study Results

Participants. We collected questionnaires from 89 participants. We discarded
seven tests for various reasons, reported in Section 0.B.2. Of the remaining
82 tests, 19 were for ChordLink and 21 for each of the other models. Regarding
the participants, 66 (80.49%) were males, 15 (18.29%) were females, and 1
(1.22%) preferred not to answer. The majority of them (82.72%) were aged below
40. 85.37% of the participants has at least a Bachelor’s degree, with 34.15%
of them having a doctoral degree. 62.2% of the participants declared a medium
or high familiarity with graph visualization and 68.29% used a screen of size
at least 15”. Fig. 9 in Section 0.B.1 summarizes the data about the
participants.

Quantitative Results. We compared the performance of the four models in terms
of error rate and response time. For T1–T5, the error rate of a user is the
ratio between the number of wrong answers and the total number of questions.
Recall that there are three questions per task and that in T4 the user has to
find three labels for each question. About T6, the error on a question is
computed as $1-\frac{1}{1+|u-r|}$, where $u$ is the value given by the user
and $r$ is the correct value; the error rate for T6 is the average of the
errors on the three questions of the task.

|  | Kruskal-Wallis | Pairwise comparisons ($p$-value)
---|---|---|---
Task |  Models ranked by average error rate |  $H(3)$ |  $p$-value |  NL-CL |  NL-NT |  NL-RC |  CL-NT |  CL-RC |  NT-RC
T1 |  CL (0.175), NL (0.191), RC (0.254), NT (0.350) |  8.471 |  0.037 |  1.000 |  0.179 |  1.000 |  0.036 |  1.000 |  0.549
T2 |  CL (0.140), NL (0.143), RC (0.191), NT (0.238) |  2.419 |  0.490 |  - |  - |  - |  - |  - |  -
T3 |  CL (0.140), RC (0.143), NT (0.270), NL (0.333) |  10.882 |  0.012 |  0.035 |  0.788 |  0.024 |  1.000 |  1.000 |  1.000
T4 |  CL (0.105), NT (0.143), RC (0.206), NL (0.302) |  6.703 |  0.082 |  - |  - |  - |  - |  - |  -
T5 |  NT (0.270), NL (0.302), CL (0.386), RC (0.400) |  2.407 |  0.492 |  - |  - |  - |  - |  - |  -
T6 |  RC (0.350), CL (0.386), NT (0.418), NL (0.429) |  0.478 |  0.924 |  - |  - |  - |  - |  - |  -
|  | Kruskal-Wallis | Pairwise comparisons ($p$-value)
Task |  Models ranked by average response time |  $H(3)$ |  $p$-value |  NL-CL |  NL-NT |  NL-RC |  CL-NT |  CL-RC |  NT-RC
T1 |  NL (16.64), NT (19.91), RC (23.47), CL (26.12) |  20.084 |  $<$0.001 |  0.000 |  1.000 |  0.031 |  0.016 |  0.832 |  0.720
T2 |  NL (25.23), CL (36.35), NT (37.63), RC (39.95) |  12.632 |  0.006 |  0.058 |  0.061 |  0.006 |  1.000 |  1.000 |  1.000
T3 |  NL (24.58), RC (39.56), NT (42.68), CL (47.69) |  19.533 |  $<$0.001 |  0.000 |  0.005 |  0.011 |  1.000 |  1.000 |  1.000
T4 |  NT (35.88), RC (37.04), NL (42.36), CL (50.60) |  9.793 |  0.020 |  1.000 |  0.579 |  1.000 |  0.018 |  0.143 |  1.000
T5 |  NL (29.71), NT (37.77), CL (42.30), RC (44.24) |  3.657 |  0.301 |  - |  - |  - |  - |  - |  -
T6 |  RC (31.56), NL (34.07), CL (35.83), NT (38.27) |  1.265 |  0.737 |  - |  - |  - |  - |  - |  -
Table 2: Results for error rate (top) and response time (bottom) for each
task.

By performing the Shapiro-Wilk test with significance level $\alpha{=}0.05$,
we found that data were not normally distributed. Hence, we performed the non-
parametric Kruskal–Wallis test with significance level $\alpha{=}0.05$, which
is suitable for comparing multiple independent samples. We finally performed
post-hoc pairwise comparisons by using Bonferroni corrections. (See also [21,
57].)

Table 2 summarizes the results of our analysis both for the error rate (top)
and for the response time (bottom). For each task, we list the models sorted
by increasing values of the average error rate or response time. These values
are shown in parentheses together with the model. Table 2 reports the
statistic (column $H(3)$) and the $p$-value of the Kruskal-Wallis test.
Finally, we report the adjusted (after Bonferroni corrections) significance
for each pairwise comparison. Values that are statistically significant are
highlighted in bold. Figs. 2 and 3 depict the box-plots of the error rate and
response time for all the tasks.

Figure 2: Error rate aggregated by task.

Figure 3: Response time aggregated by task.

Figure 4: Qualitative results.

Qualitative Results. At the end of the test, we presented to the users the
following questions: (F1) _“How much do you like the diagrams you have seen?”_
and (F2) _“How easy did you find answering the test questions?”_. The answers,
given in a 5-point Likert scale, are summarized in Fig. 4, where we also
report the answer distributions as box-plots; we assigned a score from 1
(lowest) to 5 (highest) to each answer. While there is no statistically
significant difference among the models, about (F1) NodeLink received the
highest percentage of strongly negative appreciations and NodeTrix received
the highest percentage of strongly positive appreciations, although with high
variance. About (F2), the easiness of answering was judged medium on average
for all the models. In Section 0.B.3 we discuss the free comments received by
the participants.

Discussion and Limitations. The following highlights summarize our results:

– Hypothesis H1 is largely supported by the results in terms of response time.
More precisely, NodeLink behaves better (with statistical significance) than:
ChordLink and RCI-NodeTrix for task T1; RCI-NodeTrix for task T2; and for all
hybrid models for T3. In particular, the slower performance of RCI-NodeTrix
with respect to NodeLink for all the topology-based tasks seems to confirm the
difficulty pointed out by some participants about dealing with non-symmetric
matrices. In terms of error rate, H1 is partially supported. Indeed, while
there is no statistically significant difference for task T2, we observe that
for task T3 both ChordLink and RCI-NodeTrix yield better accuracy than
NodeLink, and for task T1 ChordLink behaves better than NodeTrix. One may
wonder why the same behavior is not observable between ChordLink and RCI-
NodeTrix on task T1; our interpretation is that this might depend on the
smaller number of crossings that RCI-NodeTrix usually causes between edges
that are incident to the matrices with respect to NodeTrix.

– Hypothesis H2 is also partially supported by the results (see task T4). In
terms of response time, the two models based on matrices seem to lead to
better performance than the other two models, with statistical significance
when comparing NodeTrix and ChordLink. In terms of error rate, we do not
observe any statistically significant difference; in particular, the high
accuracy achieved with all models seems to reveal that this task was generally
easy to perform.

– Hypothesis H3 is not supported by our results, as we do not observe any
statistically significant difference among all the four models.

We conclude by discussing the limits of our study. The choice of not allowing
interaction implied to use networks of small/medium size that fit into the
screen window; also, it required to have a set of predefined clusters that the
user cannot change. On the other hand, a non-interactive environment
facilitated the execution of an on-line test; we believe that enabling visual
interaction for the considered models would require a different study design,
preferably based on a controlled experiment. Further, interactions may
introduce confounding factors and it is difficult to design interaction
features that are fair to all models. The number of tasks was limited to six,
which is in line with many previous studies. Although some works use a larger
number of tasks (see, e.g., [48]), we believe that more tasks may cause long
execution times and a high fatigue effect for the users, which may result in
less reliable data. Finally, the visualization models that we compare may be
sensitive to the specific algorithms used to produce the drawings. This
justifies further investigation with different layout algorithms.

##  5 Conclusions and Future Research

We presented a user study that compares different hybrid visualization models
and the popular node-link model. As a preliminary answer to RQ1, the results
suggest that hybrid visualizations may help to overcome some limits of node-
link diagrams in accurately executing topology-based tasks on globally sparse
but locally dense networks, at the expenses of the execution time. About RQ2,
we could not conclude that any of the considered hybrid models is superior;
however, for some topology-based tasks, we observed better accuracy with
ChordLink and faster execution with NodeTrix. Our study has some limitations
and cannot be generalized to settings significantly different from ours. This
motivates further experiments with larger networks, interaction features, and
additional tasks. Enlarging the set of participants is also an interesting
future objective. In this direction, we tried to collect an additional data
set by using the Amazon’s Mechanical Turk crowdsourcing service. To keep the
population sample homogeneous, we required users with background in computer
science. However, we report a negative response on this side: the
participation was low and the collected data was strongly unreliable (the
error rates were very high and the response times too short for a reasoned
answer). For these reasons, we decided to discard this additional data set.

Acknowledgements. We thank Giuseppe Liotta for useful discussions, Lorenzo
Angori for his help in the implementation, and all the participants to the
study.

## References

  * [1] CiteVis: Visualizing citations among InfoVis conference papers. http://www.cc.gatech.edu/gvu/ii/citevis
  * [2] NodeTrix Javascript. https://github.com/IRT-SystemX/nodetrix
  * [3] Abuthawabeh, A., Beck, F., Zeckzer, D., Diehl, S.: Finding structures in multi-type code couplings with node-link and matrix visualizations. In: VISSOFT. pp. 1–10. IEEE Computer Society (2013)
  * [4] Alper, B., Bach, B., Riche, N.H., Isenberg, T., Fekete, J.: Weighted graph comparison techniques for brain connectivity analysis. In: CHI. pp. 483–492. ACM (2013)
  * [5] Amar, R.A., Eagan, J., Stasko, J.T.: Low-level components of analytic activity in information visualization. In: IEEE Symposium on Information Visualization (InfoVis 2005), 23-25 October 2005, Minneapolis, MN, USA. pp. 111–117 (2005). https://doi.org/10.1109/INFVIS.2005.1532136
  * [6] Angelini, P., Da Lozzo, G.: Beyond clustered planar graphs. In: Hong, S., Tokuyama, T. (eds.) Beyond Planar Graphs, Communications of NII Shonan Meetings, pp. 211–235. Springer (2020). https://doi.org/10.1007/978-981-15-6533-5_12
  * [7] Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M., Rutter, I.: Intersection-link representations of graphs. Journal of Graph Algorithms and Applications 21(4), 731–755 (2017). https://doi.org/10.7155/jgaa.00437
  * [8] Angelini, P., Eades, P., Hong, S., Klein, K., Kobourov, S.G., Liotta, G., Navarra, A., Tappini, A.: Graph planarity by replacing cliques with paths. Algorithms 13(8), 194 (2020). https://doi.org/10.3390/a13080194
  * [9] Angori, L., Didimo, W., Montecchiani, F., Pagliuca, D., Tappini, A.: Hybrid graph visualizations with ChordLink: Algorithms, experiments, and applications. IEEE Transactions on Visualization and Computer Graphics (2020). https://doi.org/10.1109/TVCG.2020.3016055
  * [10] Angori, L., Didimo, W., Montecchiani, F., Pagliuca, D., Tappini, A.: ChordLink: A new hybrid visualization model. In: Graph Drawing. LNCS, vol. 11904, pp. 276–290. Springer (2019)
  * [11] Bach, B., Pietriga, E., Liccardi, I.: Visualizing populated ontologies with OntoTrix. Int. J. Semantic Web Inf. Syst. 9(4), 17–40 (2013). https://doi.org/10.4018/ijswis.2013100102
  * [12] Bachmaier, C., Buchner, H., Forster, M., Hong, S.H.: Crossing minimization in extended level drawings of graphs. Discrete Applied Mathematics 158(3), 159–179 (2010). https://doi.org/10.1016/j.dam.2009.09.002
  * [13] Bar-Joseph, Z., Gifford, D.K., Jaakkola, T.S.: Fast optimal leaf ordering for hierarchical clustering. In: Proceedings of the Ninth International Conference on Intelligent Systems for Molecular Biology. pp. 22–29 (2001)
  * [14] Batagelj, V., Brandenburg, F., Didimo, W., Liotta, G., Palladino, P., Patrignani, M.: Visual analysis of large graphs using (X,Y)-Clustering and hybrid visualizations. IEEE Trans. Vis. Comput. Graph. 17(11), 1587–1598 (2011). https://doi.org/10.1109/TVCG.2010.265
  * [15] Beck, F., Burch, M., Diehl, S., Weiskopf, D.: A taxonomy and survey of dynamic graph visualization. Comput. Graph. Forum 36(1), 133–159 (2017)
  * [16] Bedi, P., Sharma, C.: Community detection in social networks. Wiley Interdiscip. Rev. Data Min. Knowl. Discov. 6(3), 115–135 (2016). https://doi.org/10.1002/widm.1178
  * [17] Besa Vial, J.J., Da Lozzo, G., Goodrich, M.T.: Computing _k_ -modal embeddings of planar digraphs. In: ESA. LIPIcs, vol. 144, pp. 19:1–19:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
  * [18] Bostock, M., Ogievetsky, V., Heer, J.: D3 Data-Driven Documents. IEEE Trans. Vis. Comput. Graph. 17(12), 2301–2309 (2011). https://doi.org/10.1109/TVCG.2011.185
  * [19] Burch, M., Huang, W., Wakefield, M., Purchase, H.C., Weiskopf, D., Hua, J.: The state of the art in empirical user evaluation of graph visualizations. IEEE Access 9, 4173–4198 (2021). https://doi.org/10.1109/ACCESS.2020.3047616
  * [20] Christensen, J., Bae, J., Watson, B., Rappa, M.: Understanding which graph depictions are best for viewers. In: Smart Graphics. Lecture Notes in Computer Science, vol. 8698, pp. 174–177. Springer (2014)
  * [21] Conover, W.J.: Practical nonparametric statistics. Wiley series in probability and mathematical statistics, Wiley, New York, Chichester (1980)
  * [22] Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M.: Computing NodeTrix representations of clustered graphs. Journal of Graph Algorithms and Applications 22(2), 139–176 (2018). https://doi.org/10.7155/jgaa.00461
  * [23] Di Giacomo, E., Lenhart, W.J., Liotta, G., Randolph, T.W., Tappini, A.: _(k,p)_ -planarity: A relaxation of hybrid planarity. In: WALCOM: Algorithms and Computation - 13th International Conference, WALCOM 2019, Guwahati, India, February 27 - March 2, 2019, Proceedings. pp. 148–159 (2019). https://doi.org/10.1007/978-3-030-10564-8_12
  * [24] Di Giacomo, E., Liotta, G., Patrignani, M., Rutter, I., Tappini, A.: NodeTrix planarity testing with small clusters. Algorithmica 81(9), 3464–3493 (2019). https://doi.org/10.1007/s00453-019-00585-6
  * [25] Didimo, W., Kornaropoulos, E.M., Montecchiani, F., Tollis, I.G.: A visualization framework and user studies for overloaded orthogonal drawings. Comput. Graph. Forum 37(1), 288–300 (2018)
  * [26] Didimo, W., Liotta, G., Montecchiani, F.: Network visualization for financial crime detection. J. Vis. Lang. Comput. 25(4), 433–451 (2014). https://doi.org/10.1016/j.jvlc.2014.01.002
  * [27] van Dijk, R.E., Kaden, J.C., Argüelles-Ticó, A., Dawson, D.A., Burke, T., Hatchwell, B.J.: Cooperative investment in public goods is kin directed in communal nests of social birds. Ecology Letters 17(9), 1141–1148 (2014). https://doi.org/10.1111/ele.12320
  * [28] Flake, G.W., Lawrence, S., Giles, C.L., Coetzee, F.: Self-organization and identification of web communities. IEEE Computer 35(3), 66–71 (2002). https://doi.org/10.1109/2.989932
  * [29] Fortunato, S.: Community detection in graphs. Physics Reports 486(3-5), 75–174 (2010). https://doi.org/10.1016/j.physrep.2009.11.002
  * [30] Ghoniem, M., Fekete, J., Castagliola, P.: On the readability of graphs using node-link and matrix-based representations: a controlled experiment and statistical analysis. Inf. Vis. 4(2), 114–135 (2005). https://doi.org/10.1057/palgrave.ivs.9500092
  * [31] Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA 99(12), 7821–7826 (2002). https://doi.org/10.1073/pnas.122653799
  * [32] Hadlak, S., Schulz, H., Schumann, H.: In situ exploration of large dynamic networks. IEEE Trans. Vis. Comput. Graph. 17(12), 2334–2343 (2011)
  * [33] Henry, N., Bezerianos, A., Fekete, J.: Improving the readability of clustered social networks using node duplication. IEEE Trans. Vis. Comput. Graph. 14(6), 1317–1324 (2008). https://doi.org/10.1109/TVCG.2008.141
  * [34] Henry, N., Fekete, J.: MatLink: Enhanced matrix visualization for analyzing social networks. In: INTERACT (2). Lecture Notes in Computer Science, vol. 4663, pp. 288–302. Springer (2007)
  * [35] Henry, N., Fekete, J., McGuffin, M.J.: NodeTrix: A hybrid visualization of social networks. IEEE Trans. Vis. Comput. Graph. 13(6), 1302–1309 (2007). https://doi.org/10.1109/TVCG.2007.70582
  * [36] Keller, R., Eckert, C.M., Clarkson, P.J.: Matrices or node-link diagrams: which visual representation is better for visualising connectivity models? Inf. Vis. 5(1), 62–76 (2006). https://doi.org/10.1057/palgrave.ivs.9500116
  * [37] Lee, B., Plaisant, C., Parr, C.S., Fekete, J., Henry, N.: Task taxonomy for graph visualization. In: Proceedings of the 2006 AVI Workshop on BEyond time and errors: novel evaluation methods for information visualization, BELIV 2006, Venice, Italy, May 23, 2006. pp. 1–5 (2006). https://doi.org/10.1145/1168149.1168168
  * [38] Ley, M.: The DBLP computer science bibliography, https://dblp.uni-trier.de
  * [39] Liotta, G., Rutter, I., Tappini, A.: Graph planarity testing with hierarchical embedding constraints. CoRR abs/1904.12596 (2019), http://arxiv.org/abs/1904.12596
  * [40] Liotta, G., Rutter, I., Tappini, A.: Simultaneous FPQ-ordering and hybrid planarity testing. In: SOFSEM. LNCS, vol. 12011, pp. 617–626. Springer (2020)
  * [41] Liotta, G., Rutter, I., Tappini, A.: Simultaneous FPQ-ordering and hybrid planarity testing. Theoretical Computer Science 874, 59–79 (2021). https://doi.org/10.1016/j.tcs.2021.05.012
  * [42] Lloyd, S.P.: Least square quantization in PCM. IEEE Transactions on Information Theory 28(2), 129–137 (1982)
  * [43] Mahmoud, H., Masulli, F., Rovetta, S., Russo, G.: Community detection in protein-protein interaction networks using spectral and graph approaches. In: CIBB. LNCS, vol. 8452, pp. 62–75. Springer (2013). https://doi.org/10.1007/978-3-319-09042-9_5
  * [44] Mangan, S., Alon, U.: Structure and function of the feed-forward loop network motif. Proceedings of the National Academy of Sciences 100(21), 11980–11985 (2003). https://doi.org/10.1073/pnas.2133841100
  * [45] Matuszewski, C., Schönfeld, R., Molitor, P.: Using sifting for $k$-layer straightline crossing minimization. In: Graph Drawing, 7th International Symposium, GD’99, Stirín Castle, Czech Republic, September 1999, Proceedings. pp. 217–224 (1999). https://doi.org/10.1007/3-540-46648-7_22
  * [46] Melancon, G.: Just how dense are dense graphs in the real world? A methodological note. In: Proceedings of the 2006 AVI Workshop on BEyond Time and Errors: Novel Evaluation Methods for Information Visualization. p. 1–7. BELIV ’06, Association for Computing Machinery, New York, NY, USA (2006). https://doi.org/10.1145/1168149.1168167
  * [47] Okoe, M., Jianu, R.: GraphUnit: Evaluating interactive graph visualizations using crowdsourcing. Comput. Graph. Forum 34(3), 451–460 (2015)
  * [48] Okoe, M., Jianu, R., Kobourov, S.G.: Node-link or adjacency matrices: Old question, new insights. IEEE Trans. Vis. Comput. Graph. 25(10), 2940–2952 (2019). https://doi.org/10.1109/TVCG.2018.2865940
  * [49] Onnela, J., Kaski, K., Kertész, J.: Clustering and information in correlation based financial networks. The Europ. Phys. J. B-Cond. Matter and Complex Syst. 38(2), 353–362 (2004). https://doi.org/10.1140/epjb/e2004-00128-7
  * [50] Porter, M.A., Onnela, J.P., Mucha, P.J.: Communities in networks. Notices of the American Math. Soc. 56, 1082–1097, 1164–1166 (2009)
  * [51] Purchase, H.C.: Performance of layout algorithms: Comprehension, not computation. J. Vis. Lang. Comput. 9(6), 647–657 (1998). https://doi.org/10.1006/jvlc.1998.0093
  * [52] Purchase, H.C.: Experimental Human-Computer Interaction - A Practical Guide with Visual Examples. Cambridge University Press (2012)
  * [53] Purchase, H.C., Hamer, J., Nöllenburg, M., Kobourov, S.G.: On the usability of lombardi graph drawings. In: Didimo, W., Patrignani, M. (eds.) Graph Drawing - 20th International Symposium, GD 2012, Redmond, WA, USA, September 19-21, 2012, Revised Selected Papers. Lecture Notes in Computer Science, vol. 7704, pp. 451–462. Springer (2012). https://doi.org/10.1007/978-3-642-36763-2_40
  * [54] Rossi, R.A., Ahmed, N.K.: The network data repository with interactive graph analytics and visualization. In: AAAI (2015), http://networkrepository.com
  * [55] Rufiange, S., McGuffin, M.J.: Diffani: Visualizing dynamic graphs with a hybrid of difference maps and animation. IEEE Trans. Vis. Comput. Graph. 19(12), 2556–2565 (2013)
  * [56] Saket, B., Simonetto, P., Kobourov, S.G., Börner, K.: Node, node-link, and node-link-group diagrams: An evaluation. IEEE Trans. Vis. Comput. Graph. 20(12), 2231–2240 (2014). https://doi.org/10.1109/TVCG.2014.2346422
  * [57] Thode, H.C.: Testing for normality. Marcel Dekker (2002)
  * [58] Wu, H., He, J., Pei, Y., Long, X.: Finding research community in collaboration network with expertise profiling. In: ICIC (1). LNCS, vol. 6215, pp. 337–344. Springer (2010). https://doi.org/10.1007/978-3-642-14922-1_42
  * [59] Yang, X., Shi, L., Daianu, M., Tong, H., Liu, Q., Thompson, P.M.: Blockwise human brain network visual comparison using NodeTrix representation. IEEE Trans. Vis. Comput. Graph. 23(1), 181–190 (2017). https://doi.org/10.1109/TVCG.2016.2598472

##  Appendix 0.A Further Details on the User Study Design

###  0.A.1 Stimuli

For each of the four visualization models described in Section 3.1, we
produced a diagram of the three networks described in Section 3.4. The
diagrams for the NodeLink model are computed through the force-directed
algorithm available in the D3 library [18]. Starting from these drawings, we
defined some geometric clusters with the technique based on the $K$-means
algorithm [42] described in [9]. As explained in Section 3.1, the system
presented in [9] is used to compute the diagrams in the ChordLink, NodeTrix,
and RCI-NodeTrix models with the same sets of clusters. The algorithm for
NodeTrix is based on [2, 35] and uses the _leaf order method_ to compute the
row/column order [13]. The algorithm for RCI-NodeTrix is a variant of the one
for NodeTrix, where the orders for the rows and the columns are independently
computed to reduce the number of crossings between inter-cluster edges; this
is done by an adaptation of the sifting algorithm for layered drawings [12,
45]. In all four diagrams of the same network, we labeled all the nodes that
belong to clusters and few high-degree nodes outside the clusters. We avoid
label duplication in all the drawings; this reduces visual clutter and
suffices to correctly interpret the data in all models; in particular, in
NodeTrix and RCI-NodeTrix we filled each cell whose row and column refer to
the same node with a color distinct from black and white (these cells
correspond to the main matrix diagonal in NodeTrix). Also, we use numerical id
labels instead of real names to guarantee anonymity and to avoid that users
could be influenced by their knowledge about the network.

###  0.A.2 Pilot Study

The actual experiment was preceded by a pilot study with 19 participants,
mostly colleagues and students in computer engineering, who are
representatives of our class of target users. Based on the feedback received
from the pilot study, we made some small changes to the survey. More
precisely, for task T4 we increased the number of labels to be found from one
to three, because we had 100% correct answers. For task T6 we changed the type
of question from a single choice question (the user selects the answer from a
fixed set of values) to a free text answer. We made this change because the
limited number of options helped the users to guess the right answer; in
particular few participants reported that when they had in mind a wrong value
that was not present among the options, they selected the closest value.

###  0.A.3 Trials for the Network weavers

(a) T1

(b) T2

(c) T3

(d) T4

(e) T5

(f) T6

Figure 5: Trials for the network weavers in the NodeLink model. For task T3
$k=4$; for task T4 the three labels are: 374, 334, 220.

(a) T1

(b) T2

(c) T3

(d) T4

(e) T5

(f) T6

Figure 6: Trials for the network weavers in the ChordLink model. For task T3
$k=4$; for task T4 the three labels are: 374, 334, 220.

(a) T1

(b) T2

(c) T3

(d) T4

(e) T5

(f) T6

Figure 7: Trials for the network weavers in the NodeTrix model. For task T3
$k=4$; for task T4 the three labels are: 374, 334, 220.

(a) T1

(b) T2

(c) T3

(d) T4

(e) T5

(f) T6

Figure 8: Trials for the network weavers in the RCI-NodeTrix model. For task
T3 $k=4$; for task T4 the three labels are: 374, 334, 220.

##  Appendix 0.B Additional Material about the Study Results

###  0.B.1 Data about the Participants to the Study

Figure 9: Data about the participants to the study.

###  0.B.2 Discarded Questionnaires

We collected questionnaires from 89 participants. We discarded seven tests for
various reasons. One of the participants indicated in the free comments area
that some images were not shown properly. Four participants indicated to have
some color vision deficiency. Since they happened to be all assigned to the
same model, we decided to discard their tests to avoid an unbalanced effect of
this factor on the results of the experiment. Finally, since the experiment
was fully online and thus not controlled, we discarded two tests whose total
response time (i.e., the total time spent to answer the 18 trials) was an
outlier. According to common practice, we consider the total response time of
a test an outlier if it falls more than $1.5$ times IQR below the first
quartile or above the third quartile.

###  0.B.3 Free Comments

In what follows we report, for each model, a summary of the main free comments
posted by the participants at the end of the study.

NodeLink: All comments point out that the visual clutter caused by dense
portions of the network makes the execution of some tasks difficult. This is
coherent with the motivation behind the introduction of hybrid graph
visualizations.

ChordLink: The comments point out that node duplication affects the drawing
readability and makes it difficult to perform tasks related to cluster
density. This is coherent with our rationale about Hypothesis H3, i.e., node
duplication may give the impression that a cluster is sparser than it actually
is. Other comments highlight that cluster regions represented by circles with
small diameter make intra-cluster edges difficult to distinguish in some
cases.

NodeTrix: Here, the main comments report a difficulty in reading inter-cluster
edges and, in particular, their incidence to the matrices.

RCI-NodeTrix: The main comment here is that it is somewhat counter-intuitive
that the matrices do not use the same row and column order, and this has a
negative impact on following paths in the network.

We further report that two participants found our definition of density
(denoted as $d_{1}$ in Section 3.2) less intuitive than the alternative one
(denoted as $d_{2}$ in Section 3.2).