# Improved Visual Saliency of Graph Clusters with Orderable Node-Link Layouts

Nora Al-Naami, Nicolas Médoc, Matteo Magnani, Mohammad Ghoniem

► To cite this version:

Nora Al-Naami, Nicolas Médoc, Matteo Magnani, Mohammad Ghoniem. Improved Visual Saliency of Graph Clusters with Orderable Node-Link Layouts. IEEE Transactions on Visualization and Computer Graphics, In press. hal-04668352

HAL Id: hal-04668352

https://hal.science/hal-04668352v1

Submitted on 6 Aug 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Improved Visual Saliency of Graph Clusters with Orderable Node-Link Layouts

Nora Al-Naami ID, Nicolas Médoc ID, Matteo Magnani ID, Mohammad Ghoniem ID

<figure><img src="image_2.png" /><figcaption>Fig. 1: A 100-node synthetic network having three clusters with 'low' within-cluster and 'low' between-cluster link probability, laid out from left to right according to the 'Linlog' layout, vanilla 'arc diagram', symmetric 'arc diagram' and 'radial diagram'. The clusters are indiscernible in the Linlog diagram, and clearly visible in the orderable layouts, where nodes are in the original graph generation order.</figcaption></figure>

**Abstract**—Graphs are often used to model relationships between entities. The identification and visualization of clusters in graphs enable insight discovery in many application areas, such as life sciences and social sciences. Force-directed graph layouts promote the visual saliency of clusters, as they bring adjacent nodes closer together, and push non-adjacent nodes apart. At the same time, matrices can effectively show clusters when a suitable row/column ordering is applied, but are less appealing to untrained users not providing an intuitive node-link metaphor. It is thus worth exploring layouts combining the strengths of the node-link metaphor and node ordering. In this work, we study the impact of node ordering on the visual saliency of clusters in orderable node-link diagrams, namely radial diagrams, arc diagrams and symmetric arc diagrams. Through a crowdsourced controlled experiment, we show that users can count clusters consistently more accurately, and to a large extent faster, with orderable node-link diagrams than with three state-of-the art force-directed layout algorithms, i.e., 'Linlog', 'Backbone' and 'sfdp'. The measured advantage is greater in case of low cluster separability and/or low compactness. A free copy of this paper and all supplemental materials are available at https://osf.io/kc3dg/.

**Index Terms**—network visualization, arc diagrams, radial diagrams, cluster perception, graph seriation

## 1 INTRODUCTION

Graph visualization is widely used to support network analysis tasks in various areas of science and engineering [43]. One popular network analysis task consists in identifying locally dense subgraphs [54], often called ‘clusters’, or ‘communities’ in social network analysis [10], or ‘modules’ in biological network analysis [14]. Indeed, graph clusters correspond to meaningful sub-structures in many applications [84]. Hence, when asked to lay out a graph interactively, users tend to prioritize the formation of clusters over other aesthetic considerations [82].

Graph clusters are often visually identified by drawing the graph using a force-directed node-link layout ↕ algorithm. This category of algorithms uses physics-based models, whereby attraction forces place adjacent nodes (see Section 2) closer to each other, and repulsive forces place non-adjacent nodes farther apart [35, 48, 84]. Hence, when the graph contains clusters, nodes belonging to the same cluster tend to clump together in the 2D plane. This makes clusters visually salient in virtue of the Gestalt rule of proximity [48], without using any additional visual cues to denote cluster membership, such as node color. In a recent comparison of many force-directed layouts, the LinLog layout [64,

65] has consistently outperformed other alternatives [60]. The best cluster separation is generally achieved when internal link density within clusters is high, and external link density is low, i.e., relatively fewer links exist between nodes sitting in distinct clusters [65].

Another approach uses adjacency matrices as a visual metaphor to analyze graphs. Nodes are mapped to the rows and columns of a matrix, while links appear as colored rectangles at the intersection of adjacent (rows/columns) nodes. Besides being more readable for many low-level perceptual tasks, for large and dense graphs [34], matrices are effective at showing graph clusters when a suitable row/column ordering is applied [41]. Following Bertin’s work on table seriation [12], much work compared various methods for reordering matrix visualizations to elicit structural properties [11, 30]. Matrices are yet a less popular graph visualization, and are less appealing to untrained users [34].

In this work, we retain the node-link metaphor owing to its popularity and intuitiveness and, we apply node ordering to elicit clusters, inspired by the proven effectiveness of node ordering in matrix visualizations. The node-link layouts where nodes can be ordered include the ones that place nodes on a continuous non-self-intersecting topological curve, e.g., a circle, an ellipse, a straight line or a space-filling curve. Nodes can be ordered along such a curve, e.g., based on topological or attribute-based criteria. In this paper, we will refer to such layouts, as ‘orderable node-link layouts’. This category includes ‘arc diagrams’ ↕ [86] and ‘radial diagrams’ ↖ [51], which place the nodes along a straight line and along a circle, respectively. Edges are drawn as half circles in arc layouts ↕, and as Bézier curves or straight lines in radial layouts ↖. Although radial and arc layouts ↖ are not new representations, we lack user studies regarding their readability for perceptual tasks.

This paper raises the following research question: how do orderable node-link layouts ↕, ↖, and ↗ compare to force-directed layouts ↕, and to one another regarding their ability to reveal node clusters in

* Nora Al-Naami, Nicolas Médoc and Mohammad Ghoniem are with Luxembourg Institute of Science and Technology.
E-mail: {nora.alnaami | nicolas.medoc | mohammad.ghoniem}@list.lu.

* Matteo Magnani is with Uppsala University.
E-mail: matteo.magnani@it.uu.se.

Manuscript received xx xxx. 201x; accepted xx xxx. 201x. Date of Publication xx xxx. 201x; date of current version xx xxx. 201x. For information on obtaining reprints of this article, please send e-mail to: reprints@ieee.org.
Digital Object Identifier: xx.xxxx/TVCG.201x.xxxxxxx
graphs? To do so, we contribute a crowdsourced empirical study whose dependent variables are the accuracy and completion time of cluster count judgement, under varying values of independent variables which are cluster compactness, cluster separability, node ordering method, graph size and graph layout. We elicit new insights regarding how three popular orderable node-link diagrams (arc diagrams ↺, symmetric arc diagrams ⌜, radial diagrams ⌝) compare to three competitive force-directed layouts ↘ (Linlog, Backbone and sfdp). We also assess the impact of two different node ordering methods (the optimal leaf ordering and the cross reduction algorithms) on the effectiveness of orderable layouts, in addition to the original node order provided by the graph generator. Finally, we derive guidelines for the use of these layouts based on graph characteristics and type of clusters.

# 2 RELATED WORK

Our work builds on previous research in the areas of graph visualization, and graph seriation, as well as user studies related to these areas.

## 2.1 Graph Visualization

Graphs are commonly used to model relationships between entities. They have been used to analyze complex phenomena in many application fields, such as social sciences, biology, and transportation [84]. Formally, a graph $G$ is defined as $G = (V, E)$ where $V$ is a set of vertices and $E \subseteq V \times V$ is the set of edges connecting pairs of vertices in $G$. Two vertices $u \in V$ and $v \in V$ are said to be *adjacent*, if $\exists e \in E : e = (u, v)$.

The popularity of graphs has motivated much research on graph drawing and network visualization [8, 25]. In *node-link diagrams*, vertices are displayed as nodes, e.g., circles, and edges as links, e.g., curves. Many algorithms produce such diagrams in 2D and 3D [35, 43]. In their survey, von Landesberger et al. [84] categorize node-link layouts into *force-directed*, *constraint-based* [28], *multiscale* [49], *layered* [27] and *non-standard* layouts, e.g., projection-based layouts [39].

Force-directed layouts ↘ adopt a physics-based model, e.g., springs and masses, or electric particles, whose equilibrium determines the position of nodes such that adjacent nodes are placed closer to each other [40, 59]. They are hence well-suited for cluster visualization [35], in virtue of the Gestalt proximity law [48]. The 'Linlog' energy models improve the visual separation of clusters compared to prior force-directed layouts [64, 65]. Meidiana et al. [60] used a quality metric score to compare force-directed layouts (e.g., Fruchter-Reingold [31]), multi-level layouts (e.g., FM3 [37], sfdp [29, 45]), multi-dimensional scaling methods (e.g., MDS [80], pivot MDS [17]), stress-based layouts (e.g., Stress Majorization [33]), spectral layouts (e.g., with graph Laplacian) with other layouts designed for cluster discovery, such as Backbone [69], tsNET [50] and Linlog [64]. They found that the Linlog layout performed well across many graph data sets, and generally better than competing algorithms [35], followed by Backbone and tsNET.

Other node-link layouts place nodes along a geometric locus. For instance, radial layouts ↺ place nodes around a circle [26], whereas arc diagrams ↺ [63, 86] and BioFabric [32] place them along a straight line. These layouts are special cases of constraint-based layouts [28], where graph nodes are placed along the given locus, be it a circle, an ellipse, a straight-line, or a space-filling curve, e.g., Hilbert curves [61, 88]. Such layouts are orderable, since nodes can be sorted along the underlying geometric locus. User studies on the impact of node ordering on the readability of radial ↺ or arc ↺ layouts are yet lacking.

When the vertices and edges of the graph have attributes attached to them, distinct types of graphs and graph visualization problems arise. This has given birth to specific lines of graph visualization research including, for example, multivariate graphs [67], multipartite graphs [5], dynamic graphs [9] and multilayer graphs [58]. Many attribute-based techniques take a faceted layout approach to show subgraphs, e.g., parallel 1-D axes in PivotGraph [87], parallel 2-D planes (showing edges on demand) as in Semantic Substrates [78] or NodeXL [79].

In this work, we focus on the perception of clusters in single-mode unweighted unattributed graphs, without prior ground truth about clusters. We compare three orderable node-link layouts ↺, ◀, ▶ to three state-of-the-art force-directed layouts ↘, i.e., Linlog, Backbone and sfdp, in terms of visual cluster perception.

## 2.2 Graph Seriation

Graph seriation [56] is the arrangement of nodes and their edges in a visualization to elicit hidden graph patterns, which reveal key properties of the underlying network [11, 62]. Seriation was mainly applied to tables and matrices [56, 73, 75]. In a network, node ordering algorithms aim to reveal latent network patterns to the user [59]. They can be divided into *attribute-based* algorithms, e.g., ordering nodes based on their label and *topology-based* or *seriation* algorithms [56].

Focusing on adjacency matrices, Behrisch et al. [11] distinguish seven families of ordering methods, based on common underlying reordering concepts [11]: 1) Robinsonian methods, e.g., clustering-based algorithms, including the *Optimal Leaf Ordering* [6] (OLO); 2) spectral methods, e.g., rank-two ellipse seriation [19]; 3) dimensionality reduction methods, e.g., multi-dimensional scaling [15]; 4) heuristic methods, e.g., the crossing reduction heuristic (CR), also known as the barycenter heuristic [57]; 5) graph-theoretic methods, e.g., based on the Traveling Salesman Problem (TSP) [55]; 6) biclustering methods [22]; 7) interactive reordering methods, e.g., the Bertifier [73]. They benchmark many seriation methods against many real and synthetic graphs, in terms of execution time and quality of the resulting matrix visualization using the *minimum linear arrangement* score [74]. They conclude that cluster identification is better supported by clustering-based techniques. They recommend the use of OLO, as it optimizes for cluster patterns at the global and local levels, e.g., placing nodes at the boundary of their cluster closer to their neighbors in other clusters.

