Information Technology Reference
In-Depth Information
initial embedding,theresulting layouts are different. We choose two layouts of the same
graph: the one with the minimumnumber of crossings and one with approximately twice
as many crossings. These two layouts are referred to as the drawings with the
low
and
high
number of crossings; see Fig. 1. Note that neither MDS-based nor force-directed
algorithms provide any guarantees aboutthenumber of crossings. However, duetothe
many runs for each graph, we expect that the
low
number of crossings is not too far from
optimal.
Tasks.
We choose the tasks for our experiments based on several considerations. First,
the tasks should represent standard problems, commonly encountered when analyz-
ing relational data. Second, the number of edge crossingsinagraph visualization
should likely affect task performance. Finally, the tasks should be present in exist-
inggraph task taxonomies and often utilized in other graph drawinguser evaluations.
With this in mind, we consider the task taxonomy for graph visualization suggested by
Lee et al. [19], which categorizes the tasks into groups: topology-based, attribute-based,
browsing, and overview tasks. Each of the categories specifies different subcategories.
Previousstudies clearly indicate that the number of edges crossings affects tasks in
the topology-based category, while tasks in the other three categories are less likely to
be significantly impacted by the number of crossings or do not fit in our experimen-
tal setup. The graphs in our experiments do not contain special attributes (e.g., color
or shape), and hence the attribute-based tasks are not suitable. The browsing category
deals with navigational tasks that do not require a specific answer, making it difficult
to measure the task performance. Overview tasks are related to compound tasks (e.g.,
identifying changes over time, comparing the relative size of a pair of graphs) are also
not suitable to our setting and less likely to be affected by the number of edge cross-
ings. Therefore, we focus on topology-based tasks, grouped into foursubcategories:
connectivity, accessibility, adjacency, and common connections. For each subcategory,
we choose a task that is frequently used in prior user studies on graph visualization.
Ta s k 1 :
How many edges are inashortest path between two givennodes?
Ta s k 2 :
Whatisthe node with the highest degree?
Ta s k 3 :
What nodes are all adjacenttothe givennode?
Ta s k 4 :
Which of the following nodes are adjacent to bothgivennodes?
The vertices for each question were randomly selected (in the case of Task 1, addi-
tionally ensuring that the pair of vertices is at most 5 edges away).
Participants and Apparatus.
For the first experiment we recruited 6 participants (3
male, 3 female) aged 21-27 years (mean 23) with normal vision. For the second experi-
ment we recruited 16 new participants (12 male, 4 female) aged 21-30 years (mean 25)
with normal vision. All the participants were undergraduate and graduate science and
engineering students familiar with graphs and networks. Both experiments were con-
ducted on a computer with i7 CPU 860 @ 2.80GHz processor and 24 inch screen with
1600x900 resolution. The participants interacted with a standard mouse to complete
the tasks. We used custom-built software to guide the users through the experiment by
providing instructions and collecting data about time and accuracy.