In this empirical study, we take a user perception perspective on node ordering, with three understudied orderable node-link layouts ↺, ◀, ▶. Our study considers the OLO order, as recommended by Berisch et al. [11], and the CR order, which was also used by Oeke et al. [70] in their cluster perception task, and in PivotGraph [87] to minimize edge crossings between parallel 1-D axes. In this work, OLO is based on the hierarchical clustering algorithm with average linkage. This puts this work close to other studies using hierarchical clustering to order graph nodes, e.g., by Abdelaal et al. [1] who do not mention using leaf order optimization explicitly. With this empirical study, we compare the two ordering methods systematically to one another when applied to ↺, ◀, ▶ and also to three state-of-the-art force-directed layouts ↘, i.e., Linlog, Backbone and sfdp, in terms of cluster perception.

## 2.3 User Studies on Cluster Perception in Graphs

Lee et al. categorize graph visualization tasks into *topology-based*, *attribute-based*, *browsing* and *overview* tasks [54]. They consider cluster identification as a topology-based task, and underscore that an overview of the graph will usually help to find patterns, such as clusters, if a suitable graph layout is used. This is typically what force-directed node-link layouts aim to do, as well as matrix seriation methods, as pointed out earlier. Vehlow et al. survey visual encodings of group structure information in graph visualizations [83]. They deliberately exclude the use of layout for this purpose from their scope, but mention in passing the possibility to use 1-D layouts to implicitly encode group information, where nodes are placed along a circle or a linear axis. They focus on other visual encodings, like the use of node color or hulls and contours for cluster membership. They categorize groups into flat versus hierarchically structured, and disjoint versus overlapping. They also position previous work based on the type of visual encoding used to convey group membership information.

Many user studies on cluster perception in graph visualizations compare force-directed layouts to adjacency matrices and cover various graph visualization tasks such as path-related, attribute-based, overview and memorability tasks. Okoe et al. [70] compare node-link layouts generated using neato [29] and matrix visualizations ordered by the crossing reduction method from Reorderjs [30]. Based on two real graphs having 258 and 332 nodes, they show that matrices outperform force-directed layouts for the perception of colored clusters. Nobre et al. also confirmed the superiority of matrices for cluster perception in multivariate networks, based on two real 75- and 25-node graphs [68]. Chen et al. also studied cluster perception using an interactive toroidal layout, with automatic panning [21]. They used synthetic graphs of variable density comprising 68 to 134 nodes and 3 to 8 clusters. They
show that toroidal wrap layouts support faster and more accurate cluster perception than 'standard' force-directed layouts. Several studies on clustered graphs have used much larger graphs, though [24].

Other studies go beyond force-directed node-link layouts and adjacency matrices. For example, to solve path-related problems typical of adjacency matrices, Henry-Riche et al. [42] compare the Linlog layout to MatLink, a hybrid visualization composed of an arc diagram drawn on the side of a matrix ordered by a TSP heuristic. Based on six open data sets with less than 100 nodes with varying densities, they find that MatLink outperforms force-directed layouts for the identification of the largest cluster in the graph. Also, Abdelaal et al. [1] compare force-directed layouts generated by d3-force, to a bipartite layout placing nodes along two (orderable) parallel axes with links in between them and a matrix visualization. They assess user performance for five tasks, including a cluster perception task, on graphs as large as 500 nodes. The bipartite layouts and the matrices were ordered using an agglomerative hierarchical clustering algorithm. For the cluster perception task, they report no significant difference between matrices and force-directed layouts, whereas bipartite layouts are much worse.

While in prior studies the overall graph density is considered as a factor affecting user performance, this study aims to determine to what extent cluster perception is affected by link probability between clusters and within clusters, across various network sizes and visualization types, including three state-of-the-art force-directed layouts [1], i.e., Linlog, Backbone and sfdp and three orderable layouts. To this end, we generated 60 different graph structures with a controlled within- and between-cluster probability (two levels: 'low' and 'high' for both probabilities), a controlled number of clusters $k \in [3..7]$ of variable sizes, and a controlled network size in terms of number of nodes (50, 100 and 300 nodes). Also, we assess the impact of the node ordering method (CR and OLO) on the performance of orderable layouts compared to the three force-directed node-link layouts. While Linlog is close to the optimum in translating mathematical clusters into a visual clustering [66], the interplay between within- and between-cluster probability seems underexplored in network visualization. This focus on graph cluster compactness and separability is inspired by cluster validity indices [3, 23, 77] used in pattern mining research. Finally, our study is purely perceptual to evaluate the layouts in their own right, as navigation interactions may add more factors to control.

# 3 METHODS

In this section, we describe the key parameters we control to generate the set of stimuli used in this user study. We also present our hypotheses and their motivation, as well as the study design and procedure.

## 3.1 The Visual Stimuli

**Network Size** In this study, we generated synthetic data to better control key network parameters. Compared to previous work surveyed by Yoghourdjian et al. [90] where most studies use graphs with less than 100 nodes, our study considers 50-, 100- and 300-node graphs. By doing so, we aim to study both small and larger networks, without the need to use interaction techniques. We also use large networks to reduce the impact of random fluctuations during data generation.

**Number of clusters and cluster size** Since in real networks clusters may vary in size, we use the Gaussian random partition graph generator [16] of NetworkX [38] to create networks with $k \in [3..7]$ clusters, each drawn from a normal distribution with a mean cluster size and variance of cluster size distribution. We did not go beyond seven clusters because counting the clusters might become tedious without adding insights concerning cluster perception.

**Cluster compactness and separability** We set the within- and between-cluster link probability, $p_{in}$ and $p_{out}$ respectively, to control cluster compactness and separability. A high value of $p_{in}$ corresponds to compact clusters, while a low value leads to loose clusters. Likewise, a high $p_{out}$ creates relatively many links between clusters, i.e., poor cluster separation, whereas a low $p_{out}$ leads to better cluster separation. To keep the duration of user sessions under one hour, we consider two cluster compactness profiles $p_{in} \in \{low = 0.3, high = 0.6\}$ and two

<figure><img src="image_3.png" /><figcaption>Fig. 2: The four quadrants of cluster types.</figcaption></figure>

cluster separability profiles $p_{out} \in \{low = 0.3, high = 0.6\}$ as shown in Figure 2. In the rest of this paper, we will refer to clusters as separable in the low $p_{out}$ condition, and as inseparable for high $p_{out}$. Also, we describe clusters as compact if they result from high $p_{in}$, and loose otherwise. For each network size, we generate four graph structures, one in each quadrant. We use the following icons to denote these quadrants:

- [ ] (loose, separable) clusters
- [■] (loose, inseparable) clusters
- [■] (compact, separable) clusters, and [■] (compact, inseparable) clusters

An important concern regarding cluster compactness and separability is to choose the so-called 'low' and 'high' values for $p_{in}$ and $p_{out}$ such that the obtained graph clusters are meaningful. Determining the absolute upper and lower bounds beyond which clusters cease to exist is beyond the scope of this study. A pragmatic validation measure to ensure the clustering tendency of the generated graphs consisted in visually inspecting the corresponding adjacency matrices to verify the presence of characteristic diagonal blocks. The rows and columns of the matrix were ordered according the original node order provided by the graph generator. In essence, such a visual approach to assess clustering tendency is tantamount to the VAT method and its many variants [52] which also look for diagonal blocks in matrices, albeit originally for multivariate data in general. This approach also leverages prior knowledge about the effectiveness of matrix visualizations in showing clusters, subject to vertex seriation. Figure 3 shows such matrices for the 50 node-graphs for all four cluster type conditions, retaining the original node order provided by the graph generator. Clustering tendency is at stake in the top three rows, where clusters are loose and/or inseparable. Yet, we can see the right number of diagonal blocks in all cases, the signal being admittedly faint in the top left case.

**Visualization types and settings** Meidiana et al. [60] showed that Linlog is the best for cluster detection. Also, Jacomy et al. [46] argue that Force Atlas2 with Linlog energy is faster and leads to a better cluster definition than other layouts like Fruchterman-Reingold [31], Yifan-Hu and Force Atlas2 without Linlog energy. We study Linlog, Backbone and sfdp, three performant layouts from the study of Meidiana et al. We generated the Linlog layouts using Gephi [7] v. 0.10.1 based on its implementation of the Forceatlas2 algorithm with Linlog [64] mode on, and with the node overlap prevention mode on. We increased the edge width in these diagrams to improve link visibility. The Backbone layout was generated using VisOne v. 2.26, with backbone type = 'Quadrilateral Simmelian' (recommended in [69]), backbone strength type = 'redundancy' and compared edge = 'true'. The sfdp layouts came from Graphviz v. 2.43.0 with the default parameters. We also implemented three types of orderable node-link layouts in D3, namely radial, arc and symmetric arc layouts. For each graph, we applied two node ordering methods: the crossing reduction method from Reorderjs [30] v. 2.2.4, i.e., the barycenter heuristic [57], and the optimal leaf ordering method [6] with average linkage and Jaccard distance from scipy v. 1.11.4. We also generated the stimuli corresponding to the original node order provided by the graph generator (denoted as GEN hereafter). Finally, each stimulus is saved as an SVG image which is scaled to occupy all the available canvas, with no possible user interaction. To reduce digital eyestrain due to screen brightness [89], the stimuli were rendered with white semi-transparent links (and blue nodes) on a black background (as in Figure 6), whereas most images in this paper use the reverse encoding to save ink. All stimuli are provided in supplemental material. Digital eyestrain is yet a complex phenomenon for which we still lack definitive guidelines.
<figure><img src="image_4.png" /><figcaption>Fig. 3: Visual assessment of clustering tendency based on the adjacency matrix of the 50-node graphs in their original node order.</figcaption></figure>

## 3.2 Hypotheses

Below, we list our hypotheses about the visual saliency of clusters in orderable and force-directed node-link layouts across the cluster compactness and separability quadrants. Given the known ground truth of the graph generation process, we use the users' ability to count clusters as a proxy of cluster visual saliency. We use the same accuracy score as Okoe et al. [70], defined as: $Acc = \max(0, 1 - \frac{\|PA-TA\|}{\|TA\|})$, where PA stands for participant answer and TA for the true answer.

**H1** Graph clusters are more salient visually in orderable layouts compared to force-directed layouts, for all combinations of compactness and separability except for (compact, well-separated) clusters, which is the ideal scenario for force-directed layouts.

*Rationale:* Prior studies [42, 68, 70] on various cluster perception tasks suggest that ordered matrices improve the visual saliency of clusters (which appear as dense blocks of links). We expect that node ordering in arc layouts, symmetric arc layouts and radial layouts will also create locally high link concentrations easing cluster perception, as in Figure 1.

**H2** Graph clusters are more salient visually in orderable node-link diagrams ordered by the optimal leaf ordering method (OLO) than the layouts ordered by the crossing reduction method (CR).

*Rationale:* Based on the study by Behrisch et al. [11], OLO [6] which is a clustering based method is preferable for cluster perception tasks to other types of ordering methods, in this case CR [57]. In a sense, the visual saliency of clusters resulting from CR is an indirect product of reducing link crossings in a network. A good example of CR's ability to reveal clusters is provided in Figure 5. Yet, OLO is designed to reveal clusters, and should consistently surpass CR for cluster perception.

**H3** Graph clusters are more salient visually in symmetric arc diagrams than in plain arc diagrams.

*Rationale:* According to the Gestalt principles, the elements of symmetric components tend to be seen as belonging together [48]. Also, symmetry preservation is a known aesthetic rule in graph drawing [8, 18].

Hence, the round disc-shaped clusters in symmetric arc layouts might improve cluster perception as opposed to half discs in plain arc layouts.

## 3.3 Study Design

This user study combines between-subject and within-subject designs. We adopted a between-subject approach at the level of network size. That is, participants were exposed to a single network size only throughout their session. Within a session, we adopted a within subject approach where we varied all other factors as detailed in Section 3.4. We ran three pilot tests with a few users each to troubleshoot any usability issues and validate our data collection procedure, our estimation of task completion time and the total duration of each participant session. We aimed to keep the total session duration under one hour. We used Prolific to recruit English-speaking online participants, equipped with a laptop or desktop computer. Like in similar user studies [1, 70], we aimed for 40 to 50 participants for each condition. In total, we recruited *n* = 139 participants, mainly between the ages of 18 and 34 (64%); the remaining 36% were above 35. Among them, 57.24% declared to be males, 44.27% females and the rest (0.76)% did not declare their gender. Most participants were geographically located in the UK (27%), South Africa (17%), the USA (9%) and Portugal (9%).

## 3.4 Study Procedure

After signing the informed consent form, each participant was trained on scribbling on a drawing canvas using their mouse. This was needed later in the procedure to validate their understanding of the cluster identification task. Figure 4 gives an overview of the study procedure. All participants were exposed to the four visualization types in a random sequence. For each visualization type, participants went through the following steps:

1. *Training.* They watched a one-minute video explaining how to read the visualization, based on a social network scenario, presenting nodes as people, edges as friendship relationships, and clusters as friendship groups. The video showed a 51-node extract of the
<figure><img src="image_5.png" /><figcaption>Fig. 4: Flowchart of the study procedure. Credit: video icon by Ilham Fitrotul Hayat from Noun Project (CC BY 3.0).</figcaption></figure>

character co-occurrence network in *Les Misérables* novel [47] with distinct clusters (see Figure 5). The network construction was animated to ease comprehension. Users could replay the video. Then, they took a training based on two sample networks: the extract of *Les Misérables* again and the AUCS network [76]. They chose the cluster count among multiple choices between 1 and 8. The correct answer was displayed as an image with an overlay outline of the individual clusters to teach them the visual signature of clusters in the visual metaphor at hand.

2. **Counting Task.** For each visualization type, participants saw 60 stimuli in random order (4 cluster types × 5 cluster count values × 3 variants). The variants correspond either to the three node orderings (GEN, OLO, CR), if applicable, or the three force-directed layouts (Linlog, Backbone, sfdp). For each stimulus, users had to count the friendship groups and to choose the right answer between [1..8] (for ground truth $k \in [3..7]$). This task is used to test all three hypotheses.

3. **Drawing Task.** Finally, users drew an outline around clusters in the 100-node stimuli having four compact and separable clusters (those in Figure 6). As we did not have direct access to online participants, we needed concrete evidence that they individually understood the task. This might be used typically to exclude anomalous participants, which was not the case here.

After an optional 2-minute break, participants moved on to the next visualization type and repeated the same steps. Hence, all participants saw 240 stimuli in total (4 visualization types × 60 stimuli). We used Mephisto [81] to create and deploy the study, and collect data. For each stimulus, we recorded the cluster count and the response times.

# 4 RESULTS

In Figure 6, we overlay all the cluster outlines drawn by all study participants in the cluster drawing task, for network size 100. It shows that for all four layouts, participants had a good understanding of what a cluster looked like. For this task, we deliberately chose easy stimuli from the ■ category. Choosing more ambiguous stimuli would have complicated our assessment of whether participants understood the task. This doubt being cleared, we can proceed with the analysis of results.

The Anderson-Darling test [2] showed that accuracy and task completion time are not normally distributed. Hence, we performed a one-tailed Kruskal-Wallis test and Bonferroni correction to determine whether the observed differences were statistically significant, with a corrected threshold of $p = 0.05$. We discarded one single user who systematically answered 1 or 8 clusters (the two extreme options).

## 4.1 Preliminary Remarks

Regarding force-directed layouts (see Figure 7), users counted clusters faster and less accurately with sfdp than with Linlog and Backbone for all combinations of cluster compactness and separability. Linlog leads to consistently faster cluster count judgements than Backbone, while being statistically significantly more accurate for compact separable clusters and on par for other cluster types. Hence, all plots in this section use Linlog as a baseline for comparison with orderable layouts.

In the rest of this section, all figures provided to verify the various hypotheses always include a pair of plots, see Figure 8 for example. On the left, a boxplot comparing the distribution of accuracy in all four $p_{in} \times p_{out}$ quadrants □■■, divided by visualization type ↕.

On the right, a matrix visualization shows the p-values of all pairwise comparisons with Bonferroni correction applied across all 16 combinations of layout type and cluster type. Dark cells correspond to statistically significant differences ($p \le 0.05$). We focus on the four 4 × 4 diagonal blocks, outlined in red in the matrix, corresponding to the quadrants. In the interest of space, the plots corresponding to task completion time are provided in supplemental material, as well as plots comparing Backbone or sfdp baselines to orderable layouts.

## 4.2 Hypothesis H1 (✔): Orderable Node-Link Layouts Improve Cluster Saliency Over Linlog Layouts

Figure 8 shows that we can confirm H1 for loose and/or inseparable clusters □■■ for GEN-ordered orderable layouts, i.e., when the nodes are placed in the same order they were generated. In these three cluster settings, participants using the three orderable layouts ↕○↔ achieve 100% median accuracy on cluster count judgements, whereas Linlog ↕ lags significantly behind at 67% to 80%. Besides the 33% median accuracy gains, the orderable layouts achieve a median time up to 2 seconds (25%) shorter than Linlog (see supplemental material). For compact separable clusters ■, Linlog ↕, and all orderable layouts ↕○↔ are equally excellent (median accuracy of 100% with little variance). Except radial ◀↔ that has a median accuracy of 100% but a slightly higher variance. In passing, Backbone ↕ and sfdp ↕ lag clearly behind GEN-ordered orderable layouts ↕○↔ even in the case of compact separable clusters ■ (see supplemental material).

The situation is more nuanced regarding user performance with the CR and OLO ordering methods. With CR (see Figure 9), orderable layouts ↕○↔ lead to more accurate cluster count judgement for inseparable clusters □■■, and only partially for loose separable clusters ■. In the case of compact separable clusters ■, Linlog wins, although all layouts achieve 100% median accuracy. The CR-ordered layouts ↕○↔ show more variance than Linlog. Participants are consistently statistically significantly slower with CR-ordered radial layout ◀↔ than the other layouts, especially with respect to compact clusters ■■ (see supplemental Figures 13–17). With Backbone and sfdp, users are less accurate than with CR-ordered layouts in all four quadrants (see supplemental Figure 20 and Figure 26).

In Figure 10, OLO-ordered layouts ↕○↔ lead to more accurate cluster counts than Linlog ↕, in the case of loose clusters □■■. They are on par regarding compact inseparable clusters ■, and Linlog ↕ wins comfortably in the case of compact separable clusters ■.

## 4.3 Hypothesis H2 (x): OLO Beats CR at Cluster Saliency

H2 does not hold. Figure 11 and Figure 12 show that CR is equivalent to OLO in most cluster settings, except for arc layouts ↕ in the case of loose inseparable clusters □■■ and compact separable clusters ■■ where CR is better. Both CR and OLO are behind GEN, the originally generated node order, by much, across all four quadrants.

## 4.4 Hypothesis H3 (x): Beats at Cluster Saliency

H3 does not hold. There is no statistically significant difference between arc ↕ and symmetric arc ◀ layouts, for any cluster type, neither in terms of accuracy (see Figure 8 and Figure 9), nor in terms of task completion time (see supplemental Figure 13 and Figure 14).
<figure><img src="image_6.png" /><figcaption>Fig. 5: A 51-node extract from the co-occurrence network of the characters of *Les Misérables*, the novel of Victor Hugo.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 6: The 100-node network used in the drawing task. The cluster outlines show that the users understood the cluster identification task.</figcaption></figure>

## 4.5 Additional Findings

Network size affects force-directed layouts. Besides our hypotheses, we found that the accuracy of all three force-directed layouts decreases as network size increases (see Table 1 in supplemental material). The impact of network size on cluster count in orderable layouts is more complex and requires further research.

Global patterns vs. local patterns. In Figure 6, the superposition of cluster outlines drawn by the study participants reveals where they have more often identified clusters. While there were four clusters in the ground truth for this particular graph, the participants counted five clusters based on Linlog, four based on the arc, and symmetric arc layouts and six with the radial layout. This suggests that arc layouts might emphasize more the global cluster structure, while Linlog and radial layouts might promote local structures. This mere assumption requires experimental validation.

## 5 DISCUSSION

Based on our results, we discuss the performance of orderable layouts at cluster detection, the limitations of this study and formulate guidelines for the use of orderable layouts.

### 5.1 Cluster Detection in Orderable Layouts

In this study, we compared three orderable node-link layouts to three force-directed node-link layouts. Linlog, Backbone and sfdp. Our empirical results confirm previous findings that Linlog and Backbone outperform sfdp for the cluster perception task, and that Linlog is better or equivalent to Backbone [60].

Consistently with prior work on cluster perception in matrix visualizations [41, 42, 68, 70], our results also show that the performance

of orderable layouts at the cluster detection task depends on the seriation method. We extend this knowledge to understudied orderable node-link layouts and provide an empirical validation across the cluster compactness and separability quadrants. In our study, the original node order (GEN) resulting from the graph generator leads to a much more accurate and faster cluster count judgement than the node orders given by CR and OLO (with Jaccard distance and average linkage). In a sense, GEN is a very good reflection of the known ground truth. Both CR and OLO achieve a high median accuracy from 75% to 85% for the hardest, loose and/or inseparable cluster types. In the easy case of compact separable clusters, both CR and OLO achieve a median accuracy of 100%, with a statistically significant edge for CR which has a smaller variance than OLO. In the absence of a known ground truth, CR is hence an excellent seriation method for visual cluster detection.

Our results also show that, subject to a suitable node ordering, orderable node-link diagrams outperform Linlog, the best force-directed node-link layout, for the cluster identification task, in the case of inseparable clusters, both compact and loose, and also in the case of separable loose clusters. This is the case of GEN-ordered, CR-ordered and OLO-ordered orderable layouts (see Figure 8, Figure 9 and Figure 10). Users achieve very high accuracies with the GEN ordering of nodes, with median accuracy scores of 100% in all quadrants, up to 33% better than Linlog. These new findings suggest that orderable node-link layouts combined with a suitable node ordering method can complement the analyst's toolbox for cluster identification beyond the pristine case of compact separable clusters. For this latter case, we find that CR-ordered orderable node-link layouts and the Linlog layout achieve 100% median accuracy for the cluster identification task, while the orderable layouts are better for the more challenging cluster types (see Figure 9).

Based on the computational benchmark of Behrisch et al. [11] for
adjacency matrices, cluster perception is well served if the ordering method is based on a clustering approach. This is confirmed empirically by our observation that the orderable layouts ordered by OLO achieve between 70% and 85% median accuracy (Figure 12). As long as the analyst needs to identify clusters in an overview visualization, any clustering-based order applied to nodes will induce the appearance of clusters in orderable layouts. Since, among other aspects, clusters may vary in shape, size, number and density, different clustering methods will lead to more or less useful node orders/overview visualizations. Similarly, different force-directed approaches lead to more or less useful layouts. In our study, CR, a seriation method not based on clustering, did better than OLO, which is based on agglomerative hierarchical clustering, with respect to arc diagrams with compact separable clusters (Figure 12). A possible explanation is that the Jaccard distance employed by OLO in this experiment did not cope well with the many between-cluster links, while the objective to reduce edge-crossings of CR is less sensitive to this type of noise. Besides the global patterns revealed by clustering-based seriation methods, some of these methods can also optimize for more local patterns, e.g., OLO optimizes node order locally. Local optimization might address gaps identified by Noack, such as promoting the perception of missing details concerning the internal structure of clusters and relationships between clusters. Also, the different link shapes (arcs, symmetric arcs, straight lines) and node positions inherent to each layout seem to have different effects on the perception of (sub-)clusters, as shown by the annotated cluster areas in Figure 6. A formal validation is still needed for such sub-cluster level tasks, though.

Earlier user studies by Okoe et al. [70] and Nobre et al. [68] found that ordered adjacency matrices outperform force-directed layouts, for cluster identification. We introduce a new possibility, consisting in using orderable node-link layouts for this task. To keep the size of our experiment manageable, and the duration of participant sessions reasonable, we left adjacency matrices out of the scope of this study. Now that it has become clear that orderable layouts can outperform by much some of the best force-directed node-link layouts, subject to a suitable node order, a future user study could compare them to similarly ordered matrices in terms of cluster perception and explore a larger number of ordering methods. Yet, adjacency matrices rely on a visual metaphor deemed unfamiliar by most users who often prefer node-link diagrams [34]. The path finding task is also challenging with matrix visualizations, due to the duplication of nodes on the sides of the matrix. Whether this task is better supported by orderable node-link layouts thanks to the node-link metaphor is an open question. In general, more work is needed on the evaluation of orderable node-link layouts to determine which other graph analysis tasks they can effectively support.

For the cluster detection task, Abdelaal et al. [1] found that bipartite diagrams ordered according to agglomerative hierarchical clustering perform worse than force-directed node-link layouts and matrices, especially for sparse networks. Unlike previous work by Okoe et al. [70]

and Nobre et al. [68], Abdelaal et al. [1] did not report any statistically significant difference in terms of cluster perception between matrices and node-link layouts generated by neato [29] (layout based on multi-dimensional scaling). Such a disagreement between different studies may usually be explained by differences in the experimental protocol. This points to the importance of replication studies in the visualization field, and the necessity to share openly as much information as possible, including training materials, data sets etc. Towards this, we release in supplementary material all the stimuli used in this user study, along with the corresponding graph data sets, and the training material.

From a visual perception perspective, the saliency of clusters in force-directed node-link layouts, e.g., Linlog, exploits two principles: the Gestalt proximity principle entailing that nodes whose position is close in the 2D plane tend to be seen as a cluster, and the difference in luminosity induced by the locally high edge clutter within clusters in contrast to the rather sparse link connectivity elsewhere, especially in many real network data sets. In this experiment, we did our best to enhance the readability of the stimuli resulting from Linlog, for example, by increasing node size and link thickness in the larger 300-node networks to compensate for the zoom out effect resulting from fitting a larger drawing in a fixed-size display and, hence, to ensure a good readability. In contrast, our study used a basic implementation of orderable node-link layouts, where clusters are visually characterized by edge concentrations only. Orderable layouts could be further enhanced by exploiting the Gestalt proximity principle too, i.e., by introducing gaps between clusters along the underlying geometric locus, when the clusters are known. We expect such gaps to improve the visual saliency of clusters in orderable layouts, which is supported by a prior qualitative study on graph layouts based on space-filling curves [61]. One might also study the effect of edge bundling on the cluster identification task. Edge bundling has initially been applied on radial diagrams, given an overarching hierarchy [44]. It has later been extended to preserve the perception of paths [85]. Since edge bundling affects drastically the way edges are routed, and the overall edge clutter, it might as well impact cluster perception. While prior work has explored edge bundling for radial graphs and general 2D graph layouts, work on edge bundling for arc diagrams is scarce. The results of this study constitute a stepping stone in this direction, and a baseline against which future work could compare cluster perception for both edge-bundled orderable and force-directed node-link layouts.

Finally, an inconvenient of orderable layouts is their relatively inefficient use of display space. Indeed, minimizing the area of the drawing is a known graph drawing aesthetic rule [8]. In this respect, vanilla arc diagrams obviously use half the area of their symmetric variant, but much more than the equivalent radial layout (it is easy to prove that arc diagrams use $\pi/2 \approx 5$ times the area of equivalent radial diagrams). This might matter when integrating orderable layouts in a broader context, for example in a multiple coordinated view setting with other visualizations. On the one hand, arc diagrams can be easily displayed on the side of a matrix view, like in MatLink [42]. But, in any case, their nodes may need to be scaled up to ensure sufficient visibility. In this study, we scaled the different layouts to use all the available display area, and ensured a good visibility of the nodes and links in all layouts (see Section 3.1).

## 5.2 Limitations

**Data generation** Much research has gone into generating synthetic graphs meeting certain requirements, e.g., structural patterns characterized by common graph metrics such as degree distribution, or clustering coefficient [13]. The use of synthetic graphs is of practical value for large-scale benchmarking activities, for which it is difficult to gather enough real graph data sets with comparable features, and also to be able to control the key properties of graphs for a specific investigation. Also, similar to Anscombe's quartet, previous work by Chen et al. has shown that very different graphs might share the same summary statistics [20]. So, even when researchers use popular graph generators, it is difficult in practice to control for everything, and there is a large overhead associated with the preparation of graph data sets.

In this study, we used the Gaussian random partition graph genera-

<figure><img src="image_8.png" /><figcaption>Fig. 7: Cluster count accuracy (top) and completion time (bottom) for sizes=all, clusters=all, layouts={Linlog, Backbone, sfdp}.</figcaption></figure>
<figure><img src="image_9.png" /><figcaption>Fig. 8: Cluster count accuracy for sizes = all, clusters = all, order = GEN, baseline = Linlog. The dark matrix cells correspond to $p \le 0.05$.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Fig. 9: Cluster count accuracy for sizes = all, clusters = all, order = CR, baseline = Linlog. The dark matrix cells correspond to $p \le 0.05$.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Fig. 10: Cluster count accuracy for sizes = all, clusters = all, order = OLO, baseline = Linlog. The dark matrix cells correspond to $p \le 0.05$.</figcaption></figure>

tor [16] of NetworkX [38], to control the number of nodes, the number of clusters and the internal and external link probabilities of these clusters. We wanted to have small and large clusters in the same network, to better mimic real networks. Still, one limitation of our approach is that, in any given graph, we have one cluster type [4]. In real graphs, a mix of compact and loose clusters exist, with more or less coupling between them. An alternate data generation approach could consist in creating the clusters separately with the desired mix of inner link densities and cluster sizes, before injecting external links, as needed. Yet, our experiment provides a good complement to existing work on cluster perception, and a baseline for future inquiries.

**Cluster validity** When generating graphs with loose and/or inseparable clusters, given the stochastic nature of the generative process some clusters may be so loose and inseparable not to qualify as clusters. One would ideally have a measure of the clustering tendency of the generated data, and only keep graphs with a sufficient clustering tendency. This is however a complex task. Global measures associated to the presence of clusters, such as clustering coefficient or maximum modularity, are convenient, but they cannot tell whether individual clusters are too loose or inseparable. Also, maximum modularity can be very high even in random networks [36], a problem shared with other descriptive methods for cluster detection [72].

A principled way to assess clustering tendency would be to compute statistical significance [53], which is also a complex task with strong assumptions. First, some work proposing significance testing for clustering focus on the whole set of clusters, e.g., [91], where individual non-significant clusters might occur within significant clusterings [72]. Recent work explores how to test individual clusters [71], but there is

no standard way of doing it yet, and these methods rely themselves on assumptions such as the null model against which statistical significance is computed. Since different cluster types may exist, and different clustering methods are based on different definitions of what a cluster is, we conclude that clustering tendency should rather be considered while interpreting the results of the empirical study, rather than as a hard filter to decide which stimuli should be included in the study. In particular, if for some stimuli the participants fail to identify clusters for all the tested layout methods, an explanation may be that those clusters are too loose and inseparable to even qualify as clusters. If the correct number of clusters is consistently identified using one method, it seems reasonable to consider this as empirical evidence that the generated clusters are valid. As this paper aims to compare different layouts, and not to study the level of compactness/separability where specific methods start failing, this evidence suffices to reach our conclusions.

Like in Figure 3, we used matrix visualizations to check the existence of clusters in every generated graph. Future work may seek to determine the frontiers of the cluster validity space empirically by generating many graphs with decreasing cluster compactness and/or separability until users cease to catch a signal in the stimuli. Such a principled approach would provide useful insights, to guide graph generation for similar studies on cluster perception. In this study, we have seen that GEN, the node generation order, leads to significantly faster and more accurate cluster count judgements, than OLO and CR. This may occur when the clusters are generated one after the other. The 20% accuracy gap between GEN and OLO/CR calls for more adapted clustering methods for the relatively loose and/or inseparable clusters considered here.

**Layout optimization** Since the output of most graph layout algo-
<figure><img src="image_12.png" /><figcaption>Fig. 11: Cluster count accuracy for sizes = all, clusters = loose, orders = { GEN ■, CR ■, OLO ■}. The dark matrix cells correspond to $p \le 0.05$</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>Fig. 12: Cluster count accuracy for sizes = all, clusters = compact, orders = { GEN ■, CR ■, OLO ■}. The dark matrix cells correspond to $p \le 0.05$</figcaption></figure>

rithms depends on hyperparameter values, researchers should strive to evaluate algorithms at their best. For example, a computational study might seek to find the optimal hyperparameter values to refine each of the three force-directed layouts for each of the 60 graphs included in our study. This would yet require establishing which aesthetic rules best capture cluster saliency, which is an open question. In this study, we have relied on published best practice, e.g., the use of *quadrilateral Simmelian Backbone*, and the fact that default settings are usually chosen to give good results in general. Lastly, OLO and CR are both linear seriation methods, which may be suboptimal for radial layouts. Future work may consider circular seriation methods too [4].

**Crowdsourcing** One benefit of crowdsourced studies is the access to a large and diverse participant sample. While the researcher has limited control over the setup, e.g., software, hardware and ergonomic aspects, we selected participants with a suitable display size: laptops and desktop monitors, excluding all handheld devices. The high levels of accuracy, and short task completion times, achieved by the study participants make us believe that the experimental setting was suitable. We were also keen to ensure that the participants understood the task at hand, without being able to observe them directly. To mitigate any issues, we had several iterations over the training material to make the video tutorials as clear and as short as possible, prior to the study. Ultimately, the short drawing task at the end of each stimulus batch, i.e., for each visualization type, allowed us, post hoc, to quality control and check for any major misunderstanding of the task.

## 5.3 Guidelines

Our study compared three force-directed layouts (ForceAtlas2 with Linlog energy, Backbone and sfdp) to three orderable layouts in terms of cluster perception in graphs having four different types of clusters (summarized in Figure 2). The study revealed how, depending on cluster type, certain visualizations outperform others. Hence, we can formulate the following guidelines:

* **G1** When node clusters are of analytical interest, use an orderable node-link layout to get an overview of the cluster structure. **Observation:** For graphs having loose and/or inseparable clusters, orderable layouts, subject to node order, can outperform the best force-directed layouts. Therefore, only using e.g. a force-based layout may lead to a wrong perception of the cluster structure.

* **G2** Check the agreement between force-directed and orderable node-link layouts. **Observation:** When the graph has ideal clusters, i.e.,

compact and separable, all the tested layouts promote the emergence of clusters. Therefore, if force-directed and orderable node-link layouts show the same cluster structure, the choice of visualization can then be based on additional tasks to be addressed.

* **G3** When an orderable node-link diagram is chosen as a visualization, use CR or OLO. **Observation:** Both CR and OLO seriation algorithms achieve good results in terms of cluster identification.

These guidelines are valid within the experimental conditions used in our study. While our results cannot be generalized to all layout algorithms under all choices of hyperparameters, the force-directed layouts we used were informed by the literature and are commonly used. We also note that each of our stimuli only contains a single type of clusters, so that we could use this as an independent variable. While we cannot generalize our results to cases with different types of clusters in the same graph, we believe that observations about specific cluster types will still apply to these cases.

# 6 CONCLUSION

Clusters are common and important network patterns. We presented the first user study investigating the visual saliency of graph clusters in orderable node-link layouts under varying conditions of cluster compactness and separability. We found empirically that the use of orderable node-link layouts with an appropriate node ordering algorithm achieves fast and accurate cluster detection, surpassing significantly several force-directed layouts (Linlog, Backbone and sfdp), when dealing with loose and/or inseparable clusters. Only in the ideal case of compact and separable clusters, the Linlog node-link layout is on par with or better than orderable node-links diagrams. Moreover, the crossing reduction heuristic (i.e., the barycenter heuristic) outperforms the optimal leaf ordering seriation method in the case of loose and/or inseparable clusters.

Future perceptual studies might explore other graph motifs, e.g., hubs, and other tasks like path finding to better understand the pros and cons of orderable node-link layouts. One might also extend the study to include synthetic data sets with overlapping clusters, and real data sets with application-driven analytical goals. Finally, one might investigate why the orderable layouts are good at showing clusters. The rationale for H1 is that these layouts create locally high link concentrations. Insights into the specific features associated to better cluster perception with orderable layouts may lead to new methods, e.g., to quantify layout quality for this task automatically.
## SUPPLEMENTAL MATERIALS

All supplemental materials are available on OSF at https://osf.io/kc3dg/, released under a CC BY 4.0 license. In particular, they include

1. A zip file containing **I) the material used to train study participants (video tutorials and training data sets). II) The stimuli used in the user study in various formats (SVG, PDF), and III) All graph data sets** in GraphML format to support study replication.

2. Additional statistics including I) a comparison of cluster count completion time between the Linlog layout and orderable layouts (accuracy is already analyzed above), II) a comparison of completion time between all orderable layouts across all cluster types, III) a comparison of the accuracy and completion time of backbone, respectively sfdp, to orderable layouts.

## ACKNOWLEDGMENTS

The authors wish to thank Helen Purchase for her valuable advice about the experimental setup. This work was supported in part by a grant from Luxembourg FNR (# INTER/ANR/20/14956115).

## REFERENCES

[1] M. Abdelaal, N. D. Schiele, K. Angerbauer, K. Kurzhals, M. Sedlmair, and D. Weiskopf. Comparative evaluation of bipartite, node-link, and matrix-based network representations. *IEEE Trans. Visual. Comput. Graphics*, 29(1):896–906, 2023. doi: 10.1109/TVCG.2022.3209427 2, 3, 4, 7

[2] T. W. Anderson and D. A. Darling. A test of goodness of fit. *J. Am. Stat. Assoc.*, 49(268):765–769, 1954. doi: 10.1080/01621459.1954.10501232 5

[3] O. Arbelaitz, I. Gurrutxaga, J. Muguerza, J. M. Pérez, and I. Perona. An extensive comparative study of cluster validity indices. *Pattern Recognition*, 46(1):243–256, 2013. doi: 10.1016/j.patcog.2012.07.021 3

[4] S. Armstrong, C. Guzmán, and C. A. Sing Long. An optimal algorithm for strict circular seriation. *SIAM Journal on Mathematics of Data Science*, 3(4):1223–1250, 2021. doi: 10.1137/21M139356X 9

[5] A. S. Asratian, T. M. Denley, and R. Häggkvist. *Bipartite graphs and their applications*, vol. 131. CUP, 1998. doi: 10.1017/CBO9780511984068 2

[6] Z. Bar-Joseph, D. K. Gifford, and T. S. Jaakkola. Fast optimal leaf ordering for hierarchical clustering. *Bioinformatics*, 17(suppl_1):S22–S29, 2001. doi: 10.1093/bioinformatics/17.suppl_1.S22 2, 3, 4

[7] M. Bastian, S. Heymann, and M. Jacomy. Gephi: An open source software for exploring and manipulating networks. *Proc. Int. AAAI Conf. Web Social Media*, 3(1):361–362, 2009. doi: 10.1609/icwsm.v3i1.13937 3

[8] G. D. Battista, P. Eades, R. Tamassia, and I. G. Tollis. *Graph Drawing: Algorithms for the Visualization of Graphs*. Prentice Hall PTR, USA, 1st ed., 1998. 2, 4, 7

[9] F. Beck, M. Burch, S. Diehl, and D. Weiskopf. A taxonomy and survey of dynamic graph visualization. *Computer Graphics Forum*, 36(1):133–159, 2017. doi: 10.1111/cgf.12791 2

[10] P. Bedi and C. Sharma. Community detection in social networks. *Wiley interdisciplinary reviews: Data mining and knowledge discovery*, 6(3):115–135, 2016. doi: 10.1002/widm.1178 1

[11] M. Behrisch, B. Bach, N. Henry Riche, T. Schreck, and J.-D. Fekete. Matrix reordering methods for table and network visualization. *Computer Graphics Forum*, 35(3):693–716, 2016. doi: 10.1111/cgf.12935 1, 2, 4, 6

[12] J. Bertin. *Semiology of graphics: Diagrams, networks, and maps*. University of Wisconsin Press., 1983. 1

[13] A. Bonifati, I. Holubová, A. Prat-Pérez, and S. Sakr. Graph generators: State of the art and open challenges. *ACM Computing Surveys*, 53(2), article no. 36, 30 pages, 2020. doi: 10.1145/3379445 7

[14] R. Bonneau. Learning biological networks: from modules to dynamics. *Nat. Chem. Biol.*, 4(11):658–664, 2008. doi: 10.1038/nchembio.122 1

[15] I. Borg and J. Lingoes. *Multidimensional similarity structure analysis*. Springer, New York, 2012. doi: 10.1007/978-1-4612-4768-5 2

[16] U. Brandes, M. Gaertler, and D. Wagner. Experiments on graph clustering algorithms. In *Proc. ESA*, pp. 568–579. Springer Berlin, 2003. doi: 10.1007/978-3-540-39658-1_52 3, 8

[17] U. Brandes and C. Pich. Eigensolver methods for progressive multidimensional scaling of large data. In *Proc. GD*, pp. 42–53. Springer, 2006. doi: 10.1007/978-3-540-70904-6_6 2

[18] M. Burch, W. Huang, M. Wakefield, H. C. Purchase, D. Weiskopf, and J. Hua. The state of the art in empirical user evaluation of graph visualizations. *IEEE Access*, 9:4173–4198, 2021. doi: 10.1109/ACCESS.2020.3047616 4

[19] C.-H. Chen. Generalized association plots: Information visualization via iteratively generated correlation matrices. *Statistica Sinica*, pp. 7–29, 2002. doi: 10.1007/978-3-030-04421-4_33 7

[20] H. Chen, U. Soni, Y. Lu, R. Maciejewski, and S. Kobourov. Same stats, different graphs. In *Proc. GD*, pp. 463–477. Springer, Cham, 2018. doi: 10.1007/978-3-030-04421-4_33 7

[21] K.-T. Chen, T. Dwyer, B. Bach, and K. Marriott. It's a wrap: Toroidal wrapping of network visualisations supports cluster understanding tasks. In *Proc. CHI*, pp. 1–12, 2021. doi: 10.1145/3411764.3445439 2

[22] Y. Cheng and G. Church. Biclustering of expression data. In *Proc. ISMB*, vol. 8, pp. 93–103, 2000. doi: 10.1145/568522.568523 2

[23] D. L. Davies and D. W. Bouldin. A cluster separation measure. *IEEE Transactions on Pattern Analysis and Machine Intelligence*, PAMI-1(2):224–227, 1979. doi: 10.1109/TPAMI.1979.4766909 3

[24] S. Di Bartolomeo, T. Crnovrsanin, D. Saffo, E. Puerta, C. Wilson, and C. Dunne. Evaluating graph layout algorithms: A systematic review of methods and best practices. *Computer Graphics Forum*, n/a(n/a):e15073. doi: 10.1111/cgf.15073 3

[25] J. Díaz, J. Petit, and M. Serna. A survey of graph layout problems. *ACM Comput. Surv.*, 34(3):313–356, 2002. doi: 10.1145/568522.568523 2

[26] G. M. Draper, Y. Livnat, and R. F. Riesenfeld. A survey of radial methods for information visualization. *IEEE Trans. Visual. Comput. Graphics*, 15(5):759–776, 2009. doi: 10.1109/TVCG.2009.23 2

[27] T. Dwyer and Y. Koren. Dig-CoLa: directed graph layout through constrained energy minimization. In *Proc. IEEE INFOVIS*, pp. 65–72, 2005. doi: 10.1109/INFVIS.2005.1532130 2

[28] T. Dwyer, K. Marriott, and M. Wybrow. Dunnart: A constraint-based network diagram authoring tool. In *Proc. GD*, pp. 420–431. Springer, Berlin, 2009. doi: 10.1007/978-3-642-00219-9_41 2

[29] J. Ellson, E. Gansner, L. Koutsofios, S. C. North, and G. Woodhull. Graphviz— open source graph drawing tools. In *Proc. GD*, pp. 483–484. Springer, Berlin, 2002. doi: 10.1007/3-540-45848-4_57 2, 7

[30] J.-D. Fekete. Reorder.js: A JavaScript Library to Reorder Tables and Networks. *IEEE VIS* 2015, 2015. Poster. 1, 2, 3

[31] T. M. J. Fruchterman and E. M. Reingold. Graph drawing by force-directed placement. *Software: Practice and Experience*, 21(11):1129–1164, 1991. doi: 10.1002/spe.4380211102 2, 3

[32] J. Fuchs, F. L. Dennig, M.-V. Heinle, D. A. Keim, and S. Di Bartolomeo. Exploring the design space of BioFabric visualization for multivariate network analysis. *Computer Graphics Forum*, 43(3):e15079, 2024. doi: 10.1111/cgf.15079 2

[33] E. R. Gansner, Y. Koren, and S. North. Graph drawing by stress majorization. In *Proc. GD*, pp. 239–250. Springer, 2005. doi: 10.1007/978-3-540-31843-9_25 2

[34] M. Ghoniem, J.-D. Fekete, and P. Castagliola. On the readability of graphs using node-link and matrix-based representations: A controlled experiment and statistical analysis. *Information Visualization*, 4(2):114–135, 2005. doi: 10.1057/palgrave.ivs.9500092 1, 7

[35] H. Gibson, J. Faith, and P. Vickers. A survey of two-dimensional graph layout techniques for information visualisation. *Information Visualization*, 12(3-4):324–357, 2013. doi: 10.1177/1473871612455749 1, 2

[36] R. Guimerà, M. Sales-Pardo, and L. A. N. Amaral. Modularity from fluctuations in random graphs and complex networks. *Physical Review E*, 70(2):025101, 2004. doi: 10.1103/PhysRevE.70.025101 8

[37] S. Hachul and M. Jünger. Drawing large graphs with a potential-field-based multilevel algorithm. In *Proc. GD*, pp. 285–295. Springer, 2005. doi: 10.1007/978-3-540-31843-9_29 2

[38] A. A. Hagberg, D. A. Schult, and P. J. Swart. Exploring network structure, dynamics, and function using NetworkX. In *Proc. Python in Science Conference*, pp. 11–15. Pasadena, CA USA, 2008. doi: 10.1145/1794514.1805128 2

[39] D. Harel and Y. Koren. Graph drawing by high-dimensional embedding. In *Proc. GD*, pp. 207–219. Springer Berlin, 2002. doi: 10.1007/3-540-36151-0_20 2

[40] J. Heer, M. Bostock, and V. Ogievetsky. A tour through the visualization zoo. *Commun. ACM*, 53(6):59–67, 2010. doi: 10.1145/1794514.1805128 2

[41] N. Henry and J.-d. Fekete. MatrixExplorer: a dual-representation system to explore social networks. *IEEE Trans. Visual. Comput. Graphics*, 12(5):677–684, 2006. doi: 10.1109/TVCG.2006.160 1, 6

[42] N. Henry and J.-D. Fekete. MatLink: Enhanced matrix visualization for analyzing social networks. In *Proc. INTERACT*, pp. 288–302. Springer Berlin, 2007. doi: 10.1007/978-3-540-74800-7_24 3, 4, 6, 7

[43] I. Herman, G. Melançon, and M. Marshall. Graph visualization and navigation in information visualization: A survey. *IEEE Trans. Visual.*
Comput. Graphics, 6(1):24-43, 2000. doi: 10.1109/2945.841119 1, 2

[44] D. Holten. Hierarchical edge bundles: Visualization of adjacency relations in hierarchical data. *IEEE Transactions on Visualization and Computer Graphics*, 12(5):741–748, 2006. doi: 10.1109/TVCG.2006.147 7

[45] Y. Hu. Efficient, high-quality force-directed graph drawing. *Mathematica journal*, 10(1):37–71, 2006. 2

[46] M. Jacomy, T. Venturini, S. Heymann, and M. Bastian. ForceAtlas2, a continuous graph layout algorithm for handy network visualization designed for the gephi software. *PloS one*, 9:e98679, 2014. doi: 10. 1371/journal.pone.0098679 3

[47] D. E. Knuth. *The Stanford GraphBase: A Platform for Combinatorial Computing*. Addison-Wesley, USA, 1993. 5

[48] S. G. Kobourov, T. Mchedlidze, and L. Vonessen. Gestalt principles in graph drawing. In *Proc. GD*, pp. 558–560. Springer, Cham, 2015. doi: 10. 1007/978-3-319-27261-0 50 1, 2, 4

[49] Y. Koren, L. Carmel, and D. Harel. ACE: a fast multiscale eigenvectors computation for drawing huge graphs. In *Proc. IEEE INFOVIS*, pp. 137– 144, 2002. doi: 10.1109/INFVIS.2002.1173159 2

[50] J. F. Kruiger, P. E. Rauber, R. M. Martins, A. Kerren, S. Kobourov, and A. C. Telea. Graph layouts by t-SNE. *Computer Graphics Forum*, 36(3):283–294, 2017. doi: 10.1111/cgf.13187 2

[51] M. Krzywinski, J. Schein, I. Birol, J. Connors, R. Gascoyne, D. Horsman, S. J. Jones, and M. A. Marra. Circos: An information aesthetic for comparative genomics. *Genome Research*, 19(9):1639–1645, 2009. doi: 10.1101/gr.092759.109 1

[52] D. Kumar and J. C. Bezdek. Visual approaches for exploratory data analysis: A survey of the visual assessment of clustering tendency (VAT) family of algorithms. *IEEE Systems, Man, and Cybernetics Magazine*, 6(2):10–48, 2020. doi: 10.1109/MSMC.2019.2961163 3

[53] A. Lancichinetti, F. Radicchi, J. J. Ramasco, and S. Fortunato. Finding Statistically Significant Communities in Networks. *PLOS ONE*, 6(4):e18961, 2011. doi: 10.1371/journal.pone.0018961 8

[54] B. Lee, C. Plaisant, C. S. Parr, J.-D. Fekete, and N. Henry. Task taxonomy for graph visualization. In *Proc. BELIV'06*, pp. 1–5. ACM, New York, 2006. doi: 10.1145/1168149.1168168 1, 2

[55] J. K. Lenstra. Clustering a data array and the traveling-salesman problem. *Operations Research*, 22(2):413–414, 1974. doi: 10.1287/opre.22.2.413 2

[56] I. Liiv. Seriation and matrix reordering methods: An historical overview. *Stat. Anal. Data Min.*, 3(2):70–91, 2010. doi: 10.1002/sam.10071 2

[57] E. Mäkinen and H. Siirtola. The barycenter heuristic and the reorderable matrix. *Informatica*, 29:357–364, 2005. 2, 3, 4

[58] F. McGee, M. Ghoniem, G. Melançon, B. Otjacques, and B. Pinaud. The state of the art in multilayer network visualization. *Computer Graphics Forum*, 38(6):125–149, 2019. doi: 10.1111/cgf.13610 2

[59] M. J. McGuffin. Simple algorithms for network visualization: A tutorial. *Tsinghua Science and Technology*, 17(4):383–398, 2012. doi: 10.1109/TST. 2012.6297585 2

[60] A. Meidiana, S.-H. Hong, P. Eades, and D. Keim. A quality metric for visualization of clusters in graphs. In *Proc. GD*, pp. 125–138. Springer, Cham, 2019. doi: 10.1007/978-3-030-35802-0 10 1, 2, 3, 6

[61] C. Muelder and K.-L. Ma. Rapid graph layout using space filling curves. *IEEE Transactions on Visualization and Computer Graphics*, 14(6):1301– 1308, 2008. doi: 10.1109/TVCG.2008.158 2, 7

[62] C. Mueller, B. Martin, and A. Lumsdaine. A comparison of vertex ordering algorithms for large graph visualization. In *Proc. PacificVis*, pp. 141–148. IEEE, 2007. doi: 10.1109/APVIS.2007.329289 2

[63] T. Nagel and E. Duval. A visual survey of arc diagrams. In *IEEE Visualization*, Posters, 2013. 2

[64] A. Noack. An energy model for visual graph clustering. In *G. Liotta, ed.*, *Proc. GD*, pp. 425–436. Springer, Berlin, 2004. doi: 10.1007/978-3-540 -24595-7 40 1, 2, 3

[65] A. Noack. Energy models for graph clustering. *J. Graph Algorithms Appl.*, 11:453–480, 2007. doi: 10.7155/jgaa.00154 1, 2

[66] A. Noack. Modularity clustering is force-directed layout. *Phys. Rev. E*, 79(2):026102, 2009. doi: 10.1103/PhysRevE.79.026102 3

[67] C. Nobre, M. Meyer, M. Streit, and A. Lex. The state of the art in visualizing multivariate networks. *Computer Graphics Forum*, 38(3):807– 832, 2019. doi: 10.1111/cgf.13728 2

[68] C. Nobre, D. Wootton, L. Harrison, and A. Lex. Evaluating multivariate network visualization techniques using a validated design and crowdsourcing approach. In *Proc. CHI*, p. 1–12. ACM, New York, 2020. doi: 10. 1145/3313831.3376381 2, 4, 6, 7

[69] A. Nocaj, M. Ortmann, and U. Brandes. Untangling the hairballs of multi-

centered, small-world online social media networks. *J. Graph Algorithms Appl.*, 19(2):595–618, 2015. doi: 10.7155/jgaa.00370 2, 3

[70] M. Okoe, R. Jianu, and S. Kobourov. Node-link or adjacency matrices: Old question, new insights. *IEEE Trans. Visual. Comput. Graphics*, 25(10):2940–2952, 2019. doi: 10.1109/TVCG.2018.2865940 2, 4, 6, 7

[71] J. Palowitch. Computing the statistical significance of optimized communities in networks. *Scientific Reports*, 9(1):18444, 2019. doi: 10.1038/ s41598-019-54708-8 8

[72] T. P. Peixoto. *Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths*. Cambridge University Press, 2023. arXiv:2112.00183 [physics, stat]. doi: 10.1017/9781009118897 8

[73] C. Perin, P. Dragicevic, and J.-D. Fekete. Revisiting bertin matrices: New interactions for crafting tabular visualizations. *IEEE Trans. Visual. Comput. Graphics*, 20(12):2082–2091, 2014. doi: 10.1109/TVCG.2014.2346279 2

[74] J. Petit. Experiments on the minimum linear arrangement problem. *ACM J. Exp. Algorithmics*, 8, article no. 2.3, 33 pages, 2004. doi: 10.1145/996546. 996554 2

[75] R. Rao and S. K. Card. The table lens: merging graphical and symbolic representations in an interactive focus+ context visualization for tabular information. In *Proc. CHI*, pp. 318–322. ACM, New York, 1994. doi: 10. 1145/191666.191776 2

[76] L. Rossi and M. Magnani. Towards effective visual analytics on multiplex and multilayer networks. *Chaos, Solitons & Fractals*, 72:68–76, 2015. doi: 10.1016/j.chaos.2014.12.022 5

[77] P. J. Rousseeuw. Silhouettes: A graphical aid to the interpretation and validation of cluster analysis. *Journal of Computational and Applied Mathematics*, 20:53–65, 1987. doi: 10.1016/0377-0427(87)90125-7 3

[78] B. Shneiderman and A. Aris. Network visualization by semantic substrates. *IEEE Transactions on Visualization and Computer Graphics*, 12(5):733– 740, 2006. doi: 10.1109/TVCG.2006.166 2

[79] M. A. Smith, B. Shneiderman, N. Milic-Frayling, E. Mendes Rodrigues, V. Barash, C. Dunne, T. Capone, A. Perer, and E. Gleave. Analyzing (social media) networks with NodeXL. In *Proc. C&T '09*, 10 pages, p. 255–264. ACM, New York, USA, 2009. doi: 10.1145/1556460.1556497 2

[80] W. S. Torgerson. Multidimensional scaling: I. theory and method. *Psychometrika*, 17(4):401–419, 1952. doi: 10.1007/BF02288916 2

[81] J. Urbanek and P. Ringshia. Mephisto: A framework for portable, reproducible, and iterative crowdsourcing. 2023. doi: 10.48550/ARXIV.2301. 05154 5

[82] F. van Ham and B. Rogowitz. Perceptual organization in user-generated graph layouts. *IEEE Transactions on Visualization and Computer Graphics*, 14(6):1333–1339, 2008. doi: 10.1109/TVCG.2008.155 1

[83] C. Vehlow, F. Beck, and D. Weiskopf. Visualizing group structures in graphs: A survey. *Computer Graphics Forum*, 36(6):201–225, 2017. doi: 10.1111/cgf.12872 2

[84] T. von Landesberger, A. Kuijper, T. Schreck, J. Kohlhammer, J. van Wijk, J.-D. Fekete, and D. Fellner. Visual analysis of large graphs: State-of-the-art and future research challenges. *Computer Graphics Forum*, 30(6):1719–1749, 2011. doi: 10.1111/j.1467-8659.2011.01898.x 1, 2

[85] M. Wallinger, D. Archambault, D. Auber, M. Nöllenburg, and J. Peltonen. Edge-path bundling: A less ambiguous edge bundling approach. *IEEE Transactions on Visualization and Computer Graphics*, 28(1):313–323, 2022. doi: 10.1109/TVCG.2021.3114795 7

[86] M. Wattenberg. Arc diagrams: visualizing structure in strings. *Proc. IEEE INFOVIS*, pp. 110–116, 2002. doi: 10.1109/INFVIS.2002.1173155 1, 2

[87] M. Wattenberg. Visual exploration of multivariate graphs. In *Proc. CHI '06*, 9 pages, p. 811–819. ACM, New York, USA, 2006. doi: 10.1145/ 1124772.1124891 2

[88] P. C. Wong, H. Foote, P. Mackey, G. Chin, Z. Huang, and J. Thomas. A space-filling visualization technique for multivariate small-world graphs. *IEEE Transactions on Visualization and Computer Graphics*, 18(5):797– 809, 2012. doi: 10.1109/TVCG.2011.99 2

[89] X. Xie, F. Song, Y. Liu, S. Wang, and D. Yu. Study on the effects of display color mode and luminance contrast on visual fatigue. *IEEE Access*, 9:35915–35923, 2021. doi: 10.1109/ACCESS.2021.3061770 3

[90] V. Yoghourdjian, D. Archambault, S. Diehl, T. Dwyer, K. Klein, H. C. Purchase, and H.-Y. Wu. Exploring the limits of complexity: A survey of empirical studies on graph visualisation. *Visual Informatics*, 2(4):264–282, 2018. doi: 10.1016/j.visinf.2018.12.006 3

[91] P. Zhang and C. Moore. Scalable detection of statistically significant communities and hierarchies, using message passing for modularity. *Proceedings of the National Academy of Sciences*, 111(51):18144–18149, 2014. doi: 10.1073/pnas.14097701118
# APPENDICES

## Task completion time of Linlog versus orderable layouts

<figure><img src="image_14.png" /><figcaption>Fig. 13: Overall task completion time for sizes = all, clusters = all, **order = GEN**, baseline = Linlog. On the right, the dark blue matrix cells correspond to the Bonferroni corrected *p* ≤ 0.05 for all pairwise comparisons. Linlog is significantly (up to 25%) slower than GEN-ordered Arc and Arc symmetric in all quadrants, and slower than radial layouts for compact inseparable clusters.</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>Fig. 14: Overall task completion time for sizes = all, clusters = all, **order = CR**, baseline = Linlog. On the right, the dark blue matrix cells correspond to the Bonferroni corrected *p* ≤ 0.05 for all pairwise comparisons. Linlog is generally as fast as the CR-ordered orderable layouts, except for compact inseparable clusters where arc does significantly better.</figcaption></figure>

<figure><img src="image_16.png" /><figcaption>Fig. 15: Overall task completion time of cluster count for sizes = all, clusters = compact, **order = OLO**, baseline = Linlog. The dark matrix cells correspond to Bonferroni corrected *p* ≤ 0.05 for all pairwise comparisons. Linlog is not significantly different from OLO-ordered orderable layouts.</figcaption></figure>
## Task completion time of orderable layouts for loose and compact clusters

<figure><img src="image_17.png" /><figcaption>Fig. 16: Task completion time for network sizes = all, clusters = **loose**, orders = { GEN ■, CR ■, OLO ■}. On the right, the dark blue matrix cells correspond to the Bonferroni corrected *p* ≤ 0.05 for all pairwise comparisons. GEN-ordered orderable layouts lead to consistently faster cluster count judgements compared to those ordered by OLO and CR with respect to loose clusters.</figcaption></figure>

<figure><img src="image_18.png" /><figcaption>Fig. 17: Task completion time for network sizes = all, clusters = **compact**, orders = { GEN ■, CR ■, OLO ■}. On the right, the dark blue matrix cells correspond to the Bonferroni corrected *p* ≤ 0.05 for all pairwise comparisons. OLO and CR are not statistically significantly different in any of the compact cluster settings. GEN is faster than OLO when combined with arc and symmetric arc layouts. GEN beats CR occasionally with arc and symmetric arc in some compact cluster settings. GEN, CR and OLO are on par when it comes to radial layouts.</figcaption></figure>
Comparison of backbone and orderable layouts

<figure><img src="image_19.png" /><figcaption>Fig. 18: Overall accuracy of cluster count judgments for sizes = all, clusters = all, order = GEN, baseline = backbone. On the right, the dark blue matrix cells correspond to the Bonferroni corrected *p* ≤ 0.05 for all pairwise comparisons. GEN-ordered orderable layouts are significantly (up to 33%) more accurate than backbone for all cluster types. the orderable layouts achieve 100% accuracy, in almost all cluster settings. Radial layouts have a greater variance than arc and arc symmetric.</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>Fig. 19: Task completion time for sizes = all, clusters = all, order = GEN, baseline = backbone. On the right, the dark blue matrix cells correspond to the Bonferroni corrected *p* ≤ 0.05 for all pairwise comparisons. The lack of accuracy of backbone seen in Figure 18 also translates into slower cluster count judgments in all cluster settings. Likewise, radial is always slower than arc layouts.</figcaption></figure>

<figure><img src="image_21.png" /><figcaption>Fig. 20: Overall accuracy of cluster count judgments for sizes = all, clusters = all, order = CR, baseline = backbone. On the right, the dark blue matrix cells correspond to the Bonferroni corrected *p* ≤ 0.05 for all pairwise comparisons. Backbone is less accurate than the CR-ordered orderable layouts in all cluster settings, except in the case of compact inseparable clusters where it cannot be distinguished from radial.</figcaption></figure>
<figure><img src="image_22.png" /><figcaption>Fig. 21: Overall task completion time for sizes = all, clusters = all, order = CR, baseline = backbone. On the right, the dark blue matrix cells correspond to the Bonferroni corrected *p* ≤ 0.05 for all pairwise comparisons. Backbone is significantly slower than CR-ordered orderable layouts for compact clusters, and comparable in the case of loose clusters.</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>Fig. 22: Overall accuracy of cluster count judgments for sizes = all, clusters = all, order = OLO, baseline = backbone. On the right, the dark blue matrix cells correspond to the Bonferroni corrected *p* ≤ 0.05 for all pairwise comparisons. Backbone is less accurate than the OLO-ordered orderable layouts in all cluster settings, except in the case of compact inseparable clusters where it cannot be distinguished from radial.</figcaption></figure>

<figure><img src="image_24.png" /><figcaption>Fig. 23: Overall task completion time for sizes = all, clusters = all, order = OLO, baseline = backbone. On the right, the dark blue matrix cells correspond to the Bonferroni corrected *p* ≤ 0.05 for all pairwise comparisons. Backbone is slower than OLO-ordered orderable layouts for compact and separable clusters. It is comparable to orderable layouts in the other cluster types, except for loose separable and compact inseparable clusters where arc layouts are significantly faster.</figcaption></figure>
Comparison of sfdp and orderable layouts

<figure><img src="image_25.png" /><figcaption>Fig. 24: Overall **accuracy** of cluster count judgments for sizes = all, clusters = all, **order = GEN**, baseline = sfdp. On the right, the dark blue matrix cells correspond to the Bonferroni corrected *p* ≤ 0.05 for all pairwise comparisons. sfdp is significantly (up to 60%) slower than GEN-ordered orderable layouts for all cluster settings. All orderable layouts achieve 100% median accuracy. Radial layouts have a greater variance than arc and symmetric arc layouts.</figcaption></figure>

<figure><img src="image_26.png" /><figcaption>Fig. 25: Overall task **completion time** for sizes = all, clusters = all, **order = GEN**, baseline = sfdp. On the right, the dark blue matrix cells correspond to the Bonferroni corrected *p* ≤ 0.05 for all pairwise comparisons. The poorer accuracy of sfdp observed in Figure 24 comes with short completion time, indicating that the participants were discouraged by the relatively higher visual clutter in sfdp plots.</figcaption></figure>

<figure><img src="image_27.png" /><figcaption>Fig. 26: Overall **accuracy** of cluster count judgments for sizes = all, clusters = all, **order = CR**, baseline = sfdp. On the right, the dark blue matrix cells correspond to the Bonferroni corrected *p* ≤ 0.05 for all pairwise comparisons. sfdp is significantly (up to 46%) slower than CR-ordered orderable layouts for all cluster settings. All orderable layouts achieve high median accuracy, between 75% and 100%.</figcaption></figure>
<figure><img src="image_28.png" /><figcaption>Fig. 27: Overall task **completion time** for sizes = all, clusters = all, **order = CR**, baseline = sfdp. On the right, the dark blue matrix cells correspond to the Bonferroni corrected *p* ≤ 0.05 for all pairwise comparisons. The poorer accuracy of sfdp observed in Figure 26 comes with short completion time, indicating that the participants were discouraged by the relatively higher visual clutter in sfdp plots.</figcaption></figure>

<figure><img src="image_29.png" /><figcaption>Fig. 28: Overall **accuracy** of cluster count judgments for sizes = all, clusters = all, **order = OLO**, baseline = sfdp. On the right, the dark blue matrix cells correspond to the Bonferroni corrected *p* ≤ 0.05 for all pairwise comparisons. sfdp is significantly (up to 43%) slower than OLO-ordered orderable layouts for all cluster settings. All orderable layouts achieve high median accuracy, between 71% and 100%.</figcaption></figure>

<figure><img src="image_30.png" /><figcaption>Fig. 29: Overall task **completion time** for sizes = all, clusters = all, **order = OLO**, baseline = sfdp. On the right, the dark blue matrix cells correspond to the Bonferroni corrected *p* ≤ 0.05 for all pairwise comparisons. The poorer accuracy of sfdp observed in Figure 28 comes with short completion time, indicating that the participants were discouraged by the relatively higher visual clutter in sfdp plots.</figcaption></figure>
The Effect of Network Size on Cluster Count in Force-Directed Layouts

<table><caption>Table 1: The difference in median accuracies for cluster count judgements between pairs of network sizes. Bold-faced values are statistically significant. A star * marks the network size with higher accuracy. For Linlog, Backbone and SFDP, the accuracy is always better for the smaller network size.</caption><thead><tr><th>Layout</th><th>Size</th><th>p-value</th><th>Δ Median accuracy</th></tr></thead><tbody><tr><td rowspan="3">Linlog</td><td>50*-100</td><td>&lt; 0.001</td><td><strong>8.33%</strong></td></tr><tr><td>50*-300</td><td>&lt; 0.001</td><td><strong>8.33%</strong></td></tr><tr><td>100*-300</td><td>0.11</td><td>0%</td></tr><tr><td rowspan="3">Backbone</td><td>50*-100</td><td>&lt; 0.001</td><td><strong>5%</strong></td></tr><tr><td>50*-300</td><td>&lt; 0.001</td><td><strong>8.6%</strong></td></tr><tr><td>100*-300</td><td>0.236</td><td>3.6%</td></tr><tr><td rowspan="3">SFDP</td><td>50*-100</td><td>&lt; 0.001</td><td><strong>15%</strong></td></tr><tr><td>50*-300</td><td>&lt; 0.001</td><td><strong>32.1%</strong></td></tr><tr><td>100*-300</td><td>&lt; 0.001</td><td><strong>17.1%</strong></td></tr></tbody></table>

Detailed p-value Tables

<table><caption>Table 2: P-Values for cluster count accuracy for sizes = all, clusters = all, order = GEN, baseline = Linlog (see the corresponding matrix Fig. 8).</caption><thead><tr><th></th><th>Linlog</th><th>Backbone</th><th>SFDP</th></tr></thead><tbody><tr><td>2e-84</td><td></td><td></td><td></td></tr><tr><td>1.4e-79</td><td>0.18</td><td></td><td></td></tr><tr><td>1.8e-51</td><td>5.1e-06</td><td>0.0007</td><td></td></tr><tr><td>1.4e-09</td><td>7.9e-51</td><td>5e-46</td><td>1.4e-24</td></tr><tr><td>8.9e-102</td><td>0.0092</td><td>4.9e-05</td><td>2.4e-12</td><td>2.7e-67</td></tr><tr><td>5.9e-90</td><td>0.13</td><td>0.0033</td><td>4e-09</td><td>2.4e-57</td><td>0.31</td></tr><tr><td>5e-72</td><td>0.087</td><td>0.69</td><td>0.0042</td><td>1.3e-40</td><td>1.8e-05</td><td>0.0014</td></tr><tr><td>1.5e-21</td><td>8.5e-30</td><td>3.5e-25</td><td>5.7e-11</td><td>5.7e-05</td><td>7.9e-44</td><td>2.4e-36</td><td>3.4e-22</td></tr><tr><td>1.6e-113</td><td>4.6e-08</td><td>4.6e-12</td><td>1.6e-21</td><td>2e-80</td><td>0.0022</td><td>7.3e-05</td><td>1.6e-12</td><td>3.5e-57</td></tr><tr><td>1.1e-102</td><td>0.00018</td><td>2.9e-07</td><td>2.2e-15</td><td>5.6e-69</td><td>0.18</td><td>0.022</td><td>7.5e-08</td><td>7.1e-47</td><td>0.11</td></tr><tr><td>3.6e-59</td><td>0.022</td><td>0.3</td><td>0.042</td><td>7e-32</td><td>3.6e-06</td><td>0.00034</td><td>0.52</td><td>3.1e-17</td><td>4.6e-13</td><td>9.6e-09</td></tr><tr><td>1.9e-126</td><td>3.9e-12</td><td>5.1e-17</td><td>8e-28</td><td>3.7e-92</td><td>5e-06</td><td>5.4e-08</td><td>1.3e-17</td><td>2.8e-67</td><td>0.16</td><td>0.0023</td><td>5.9e-18</td></tr><tr><td>1.2e-137</td><td>9.5e-21</td><td>6.9e-27</td><td>9.4e-39</td><td>6.8e-105</td><td>6.6e-13</td><td>1.8e-15</td><td>1.4e-27</td><td>2e-80</td><td>4.8e-05</td><td>2.1e-08</td><td>2.2e-27</td><td>0.0051</td></tr><tr><td>2.5e-128</td><td>1.2e-15</td><td>5e-21</td><td>4.7e-32</td><td>2e-95</td><td>6.6e-09</td><td>3.8e-11</td><td>1e-21</td><td>1e-71</td><td>0.0069</td><td>2.2e-05</td><td>7.5e-22</td><td>0.17</td><td>0.16</td></tr><tr><td>3.5e-85</td><td>0.028</td><td>0.0005</td><td>3.5e-10</td><td>2.5e-54</td><td>0.98</td><td>0.36</td><td>0.00012</td><td>1.1e-35</td><td>0.0039</td><td>0.18</td><td>2.5e-05</td><td>2.1e-05</td><td>1.6e-11</td><td>6.7e-08</td></tr></tbody></table>
<table><caption>Table 13: P-Values for overall completion time for network sizes = all, clusters = all, order = OLO, baseline = backbone (see the corresponding matrix Fig. 23).</caption><thead><tr><th></th><th>0.011</th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th></tr></thead><tbody><tr><td>0.011</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>0.99</td><td>0.0042</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>0.91</td><td>0.006</td><td>0.88</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>0.31</td><td>0.096</td><td>0.29</td><td>0.25</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>1.6e-05</td><td>0.067</td><td>1.9e-06</td><td>5.6e-06</td><td>0.00042</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>0.0048</td><td>0.95</td><td>0.0019</td><td>0.0028</td><td>0.057</td><td>0.064</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>0.14</td><td>0.23</td><td>0.11</td><td>0.1</td><td>0.6</td><td>0.0025</td><td>0.17</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>0.099</td><td>0.27</td><td>0.069</td><td>0.07</td><td>0.49</td><td>0.0027</td><td>0.21</td><td>0.89</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>7e-06</td><td>0.075</td><td>8.5e-07</td><td>3.1e-06</td><td>0.00027</td><td>0.89</td><td>0.065</td><td>0.0019</td><td>0.0021</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>0.034</td><td>0.52</td><td>0.019</td><td>0.02</td><td>0.25</td><td>0.009</td><td>0.44</td><td>0.52</td><td>0.63</td><td>0.0092</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>0.0029</td><td>0.79</td><td>0.0016</td><td>0.0022</td><td>0.04</td><td>0.13</td><td>0.82</td><td>0.12</td><td>0.15</td><td>0.12</td><td>0.36</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>0.037</td><td>0.4</td><td>0.021</td><td>0.023</td><td>0.28</td><td>0.004</td><td>0.35</td><td>0.58</td><td>0.69</td><td>0.0041</td><td>0.87</td><td>0.28</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>1.1e-18</td><td>3.1e-11</td><td>2.1e-22</td><td>9.9e-20</td><td>8.5e-17</td><td>1.1e-06</td><td>5.3e-12</td><td>6.9e-15</td><td>1.8e-15</td><td>1.3e-07</td><td>1.3e-14</td><td>3.3e-10</td><td>2.8e-16</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>2.3e-12</td><td>3.2e-06</td><td>9.5e-15</td><td>3.2e-13</td><td>1.4e-10</td><td>0.0055</td><td>1.6e-06</td><td>5.1e-09</td><td>3.5e-09</td><td>0.0024</td><td>2.2e-08</td><td>1.7e-05</td><td>1.9e-09</td><td>0.024</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>1.7e-10</td><td>5.1e-05</td><td>1.9e-12</td><td>3e-11</td><td>9.5e-09</td><td>0.026</td><td>3.3e-05</td><td>1.9e-07</td><td>1.3e-07</td><td>0.014</td><td>7.1e-07</td><td>0.00023</td><td>1.3e-07</td><td>0.0075</td><td>0.63</td><td></td><td></td><td></td><td></td></tr></tbody></table>

<table><caption>Table 14: P-Values for overall accuracy of cluster count judgments for sizes = all, clusters = all, order = GEN, baseline = sfdp (see the corresponding matrix Fig. 24).</caption><thead><tr><th></th><th>2.5e-127</th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th></tr></thead><tbody><tr><td>1e-123</td><td>0.18</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>1.6e-94</td><td>5.1e-06</td><td>0.0007</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>1.2e-13</td><td>6.3e-90</td><td>6.3e-86</td><td>1.4e-58</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>7.3e-141</td><td>0.0092</td><td>4.9e-05</td><td>2.4e-12</td><td>4.7e-104</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>1.7e-129</td><td>0.13</td><td>0.0033</td><td>4e-09</td><td>1.5e-92</td><td>0.31</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>3.9e-115</td><td>0.087</td><td>0.69</td><td>0.0042</td><td>1.2e-77</td><td>1.8e-05</td><td>0.0014</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>0.22</td><td>1.2e-132</td><td>7.3e-129</td><td>1.7e-99</td><td>1.4e-17</td><td>3.3e-147</td><td>8.5e-136</td><td>1e-120</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>2.8e-150</td><td>4.6e-08</td><td>4.6e-12</td><td>1.6e-21</td><td>2.3e-113</td><td>0.0022</td><td>7.3e-05</td><td>1.6e-12</td><td>1.4e-157</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>2.2e-141</td><td>0.00018</td><td>2.9e-07</td><td>2.2e-15</td><td>2.3e-105</td><td>0.18</td><td>0.022</td><td>7.5e-08</td><td>1.5e-147</td><td>0.11</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>1.6e-100</td><td>0.022</td><td>0.3</td><td>0.042</td><td>7e-64</td><td>3.6e-06</td><td>0.00034</td><td>0.52</td><td>1e-106</td><td>4.6e-13</td><td>9.6e-09</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>1.5e-74</td><td>7.7e-28</td><td>2.8e-23</td><td>3.9e-09</td><td>1.5e-38</td><td>2.3e-42</td><td>7.9e-35</td><td>4.1e-20</td><td>1.9e-78</td><td>1.6e-56</td><td>2.3e-45</td><td>2.5e-15</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>1.7e-168</td><td>9.5e-21</td><td>6.9e-27</td><td>9.4e-39</td><td>5.8e-136</td><td>6.6e-13</td><td>1.8e-15</td><td>1.4e-27</td><td>1.8e-175</td><td>4.8e-05</td><td>2.1e-08</td><td>2.2e-27</td><td>8e-81</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>8.5e-161</td><td>1.2e-15</td><td>5e-21</td><td>4.7e-32</td><td>2.6e-127</td><td>6.6e-09</td><td>3.8e-11</td><td>1e-21</td><td>6e-168</td><td>0.0069</td><td>2.2e-05</td><td>7.5e-22</td><td>1.9e-71</td><td>0.16</td><td></td><td></td><td></td><td></td></tr><tr><td>1.1e-123</td><td>0.028</td><td>0.0005</td><td>3.5e-10</td><td>8.7e-89</td><td>0.98</td><td>0.36</td><td>0.00012</td><td>1.4e-129</td><td>0.0039</td><td>0.18</td><td>2.5e-05</td><td>4.3e-34</td><td>1.6e-11</td><td>6.7e-08</td><td></td><td></td><td></td></tr></tbody></table>
<figure><img src="image_31.png" /><figcaption>Table 15: P-Values for overall completion time for network sizes = all, clusters = all, order = GEN, baseline = sfdp (see the corresponding matrix Fig. 25).</figcaption></figure>

<figure><img src="image_32.png" /><figcaption>Table 16: P-Values for overall accuracy of cluster count judgments for sizes = all, clusters = all, order = CR, baseline = sfdp (see the corresponding matrix Fig. 26).</figcaption></figure>