# Flud: a hybrid crowd–algorithm approach for visualizing biological networks

Aditya Bharadwaj  1234-5678-9012 Virginia TechBlacksburgVirginiaUSA24060
<EMAIL_ADDRESS>,  David Gwizdala  Bridgewater AssociatesStamfordConnecticutUSA
<EMAIL_ADDRESS>,  Yoonjin Kim  Virginia TechBlacksburgVirginiaUSA24060
<EMAIL_ADDRESS>,  Kurt Luther  Virginia TechArlingtonVirginiaUSA22203
<EMAIL_ADDRESS>and  T. M. Murali  Virginia TechBlacksburgVirginiaUSA24060
<EMAIL_ADDRESS>
###### Abstract.

Modern experiments in many disciplines generate large quantities of network
(graph) data. Researchers require aesthetic layouts of these networks that
clearly convey the domain knowledge and meaning. However, the problem remains
challenging due to multiple conflicting aesthetic criteria and complex domain-
specific constraints. In this paper, we present a strategy for generating
visualizations that can help network biologists understand the protein
interactions that underlie processes that take place in the cell.
Specifically, we have developed Flud, an online game with a purpose (GWAP)
that allows humans with no expertise to design biologically meaningful graph
layouts with the help of algorithmically generated suggestions. Further, we
propose a novel hybrid approach for graph layout wherein crowdworkers and a
simulated annealing algorithm build on each other’s progress. To showcase the
effectiveness of Flud, we recruited crowd workers on Amazon Mechanical Turk to
lay out complex networks that represent signaling pathways. Our results show
that the proposed hybrid approach outperforms state-of-the-art techniques for
graphs with a large number of feedback loops. We also found that the
algorithmically generated suggestions guided the players when they are stuck
and helped them improve their score. Finally, we discuss broader implications
for mixed-initiative interactions in human computation games.

crowdsourcing, human computation, graph drawing, computational biology,
protein networks, graphs, citizen science, serious games, games with a
purpose, optimization

††ccs: Human-centered computing Collaborative and social computing systems and
tools††ccs: Human-centered computing Empirical studies in collaborative and
social computing††ccs: Human-centered computing Information
visualization††ccs: Human-centered computing Human computer interaction (HCI)

##  1\. Introduction

Many fields of science require meaningful and visually appealing layouts of
networks (also known as graphs). A prominent example is the discipline of
network biology, where scientists use networks to understand the chemical
reactions and protein interactions that underlie processes that take place in
the cell (Barabasi and Oltvai, 2004). In order to present and analyze these
networks, researchers require aesthetic layouts of these networks that clearly
convey the relevant biological information. A _layout_ of a network assigns
$x$ and $y$ coordinates to each node and routes each edge using a straight
line or a curve in order to create a meaningful visual representation.

There are two major approaches for creating network layouts. The first
approach views humans as the deciding agent and primary creator, with
computers seen as support tools. An example is a graph (or network) drawing
interface in Cytoscape (Smoot et al., 2010) that provides the layout tools for
designers to use while drawing networks. This approach offers creative freedom
and allows the user create meaningful layouts by capturing complex, domain-
specific constraints. However, it is time-consuming to create layouts
manually. The second approach uses fully-automated methods and does not
require human intervention. In contrast to the first approach, it can generate
data visualizations at scale (Tamassia, 2013; Di Battista et al., 1994;
Pavlopoulos et al., 2008; Gibson et al., 2013). However, these methods lack
the ability to capture complex visualization constraints and domain-specific
needs. As a result, it is a common for biologists to depend on the time-
consuming practice of manually improving automatically generated
visualizations.

Crowdsourcing has emerged as a promising solution to scale up such manual
tasks (van Ham and Rogowitz, 2008; Singh et al., 2018; Yuan et al., 2012) by
tapping into the human intelligence and creativity of crowdworkers. However,
it is unclear how to design interfaces and tasks that will allow novice
crowds—who lack expertise in biology and computer science in general—to make
domain-specific modifications to network layouts and balance various
constraints. Our research seeks to bridge this fundamental gap.

In this work, we present Flud, an online game with purpose (GWAP) that allows
humans with no expertise to design biologically meaningful network layouts
with the help of algorithmically-generated suggestions. The goal of the game
is to move nodes in a given network so as to create a layout that optimizes a
score based on pre-specified design criteria. These criteria include four
previously defined aesthetic considerations (Figure 1): 1) minimizing the
number of edge crossings, 2) keeping nodes connected by an edge close to each
other, 3) dispersing disconnected node pairs, and 4) increasing the separation
between nodes and edges. We also introduce a new, fifth criterion inspired by
a biological application to cellular signaling: 5) maximize the number of
downward pointing paths in the layout (Figure 1). These types of paths draw
visual attention to sequences of edges that lead from receptor proteins in the
cell membrane (green triangles, placed at the top of the layout) through
internal nodes to effector molecules in the nucleus (transcription factors,
yellow squares, placed at the bottom of the layout).

Figure 1. Five layout criteria used in Flud. 1) Minimize the number of edge
crossings, 2) Keep nodes connected by an edge close to each other, 3) Disperse
disconnected node pairs, 4) Increase the separation between nodes and edges,
and 5) Increase the number of downward pointing paths.

The role of the game players is to make modifications to the layout so as to
balance the criterion-specific scores based on the direction of flow of
information in the network, edge crossings, and relative distances between
nodes and edges. Since, these criteria may conflict with each other, Flud
allows the players to track the changes in layout score and the corresponding
criterion-specific scores with every move. Another important feature of Flud
is the availability of a “clue” for each criterion. If the player is stuck,
perhaps because the network is complex or it is unclear what the next move
should be, the game highlights a small subset of nodes and edges in the
network as clues. These nodes and edges are selected by Flud such that
changing the positions of these elements is likely to improve the score for
the corresponding criterion. With the help of criterion-specific scores,
clues, and layout tools in Flud interface, we expect that game players will
succeed in generating aesthetic and meaningful layouts.

Flud also facilitates a novel mixed-initiative network layout strategy that
utilizes a sequential and collaborative process wherein human players and a
simulated annealing based layout algorithm (Davidson and Harel, 1996) build on
each other’s progress. The simulated annealing algorithm seeks to iteratively
reach a layout with higher score by randomly searching the neighborhood of an
initial guess. Its strength is that it avoids getting stuck at local optima —
a solution that is better than the others nearby but is not the very best — by
probabilistically accepting an inferior solution. In contrast, human players
use their intelligence and creativity to optimize the score by making
modifications that may be global in nature and challenging to achieve using an
automated method.

To showcase the effectiveness of Flud and the novel mixed-initiative approach,
we recruited nearly 2,000 novice crowd workers on Amazon Mechanical Turk to
lay out and visualize complex protein networks that represent signaling
pathways in human cells. We presented three different versions of the hybrid
crowd–algorithm approach and evaluated them against a crowd-only strategy and
algorithmic baselines. Our results show that such a collaboration between
humans and algorithms leads to higher scoring layouts than either from humans
or from algorithms alone. We found that the game elements such as criterion-
specific modes and clues supported crowd workers in the visualization tasks.
The results also show that the crowd workers who moved one of the nodes
suggested by Flud contributed more to the overall layout score in comparison
to rest of the nodes in the network.

In summary, our contributions include:

  * •

A novel mixed-initiative approach that combines crowdsourcing with
computational engines to create high-quality visualizations of biological
networks.

  * •

A game with a purpose, Flud, that facilitates this approach with two
components: a) an interface that gamifies the network visualization task to
make it more accessible to crowd workers with no biological or computer
science expertise, and b) an implementation that allows crowd workers and
algorithms to build on each others progress.

  * •

Experiments that provide empirical evidence of the benefits of mixed-
initiative layout methods compared to algorithmic baselines.

##  2\. Related Work

###  2.1. Algorithms for network layout

Several algorithms exist to automatically compute network layouts. Popular
methods include circular (Baur and Brandes, 2004; Gansner and Koren, 2006),
hierarchical (Eades et al., 1996; Sugiyama et al., 1981; Gansner et al.,
1993), orthogonal (Eiglsperger et al., 2000), force directed (Fruchterman and
Reingold, 1991; Kamada et al., 1989), and spectra (Koren, 2003, 2005) layouts.
Several of these methods can generate layouts in a few seconds for moderately-
sized networks. Implementations are available in various tools or libraries,
e.g., Cytoscape (Shannon et al., 2003), Gephi (Jacomy et al., 2014), Graphviz
(Ellson et al., 2001), NetworkX (Hagberg et al., 2008), NetBioV (Tripathi et
al., 2014), and Pajek (Batagelj and Mrvar, 2001).

Despite their wide availability, these methods have several drawbacks. They
may produce very specific types of layouts, e.g., arrange nodes in circles
(Baur and Brandes, 2004; Gansner and Koren, 2006), or be appropriate for
restricted classes of networks, e.g., directed acyclic networks (Eades et al.,
1996; Sugiyama et al., 1981). They may compute layouts that try to optimize
specific aesthetic criteria, e.g., prevent edges from being stretched and
disconnected nodes from coming too close (Fruchterman and Reingold, 1991;
Kamada et al., 1989) or hierarchically arrange nodes and remove edge crossings
(Sugiyama et al., 1981; Gansner et al., 1993). One such popular method is Dig-
Cola (Dwyer and Koren, 2005), which arranges the nodes in layers while
preserving edge length and symmetries. Since highlighting information flow is
an important criterion for experiments in this paper, we use Dig-Cola as a
baseline to compare performance against Flud. In general, these methods do not
have the flexibility to accommodate a diverse variety of layout criteria and
domain-specific constraints.

As discussed earlier, a general purpose approach to accommodate multiple
layout criteria is to formulate network layout as an optimization problem and
solve it using simulated annealing (Davidson and Harel, 1996). Taking
inspiration from these ideas, we propose to examine how a mixed-initiative
approach that combines human intelligence with simulated annealing can yield
better layouts than either of these methods alone.

###  2.2. Leveraging human abilities through crowdsourcing to lay out networks

Some research has examined how users lay out networks, including in comparison
to automated layouts. Two studies (Dwyer et al., 2009; van Ham and Rogowitz,
2008) asked participants to draw an aesthetic layout of a given network. Dwyer
et al. (Dwyer et al., 2009) concluded that the best user-generated layouts
performed as well as or better than automated layouts based on physical
models. Although these studies do not use crowd workers, they provide evidence
that non-expert humans can create network layouts comparable to algorithms.

Researchers have explored using non-expert volunteers (e.g., citizen
scientists) to perform other visualization tasks. For example, systems such as
ManyEyes (Viégas et al., 2007) and Sense.us (Heer et al., 2007) have used
novice crowds to create, collaborate on, and analyze data visualizations.
Connect the Dots (Li et al., 2018) and CRICTO (Chung et al., 2017) ask novice
crowds to build social networks for intelligence analysis, but not to create
layouts for them. Inspired by these projects, we explore the use of non-expert
workers on Amazon Mechanical Turk to create biological network layouts.

Most related to this paper, our prior work on CrowdLayout leverages crowd
workers to design layouts of biological networks that satisfy domain-inspired
guidelines specified in natural language (Singh et al., 2018). CrowdLayout
also uses crowd workers to evaluate how well these layouts satisfy the
guidelines. Our work in CrowdLayout shows that translating domain knowledge
into representational guidelines can allow non-expert crowds to create
effective layouts.

Our work differs from and complements these efforts in several important ways.
First, we focus on combining multiple aesthetic criteria with a specific
domain knowledge guideline, all of which can be translated into mathematical
formulae. Second, we score layouts to provide real-time feedback to the user
who is modifying the layout rather than (as in the case of CrowdLayout) wait
for other crowd workers to evaluate the layout. Third, we formulate layout
creation as a collaboration among multiple crowd workers or between crowd
workers and computational engines, in contrast to single-user design tasks.

###  2.3. Designing network layouts by combining algorithms with crowdsourcing

Prior work has explored using mixed-initiative systems to perform a variety of
tasks like data wrangling (Kandel et al., 2011), exploratory analysis
(Wongsuphasawat et al., 2016), and natural language translation (Green et al.,
2014). In a recent work, Heer (Heer, 2019) discussed how these systems use
shared representations like text-editing interfaces and domain-specific
languages through which humans and algorithms can work together to accomplish
a goal. In contrast to these systems, the shared representation in Flud
involves three components: (i) a network layout interface, (ii) 2D coordinates
on the screen as potential actions, and (iii) a scoring scheme as a shared
objective. More importantly, we use these shared representations to support
mixed-initiative interaction in a novel network layout task.

Some mixed-initiative systems also leverage the complementary strengths of
human intelligence and automated techniques to help users understand network
data. These include a visualization tool that allows users to analyze legal
citation networks with degree of interest functions (van Ham and Perer, 2009),
and a system that helps users explore clusters of similar research papers via
machine learning and visualization (Chau et al., 2011). These systems can be
highly effective for individual expert users, but this paper considers how
non-expert crowds can work with algorithms to pre-process network layouts for
expert users.

Researchers have also begun exploring mixed-initiative systems that use
crowdsourcing. For example, Flock (Cheng and Bernstein, 2015) helps build
accurate classifiers by supporting a mixed-initiative interaction where crowd
nominates features and machine learning weighs them. Jellybean (Sarma et al.,
2015) was able to accurately count objects in images by combining results from
crowds and computer vision algorithms. Ideahound (Siangliulue et al., 2016)
combines human judgment with machine learning techniques to create a
computational semantic model of the emerging solution space. Mobi (Zhang et
al., 2012) demonstrated how a mixed-initiative crowdsourcing system could
support trip planning by allowing a traveler to specify both quantitative
global constraints (e.g., allotted time, number of activities) enforced by the
software, and qualitative constraints (e.g., visiting the beach vs. the
downtown) satisfied by crowd workers. Subsequent research explored these ideas
for other tasks and domains, such as conference planning (Kim et al., 2013).
Moreover, while Mobi guided worker effort through todo items, systems like
Flock, Jellybean, and Ideahound used simple instructions to guide them. In
contrast, we consider how gameplay mechanisms can motivate desired behavior in
crowd workers. Also, Flud differs in that we adapt these ideas for a novel
task type (i.e., network layout) and task domain (i.e., biology).

Yuan et al. (Yuan et al., 2012) proposed a strategy that utilized crowd
workers to lay out subnetworks of a complex network. Subsequently, the authors
used a constrained distance-embedding algorithm to compose the layouts of the
subnetworks into one for the entire network. In contrast, our work seeks to
facilitate the design process for crowd workers in order to improve the
overall quality of layouts they generate.

###  2.4. Designing a game with a purpose to lay out networks

The idea of using games to solve real-world scientific problems is not new
(Schrier, 2018; Cooper, 2014; Ferrara, 2013) and has been used to solve a wide
range of complex problems, such as protein folding (Cooper et al., 2010), RNA
sequence design (Lee et al., 2014), DNA sequence alignment (Kawrykow et al.,
2012), molecular design (Anderson-Lee et al., 2016), and neuron reconstruction
(Kim et al., 2014a). Inspired by the success of these games, we developed
Flud, a game with a purpose that leverages the creativity and cognitive
abilities of the players to create biological network visualizations, a
challenge that has not previously been tackled using games. We also explore a
game mechanic that differs from most prior citizen science games. While the
players in most of these games compete against each other, Flud players
sequentially collaborate on a layout by building on each others’ progress.

Some computer games have been developed for network drawing purposes (Duncan
et al., 2012), including the popular one-player game Planarity (Eppstein,
2014). Planarity (also known as UntangleManiak or The Plateau) asks the player
to move nodes in order to untangle (remove) the edge crossings in the given
network. CycleXing (Bauer et al., 2012) is a two-player game with an
adversarial game mechanic where one player tries to maximize the number of
crossings, and the other tries to minimize them. Similar to Planarity and
CycleXing, Flud asks the players to move the nodes around to manipulate
layouts. In contrast, Hashi (Hashi Puzzle Bridges Game, [n. d.]) is a single-
player network drawing based game where the players draw an edge between
nodes. The goal of a Hashi game is to create a single connected component
while following specific rules like the edges cannot cross and should be
orthogonal. While minimizing the number of edge crossings is one of our
criteria, Flud players need to consider four other layout criteria as well.
More importantly, none of these games asks the players to optimize the number
of downward pointing paths.

In a recent study, Hamari et al. found that leaderboards are the most commonly
studied gamification technique for motivating the players (Hamari et al.,
2014). They are generally used to help players judge their success by
comparing their performance in against other players (e.g., Foldit (Cooper et
al., 2010), Peekaboom (von Ahn et al., 2006)) and even themselves (e.g.,
Planarity (Eppstein, 2014)). In contrast to these games, since Flud players
sequentially collaborate by building on the previous best layout, we only show
them the best score so far instead of showing a leaderboard. However, it might
be interesting to explore the use of leaderboard to motivate the players to
play multiple games by aggregating the points.

The scoring system is another essential gaming element and is used to reward
players for their performance. The scoring system generally depends on more
than one component. While games like Phylo (Kawrykow et al., 2012) provide
detailed scoring information by showcasing values for all of the components
that make up the overall score, games like Foldit (Cooper et al., 2010) and
EyeWire (Kim et al., 2014b) only show the overall score. In Flud, our players
need to consider multiple layout criteria while playing the game, and
therefore, we show all of the component scores along with the overall scores.
Our scoring information differs from these systems in two important ways.
First, to help players understand the scoring method, we transparently show
the weights of all the component scores. Second, we use visual cues like
up/down arrows and green/red colors to allow players to track progress after
each move.

Game modes is another gaming element used in Flud. They are commonly used in
games to offer players different gameplay settings, difficulty levels, tools,
rules, and even graphics. A typical example of the game mode is the choice
between single-player versus multi-player setting. Expectedly, game modes are
common in serious games as well. For example, Phylo has three different games
modes (Story, Ribo, Phylo) with different gameplay settings including one for
RNA molecules. Foldit has fives game modes: Modeless, Pull, Structure, Note,
Design. Each of these modes enable the players with unique abilities, which
are otherwise not available in other modes. In Flud, we adapt these ideas and
use five modes where we enable players with a game visualization and clues
unique to a given mode. However, our use of modes differs from other serious
games in that we allocate a mode to players instead of giving them an option
to choose it. Moreover, in this paper, we empirically study the best strategy
to assign modes to Flud players.

##  3\. Description of the Flud System

Flud is a web-based game with a purpose that allows a _requester_ — a
biologist seeking to visualize his or her network data — to crowdsource the
layout design task for biological network visualizations to novice game
_players_. Flud, as a system, has two main components: the requester interface
and the game interface. We now describe how Flud assists novice _players_ in
visualizing and laying out a network in the context of layout criteria
specified by a _requester_.

###  3.1. Flud requester interface

This interface allows a requester to send a network to Flud and crowdsource
the layout design task. The requester can use the interface to control
parameters such as the number of players per game, layout criteria, and the
number of minutes a player can play the game. We detail some of the most
important parameters below.

####  3.1.1. Flud layout criteria

A requester can ask Flud players to optimize the network layout for five types
of criteria (see Figure 1). The first criterion is domain-inspired, while the
other four are aesthetic and have been previously used as design guidelines in
network drawing (also called graph drawing).

  1. (1)

_Downward pointing paths_ : This guideline asks players to maximize the number
of downward pointing paths. This domain-specific constraint is especially
useful for analyzing the flow of information in biological networks that
represent cellular signaling.

  2. (2)

_Non-crossing edge pairs_ (Purchase et al., 2001; Taylor and Rodgers, 2005;
Tamassia et al., 1988): The goal of this guideline is to maximize the number
of edge pairs that do not intersect, i.e., minimize the number of edge
crossings.

  3. (3)

_Edge length_ (Taylor and Rodgers, 2005; Tamassia et al., 1988): This
guideline asks players to minimize the length of the edges in the network.

  4. (4)

_Node distribution_ (Bennett et al., 2007; Davidson and Harel, 1996; Taylor
and Rodgers, 2005; Tamassia et al., 1988): In this guideline, unconnected
nodes should be far apart from each other.

  5. (5)

_Node edge separation_ (Davidson and Harel, 1996): This guideline seeks to
create layouts where nodes are positioned away from edges.

Requesters may also assign priorities or weights to each layout criterion to
convey their relative importance to Flud players. These priorities help
players to prioritize layout criteria in case of conflicts. A requester can
also exclude a layout criterion by assigning it a priority of zero.

####  3.1.2. Crowdsourcing approach

One of the challenges in creating network layouts is that different criteria
may conflict with each other. Heuristics used by automated methods may compute
non-optimal solutions or get stuck in local optima. For instance, the correct
orientation of several edges in a path may be required to make it point
downwards. Therefore, it is common practice for experts (biologists in our
case) to manually improve automatically generated visualizations. In Flud, we
use crowdsourcing to leverage the visual and cognitive abilities of humans to
observe patterns and identify solutions that escape local optima. Flud allows
requesters to specify the total number of game players for a layout design
task. They can also select one of two available crowdsourcing approaches:

  1. (1)

_Crowd_ : In this approach, Flud asks a fixed number of players (specified by
the requester) to play the game in a sequence. In each game session, a player
starts with the highest-scoring layout created so far, i.e., across all
earlier sessions. During a game session, a player may create multiple layouts.
Flud stores the highest-scoring layout of these. If this layout scores better
than the current leader, Flud updates the best overall layout. In this
fashion, players can iteratively improve upon one another’s results.

  2. (2)

_Hybrid_ : Here, Flud alternates sessions of gameplay between players and
simulated annealing (Davidson and Harel, 1996). In each session, either a
player or simulated annealing starts with the highest-scoring layout created
so far, with the this layout updated as in the crowd-only approach. In this
fashion, human players and the algorithm can iteratively improve upon one
another’s results. Flud allows requesters to specify the initial temperature
(default = 100) and number of iterations (default = 500) in a given simulated
annealing session.

###  3.2. Flud game interface

The game interface has three major parts: a visualization of the network being
laid out on the left, text panels with game-related tips in the middle, and a
sidebar with game controls and score information on the right (Figure 2).

Figure 2. Screenshot of Flud’s game interface in the “Downward Pointing Paths”
mode. The interface has three major parts: a visualization of the network
being laid out (left), text panels with game-related tips (middle), and a
sidebar with game controls and score information (right). The upward pointing
edges are shown in red to draw the player’s attention. The path highlighted in
saturated colors is an automatically generated hint. Reorienting the red edge
to make it point downward will increase the number of downward pointing paths.

####  3.2.1. Network visualization

Flud provides an interactive network visualization that supports both touch
and mouse gestures to select and drag one or more nodes. Since Flud players do
not need biological expertise, they do not see any node or any edge labels
describing their biological meaning. Instead, each node displays the number of
edges incident on it as a signal of that node’s importance.

####  3.2.2. Scores

The top portion of the sidebar displays the highest score achieved by a layout
for the network, the score of the current layout, and a criterion-specific
score board. The score board displays the scores and priorities (in coin-
shaped badges) for each individual criterion. In the score board, we sort the
criteria in decreasing order of the priorities assigned by the requester. We
scale the per-criterion scores between 0 and 10,000 to avoid displaying
floating point values. After the player makes a move, Flud recalculates and
displays, in real time, each per-criterion score as well as the total score. A
green up arrow ($\uparrow$) or a red down arrow ($\downarrow$) next to each
per-criterion score allows players to track the impact of their last move on
the score. In addition, we display the change in the overall score with a
similar color scheme.

####  3.2.3. Criterion-specific modes and clues

Csikszentmihalyi (Csikszentmihalyi, 1990) argues that a user can achieve flow,
a state of being “in the zone,” if they attain multiple component states.
These states include challenge-skill level balance, immediate and unambiguous
feedback from the system, concentration on the task at hand, and clarity of
goals. Inspired by flow theory, which has been influential in game design
(Cowley et al., 2008), we implemented two important gameplay features —
criterion-specific modes and clues (Figures 5 and 6) — to help players focus
on their goals and make progress without becoming bored or frustrated. At the
start of a game session, the player is assigned a single criterion-specific
mode. In this mode, to delineate the task, the visual representation of the
network highlights (in red) the elements that are relevant to the criterion-
specific task. Flud has five such modes: Downward pointing paths, Non-crossing
edge pairs, Edge length, Node distribution, and Node edge separation.

Moreover, if the player is stuck while playing, Flud reduces the challenge
level by presenting them with an algorithmically-generated, mode-specific
“clue” that highlights a small subset of nodes and edges in the network and
further narrows the focus of a player to a very specific task (Von Ahn and
Dabbish, 2008). Flud selects specific elements in the clue such that changing
their positions is likely to improve the score for the corresponding
criterion. We now describe each criterion-specific mode and the corresponding
clue.

##### (i) Downward pointing paths:

We say that an individual directed edge is _downward pointing_ if the
$y$-coordinate of its head is below the $y$-coordinate of the tail and angle
between the edge and the $x$-axis is greater than equal to a fixed degree (15
degrees, in our implementation; Figure 3). A path is _downward pointing_ if
all the edges in it have this property (Figure 4).

Figure 3. Illustration of downward and upward pointing edges. A directed edge
is _downward pointing_ if the $y$-coordinate of its head is below the
$y$-coordinate of the tail and angle between the edge and the $x$-axis is
greater than equal to 15 degrees. The blue and red regions show the angles at
which a directed edge will be considered as downward pointing and upward
pointing, respectively.  Figure 4. Downward-pointing paths. (a) Three paths.
(b) Moving the node with a green border increases the number of paths to four.
(c) Another move increases the number to six.

In the downward pointing paths mode, Flud highlights every upward pointing
edge in red (Figure 5(a)). A player can reorient such an edge in an attempt to
increase the number of downward pointing paths. A clue in this mode (Figure
5(b)) highlights a path in the network that (a) contains at least one upward
pointing edge, and (b) has the property that reorienting all upward-pointing
edges in the path is guaranteed to increase the number of downward pointing
paths. If there is no such path, the player does not see any clue.

(a) Mode for downward pointing paths.

(b) Clue for downward pointing paths.

(c) Mode for edge crossings.

(d) Clue for edge crossings.

Figure 5. Screenshots of the network visualization and the clue in the
“Downward pointing paths” and “Non-crossing edge pairs” modes.

##### (ii) Non-crossing edge pairs:

This mode displays every edge crossing as a red point (Figure 5(c)). When a
player hovers on an edge crossing, the mode highlights the intersecting edges.
Decreasing the number of edge crossings is perhaps one of the most challenging
layout criteria since the player has to manipulate nodes without introducing
new intersections. Intuitively, the higher the degree of a node, the harder it
may be to remove intersections involving edges incident on that node.
Therefore, the clue in this mode highlights a pair of crossing edges such that
the total degree of the four nodes involved is the smallest over all the
intersections in the layout (Figure 5(d)). Note that we cannot guarantee that
the player will indeed be able to decrease the number of crossings by moving
one or more of these nodes.

##### (iii) Edge length:

For this criterion, players need to consider the length of all the edges in
the network. Therefore, the mode presents all the nodes and edges in blue. The
clue highlights an edge that is either very long or very short (Figure 6(a)).
Correcting the length of this edge should lead to the improvement of the edge
length score.

(a) Clue for edge length.

(b) Clue for node distribution.

(c) Clue for node edge separation.

Figure 6. Screenshots of the network visualization in Edge length, Node
distribution, and Node edge separation mode.

##### (iv) Node distribution:

In this mode, the clue highlights the unconnected pair of nodes that are the
closest to each other (Figure 6(b)). Thus, the clue provides a greedy way for
players to consider node pairs that need to be moved further apart.

##### (v) Node edge separation:

Here, the clue highlights the node-edge pair that is the closest to each other
(Figure 6(c)).

####  3.2.4. Layout controls

The bottom part of the sidebar contains multiple controls that allow players
to rapidly perform non-trivial changes to the layout. These changes include
expanding and squeezing the spacing between selected nodes, undoing and
redoing earlier actions, and reverting to the layout with the best score.

####  3.2.5. Game tips

The middle part of the interface contains text panels with game related tips.
These tips include an example of a good layout for a toy network, a link to
the tutorial on how to use criterion-specific clues, and specific instructions
on how to improve the per-criterion score for the assigned mode.

####  3.2.6. Bounding box

To prevent players from creating pathological layouts that move nodes
indiscriminately far apart from each other, we set the scores for each
criterion to zero if any node is moved outside a bounding box of fixed size.

###  3.3. Flud scoring system

In describing the scoring system, we use $G=(V,E)$ to denote the network $G$
being laid out with $V$ denoting its nodes and $E$ denoting its edges. We use
$n$ to denote the number of nodes and $m$ for the number of edges in $G$.
Given the $x$\- and $y$-coordinates for every node in $V$, we use $d(u,v)$ to
denote the Euclidean distance between nodes $u$ and $v$ and $l(e)$ to denote
the length of an edge $e$ (the Euclidean distance between its endpoints). We
use $w$ and $h$ to represent the fixed width and height of the bounding box.
We now describe how we computed the score corresponding to each criterion
(per-criterion score).

  1. (1)

_Downward pointing paths_ : We compute a normalized _downward pointing_ score
as follows:

$\mathit{DP}(G)=\frac{\pi(G)}{\rho(G)}.$

where $\pi(v)$ is the number of downward-pointing paths and $\rho(v)$ is the
approximated upper bound of the number of downward-pointing paths. The closer
$DP(G)$ is to one, the larger the number of downward-pointing paths in the
layout.

  2. (2)

_Non-crossing edge pairs_ : Since the maximum number of non-crossing edge
pairs possible in $G$ is $m(m-1)/2$, we compute the _non-crossing edge pairs
score_ as

$\mathit{EC}(G)=\frac{2\chi(G)}{m(m-1)}.$

The closer $EC(G)$ is to one, the smaller is the number of edge crossings in
the layout. We have intentionally defined $\mathit{EC}(G)$ as above so that
high values reflect good performance and players focus on increasing their
scores.

  3. (3)

_Edge length_ : We define the cost $c(e)$ of an edge to be equal to its length
$l(e)$ if $l(e)\geq$ size of a node or equal to a large penalty, otherwise. We
normalize the cost of each edge by the largest possible edge length and
therefore, penalty should be greater the diagonal of the screen. We compute
the _edge length score_ of a layout as

$\mathit{EL}(G)=\max\Big{\\{}0,1-\frac{1}{m}\sum_{e\in
E}\frac{c(e)}{\sqrt{w^{2}+h^{2}}}\Big{\\}}$

Thus, the closer $EL(G)$ is to one, the closer the nodes connected by an edge
are, on average.

  4. (4)

_Node distribution_ : Here, we want to maximize the average distance in the
layout between a node and its closest unconnected node. Unlike the previous
criterion, it applies only to pairs of nodes not connected by an edge. We
compute the _node distribution score_ as

$\mathit{ND}(G)=\frac{1}{n}{\sum}\limits_{u\in
V}\frac{\min\limits_{\begin{subarray}{c}v\in V,(u,v)\notin
E\end{subarray}}d(u,v)}{\sqrt{w^{2}+h^{2}}},$

  5. (5)

_Node edge separation_ : In this criterion, we want to maximize the average
distance between a node and the closest edge to it in the layout. Therefore,
we define the _node edge separation score_ as

$\mathit{NED}(G)=\frac{1}{n}{\sum}\limits_{u\in
V}\frac{\min\limits_{\begin{subarray}{c}e=\\{t,v\\}\in E\\\ u\neq t\neq
v\end{subarray}}d(u,e)}{\sqrt{w^{2}+h^{2}}}$

where $d(v,e)$ denotes the distance between node $v$ and edge $e$.

We define the overall score $\mathit{OS}(G)$ for a layout as a weighted sum of
the five per criterion scores

$\mathit{OS}(G)=w_{\mathit{DP}}\times\mathit{DP}(G)+w_{\mathit{EC}}\times\mathit{EC}(G)+w_{\mathit{EL}}\times\mathit{EL}(G)+w_{\mathit{ND}}\times\mathit{ND}(G)+w_{\mathit{NED}}\times\mathit{NED}(G),$

where the coefficients are the priorities assigned to each criterion by the
requester. We describe the algorithm and parameters used to compute the per
criterion scores in Appendix.

###  3.4. Simulated Annealing

We use simulated annealing (Davidson and Harel, 1996) as the primary baseline
for comparison and as the algorithm in the hybrid approach. We selected this
method primarily due to its flexibility to accommodate all of our criteria
(Section 3.1.1). We run the algorithm for a fixed number of iterations (e.g.,
500) with the temperature decreasing by a factor of 0.995 after every
iteration. Each iteration involves $10n$ steps, where $n$ is the number of
nodes in the network. In every step, we move a node to a random position
$(x_{\mathit{new}},y_{\mathit{new}})$ computed as follows from the current
position $(x_{\mathit{current}},y_{\mathit{current}})$:

$x_{new}=x_{current}+\rho_{x}\frac{1}{4}\bigg{(}\frac{T}{T_{\mathit{max}}}\bigg{)}^{2}w$
$y_{new}=y_{current}+\rho_{y}\frac{1}{4}\bigg{(}\frac{T}{T_{\mathit{max}}}\bigg{)}^{2}h$

where $T_{\mathit{max}}=100$ and $T$ represent the maximum and current
temperatures, respectively, and we draw $\rho_{x}$ and $\rho_{y}$ uniformly at
random from the interval $[0,1]$. Thus, we select the new position uniformly
at random from a rectangle centered at the current location of the node. The
size of this rectangle is proportional to the fixed page size and decreases
quadratically with the temperature. We compute the score of the layout with
this new position. We accept the move if it improves the score. Otherwise, we
accept this move, even though it worsens the score, with a probability
$\Pr(\Delta s)=e^{-\frac{\Delta s}{T}}$, where $\Delta s$ is the change in
score. Therefore, as the temperature decreases, so does the probability of
accepting a move that worsens the score. Once the algorithm stops, we use the
best layout in the entire run as the final layout. Overall, the annealing
schedule took approximately 1 hour to cool down from high initial temperature
($T=T_{0}=100$) to low temperature ($T\approx 1$).

###  3.5. Implementation details

We implemented Flud in Python using the Django web framework, with network
visualization supported by Cytoscape.js (Franz et al., 2016). Flud interfaces
with GraphSpace (Bharadwaj et al., 2017) for storing and sharing networks and
their layouts. To create a game of Flud, a requester interface shares the
networks posted by the requester to a public group called ‘Flud’ on
GraphSpace. The Flud system pings GraphSpace for new networks in ‘Flud’ group
and makes it available on the Flud website for a player to lay out. When a
player selects a graph, Flud presents the highest-scoring layout so far for
that graph. During a game session, a player may create multiple layouts to
maximize their score, and Flud stores the highest-scoring layout. If this
layout scores better than the current leader, Flud updates GraphSpace with
this layout. In this fashion, players can iteratively improve upon one
another’s results. Finally, the requesters can access all of the crowd-
generated layouts, including the best overall layout on GraphSpace.

##  4\. Evaluation

Having implemented the Flud system as described above, we aimed to showcase
its effectiveness to crowdsource the layout design task for biological network
visualizations. To this end, we posed the following research questions:

  * _RQ1:_

_How should Flud assign criterion-specific modes to players to optimize the
scores they achieve?_

  * _RQ2:_

_How do the crowd and hybrid approaches perform in comparison to automated
methods?_

  * _RQ3:_

_What are the dynamics of the mixed-initiative collaboration in the hybrid
approach?_

In the rest of this section, we describe how we selected crowd workers, the
networks we laid out, the task each worker had to perform, and how we
compensated them before presenting our experiment design.

###  4.1. Networks

We selected three different complex protein networks of similar size (Table 1)
that represent signaling pathways in cells. These networks contained both
directed and undirected edges. These networks contained a small (G1), medium
(G2), and high (G3) number of cycles. The presence of a large number of cycles
makes it difficult to create layouts with many downward-pointing paths. Hence,
these networks should present different levels of challenges to crowd workers
and to automated algorithms.

Network | Description | #Nodes | #Edges | #Simple Cycles |  | #Simple Paths from
---
sources to targets
G1 |  | Crosstalk from Estrogen signaling
---
pathway to HIF-1 signaling pathway
71 | 112 | 3 | 1952
G2 |  | Network representing Epithelial-
---
to-mesenchymal transition (EMT)
69 | 131 | 8463 | 10066
G3 |  | Signaling from SCH9 to TPK2
---
in budding yeast
58 | 136 | 269437 | 2361

Table 1. Networks used for evaluation.

###  4.2. Crowd workers

To showcase that Flud can support broad player bases, we did not require the
participants to have network or biology expertise. Therefore, we recruited
novice crowd workers from the Amazon Mechanical Turk (MTurk) platform as our
game players. We used MTurk’s built-in qualification types to only recruit
workers from the US with a Human Intelligence Task (HIT) approval rate of at
least 97% and at least 100 completed HITs.

In a pilot study where we asked crowd workers to play the game, we noticed
that some players (a) did not carefully go through the tutorial and (b) moved
the nodes aimlessly to use up the fixed number of moves required to be paid
for completing the game. In order to prevent such unproductive crowd activity,
we only invite crowd workers to play the real game who correctly solved two
small puzzles towards the end of the tutorial. The first puzzle asks the crowd
worker to increase one of the per-criterion scores in a toy network by at
least one point with the help of a clue. The second puzzle again asks the
worker to increase the per criterion score for the same network except that
there is no clue available. To avoid learning effects, we recruited the crowd
workers such that no individual repeated the same network or criterion-
specific task.

###  4.3. Crowd worker task

We start the task for a crowd worker by randomly selecting a game
corresponding to one of the three networks. Next, we assign them one of the
layout criteria (using one of the strategies described in Section 4.5.1) to
restrict their gameplay to a criterion-specific mode. We ask the crowd worker
to go through a two-part interactive tutorial that introduces the visual
elements, game rules, and use of the criterion specific clues. In the first
part of the tutorial, we train the worker to improve the criterion-specific
subscore both with and without the help of a clue. At the end of part one of
the tutorial, we give the worker an option to submit the HIT or to continue
with part two of the tutorial and play the game to earn a bonus (Refer to
Section 4.4). The second part of the tutorial introduces the worker to the
remaining the subscores and the complete rules of the game. During the game
session, each worker had one hour to generate an improved layout. A player can
quit the game at any point. Irrespective of the assigned mode, the crowd
worker’s goal is to create a layout that optimizes the total score based on
the layout criteria (see Section 3.1.1).

###  4.4. Compensation

For the first half of the tutorial, we compensate the workers with at least
the minimum hourly wage rate ($7.25 per hour) in our region. If a worker
elects to continue playing Flud in order to obtain bonus compensation, we pay
this amount according to how they increase the score of the layout. We use
this strategy to motivate a worker to fully utilize the time available to
them.

We assign budgets to each criterion in proportion to its priorities. These
budgets determine the amount of bonus a player can earn while playing the game
for the assigned criterion-specific mode. The bonus amount earned when a
player improves the score from $s_{i}$ to $s_{j}$ is

$(b+1)^{\frac{\min\\{s_{\mathit{j}},s_{\mathit{target}}\\}}{s_{\mathit{target}}}}-(b+1)^{\frac{\min\\{s_{\mathit{i}},s_{\mathit{target}}\\}}{s_{\mathit{target}}}},$

where $s_{j}>s_{i}$, $b$ is the budget assigned to the given criterion and
$s_{\mathit{target}}$ is the target score we want the players to achieve. The
exponential nature of the bonus computation ensures that the workers earn more
money per point as they approach the target score. The goal is to motivate the
workers to continue playing the game, even though the task of improving the
score gets harder as the player gets closer to the target score. Ideally, we
should aim to set $s_{\mathit{target}}$ to an achievable value in order to
ensure that the bonus is fair. For example, it is not possible for a player to
achieve a score 10,000 (maximum possible score) if the network has many
cycles. Therefore, we suggest using an achievable target (say, 2,000). Once
the workers achieve the target score, the requester has the option to increase
the budget and the desired score.

###  4.5. Experiment design

Figure 7. Figure illustrating the _Crowd_ , _Crowd-Random_ , and _Hybrid_
(Crowd-SA) approaches evaluated in this paper. Each circle represents a crowd
worker in a game sequence where a crowd worker is assigned a criterion-
specific mode $M$. Each criterion-specific mode is assigned N times in a game
sequence. A rectangle represent a simulated annealing schedule with initial
temperature $t$.

Given the central importance of domain-specific downward pointing path
criterion, we assigned it a high priority of 400. We assigned the non-crossing
edge-pairs criterion a priority of 3 and rest of the criteria a priority of 1.
We conducted two experiments to address our research questions.

####  4.5.1. Experiment 1

We designed the first experiment to answer _RQ1_ , where we want to find a
good strategy to assign a criterion-specific mode to a game player in a
sequence. To this end, we evaluated the performance of two different
approaches: _Crowd_ and _Crowd-Random_. In the _Crowd_ approach, we assigned
criterion-specific modes to workers in the order of their priorities, i.e.,
downward pointing paths (DP), non-crossing edge pairs (EC), edge length (EL),
node distribution (ND), and node-edge separation (NED), as shown in Figure 7.

We recruited $20$ crowd workers for each game sequence where four ($N=4$)
workers focused on each of the five layout criteria used in Flud. In contrast,
for the _Crowd-Random_ approach, we randomly assigned each criterion four
($N=4$) times in a sequence of $20$ crowd workers (refer to Figure 7). We
recruited crowd workers for three game sequences per network for each
approach. Overall, we recruited $360$ crowd workers for this experiment.

####  4.5.2. Experiment 2

In our second experiment, we evaluated the performance of the _Crowd_ approach
described in Experiment 1 and the _Hybrid_ approach against automated baseline
methods with the goal of answering RQ2 and RQ3. Similar to the _Crowd_
approach, for _Hybrid_ approach, we recruited $5N$ crowd workers for each game
sequence where $N$ workers focused on each of the five criteria; we provide
the values of $N$ below. However, in _Hybrid_ , we alternate sessions of
gameplay between crowd worker and simulated annealing (refer to Figure 7).
Davidson and Harel’s simulated annealing based layout algorithm (Davidson and
Harel, 1996) starts with “non-local” moves ($T=100$), where a node’s next
location is not restricted to nearby positions, and ends with “local” moves
($T\approx 1$) where a node can move only to a nearby position. In this
experiment, we tried three different types of hybrid approaches (_Crowd-SA100_
, _Crowd-SA50_ , and _Crowd-SA20_), where we alternate the _Crowd_ approach
and simulated annealing schedules with three different initial temperatures
(refer to Figure 8).

  * •

_SA100 (High temperature)._ In this schedule, we started with a high
temperature ($T_{0}=100$) and only ran the initial part of the schedule
(approximately 15 minutes). In this schedule, we only made random moves that
are “non-local” in nature.

  * •

_SA20 (Low temperature)._ Here, we started with a low temperature ($T_{0}=20$)
and only ran the later part of the schedule (approximately 15 minutes). Due to
the low initial temperature, we only made random moves that are “local” in
nature. Such moves further optimized the score while preserving the overall
structure of the layout.

  * •

_SA50 (Medium temperature)._ In this variant, we started with an intermediate
temperature ($T_{0}=50$) and ran the middle part of a SA schedule
(approximately 15 minutes).

Figure 8. Figure illustrating the three simulated annealing schedules used in
our hybrid approaches.

Overall, we aimed to recruit $N=10$, $N=15$, and $N=20$ crowd workers per
criterion for networks G1, G2, and G3, respectively, for both _Hybrid_ and
_Crowd_ approach. We stopped recruiting crowd workers once the total gameplay
time taken by the workers in the sequence exceeded 24 hours. At the end of the
sequence, we fine-tuned the best layout so far to generate the final output
layout by using the fine-tuning procedure described in Harel and Sardas’s work
on incremental improvement of layouts of planar networks.

In order to highlight the quality of layouts generated by the Flud system, we
compared our results against four automatic layout algorithms.

  * •

_Simulated annealing (SA)_ (Davidson and Harel, 1996). We selected this
algorithm as our primary baseline due to its flexibility to accommodate all of
our criteria (Section 3.1.1). We ran the algorithm for a fixed number of
iterations (e.g., 500) where the temperature cools down from high initial
temperature ($T=T_{0}=100$) to low temperature ($T\approx 1$). To compare
performance of SA against _Crowd_ and _Hybrid_ , we ran the simulated
annealing schedule multiple times for 24 hours such that each schedule builds
upon the best layout created so far. We ran the baseline simulated annealing
algorithm on a machine with an Intel Xeon (16 cores at 2.40 GHz) CPU.

  * •

_Dig-Cola_ (Dwyer and Koren, 2005). Our second baseline was Dig-Cola, which
may indirectly optimize the number of downward pointing paths criterion since
it lays out nodes in a hierarchical manner. Dig-cola also provides a way to
conserve aesthetic criteria such as edge lengths and symmetries. We used the
implementation of Dig-Cola in the Neato program in the Graphviz package
(Ellson et al., 2001). We ran Dig-Cola with nine different values of the
minimum gap between levels $\\{0.1,0.2,0.5,1,2,5,-0.5,-1,-2\\}$, four
different values of the preferred edge length parameter ${1,3.125,5}$, and all
possible values of the overlap parameter. Finally, we used the layout that
produced the largest total score.

  * •

_IPSEP-Cola_ (Dwyer et al., 2006). Our third baseline was IPSEP-Cola, which
tries to ensure that node $s$ is placed above node $t$ if there is a directed
edge from $s$ to $t$. If the network contains directed cycles, IPSEP-Cola
computes the largest acyclic subgraph and relaxes the constraints on the
excluded edges. This approach may optimize the number of downward pointing
paths. We used the implementation of IPSEP-Cola in the Neato program in the
Graphviz package (Dwyer et al., 2006). We ran a parameter search similar to
Dig-Cola and used the layout that produced the largest total score in our
comparisons.

  * •

_Spring-electrical model_ (Hu, 2005). This force-directed algorithm uses
spring elasticity to keep connected nodes closer and electric charge repulsion
to keep disconnected nodes away from each other. The method is available as
the ‘sfdp’ program in the Graphviz package (Ellson et al., 2001). We ran the
program with six different values of the spring constant
$K=\\{0.1,0.2,0.5,1,2,5,10\\}$ and of the power of repulsive force
$R=\\{0.1,0.2,0.5,1,2,5,10\\}$. We used the layout from the parameter pair
with the highest score in our comparisons.

Finally, we also instrumented Flud to record each action taken by the crowd
workers during their gameplay as well as the corresponding scores and layout.
We used the collected data to analyze how the crowd workers played the game,
and understand the impact of features such as criterion-specific modes and
clues on the scores.

##  5\. Results

###  5.1. RQ1: How should Flud assign criterion-specific modes to players to
optimize the scores they achieve?

We used Experiment 1 to compare the performance of the crowdsourcing approach
when the criterion-specific modes are assigned in decreasing order of the
priorities (i.e., _Crowd_) versus a random assignment of modes (i.e., _Crowd-
Random_). Figure 9A shows that for each of the three networks, the median
total score achieved by the _Crowd_ approach was greater than the median score
achieved by _Crowd-Random_ approach. On further investigation, we found out
that the _Crowd_ approach achieved a better median per-criterion score for
downward pointing paths (DP), node distribution (ND), and node edge separation
(NED) criterion for all three networks (Figure 9B). On the other hand, the
_Crowd-Random_ approach achieved a higher median per-criterion score for non-
crossing edge pairs (EC) and edge length (EL) criterion for networks G2 and
G3. Since the _Crowd_ approach achieves a higher score for three out of five
layout criteria, including the important domain-specific DP criterion
(reflected in the total layout score), we decided to assign criterion-specific
modes in order of priorities in Experiment 2.

(A)(B) Figure 9.  Comparison of scores achieved by crowd workers when modes
are assigned randomly (_Crowd-Random_) and in decreasing order of priorities
(_Crowd_). (A) Distributions of total scores. (B) Distributions of per-
criterion scores.

In the _Crowd_ approach, we also observed that while four crowd workers were
able to lay out as many as 1,303 downward pointing paths in network G1, the
same number of crowd workers could only lay out 321 and 131 downward pointing
paths in networks G2 and G3, respectively. We attributed this difference in
performance to a large number of cycles in G2 and G3 compared to G1 (Table 1).
We noticed that in the presence of large numbers of cycles, crowd workers had
to make more moves in network G2 (mean=899) and G3 (mean=850) compared to
network G1 (mean=403) where the number of cycles is very low (Table 1).
Therefore, we decided to recruit crowd workers in proportion to the number of
simple paths from sources to targets (Table 1) in Experiment 2 to balance out
the crowd workers’ low throughput for downward pointing paths criterion in
networks with large number of cycles.

###  5.2. RQ2: How do the crowdsourcing approaches perform in comparison to
automated methods?

We used the data collected from Experiment 2 to answer this research question.
We considered several aspects to answer RQ2: overall scores, number of
downward-pointing paths, scores for aesthetic criteria, rate of improvement,
and final network layouts.

_Overall score_. First, we compared the performance of all the approaches on
the overall score (Figure 10). We observed that the crowd and hybrid
approaches clearly outperformed all the automated techniques for networks G2
and G3. In contrast, for network G1, the automated methods, especially SA, had
comparable performance to the crowd and hybrid approaches. We also noticed
that _Dig-Cola_ , _IPSEP-Cola_ , and _Spring Electrical_ algorithms hardly
improved the starting overall score for networks G2 and G3. However, _Dig-
Cola_ and _IPSEP-Cola_ were able to considerably improve the overall score for
network G1. We attributed this difference to the much larger number of cycles
in G2 and G3 in comparison to G1 (Table 1). To further understand these
results, we examined the downward-pointing paths results in detail.

Figure 10. Distributions of the total scores of layouts created by different
approaches.

_Downward-pointing paths criterion_. Here, we compared the performance of all
the approaches on the number of downward pointing pathways, our sole domain-
specific layout criterion (Figure 11). In Figure 11, we saw a trend similar to
overall scores shown in Figure 10. We attribute this similarity to the high
priority we assigned to the DP criterion. This explains that DP is the main
reason why our baseline methods did not perform well on networks G2 and G3. We
believe as the number of cycles increase in a network, it becomes harder for
the automated methods to optimize for downward pointing paths. In fact, _Dig-
Cola_ , _Spring Electrical_ , and _IPSEP-Cola_ computed very few downward
pointing paths ($\leq 10$) in networks G2 and G3. In contrast, crowd workers
seem to be able to observe the direction of the flow along the edges and
develop moves that significantly increase the number of downward pointing
paths despite the presence of cycles. Overall, these results indicate that
crowd workers are better than automated methods at downward pointing paths
task, specially for networks with several cycles. Moreover, _Crowd-SA100_
hybrid approach achieves even more number of downward pointing paths than
crowd workers alone (_Crowd_). We discuss the performance of the hybrid
approaches in detail later in the section.

Figure 11. Distributions of the number of downward pointing paths in the
layouts created by different approaches.

_Other aesthetic criteria_. Next, we compared the distributions of per-
criterion scores for the remaining layout criteria of all the approaches
(Figures A1–A4 in Appendix). In these figures, we observed that the simulated
annealing (_SA_) baseline outperformed the _Crowd_ , _Hybrid_ , and other
automated approaches on the EC, EL, ND, and NED criteria. However, when we
analyzed the median scores achieved by the _Crowd_ and _SA_ (refer to Figure
12A), we found that the (positive) percentage difference for the DP criterion
was one order of magnitude higher than the (negative) percentage difference
for each of the remaining criteria. Since, DP is our sole biology inspired
criterion, it is important to achieve high DP score to get a biologically
meaning drawing. Therefore, we believe there is an advantage (more
biologically meaningful drawing) of using _Crowd_ approach even though it
performs slightly worse (less aesthetic) than _Simulated Annealing_ on the EC,
EL, ND, and NED criteria. We also observed that the _Crowd_ approach
outperformed the _Spring Electrical_ and _Dig-Cola_ methods for all criteria
(Figure 12B–C). _Crowd_ also outperformed _IPSEP-Cola_ on the DP, ND, and NED
criteria (refer to Figure 12D).

_Crowd versus Hybrid_. The _Crowd_ approach outperformed the _Crowd-SA100_
hybrid approach (Figure 12H) on distance-based criteria (EL, ND, and NED). On
the other hand, _Crowd-SA100_ performed better on the DP and EC criteria. We
attribute this behavior to assistance from the _SA100_ simulated annealing
component in the _Crowd-SA100_ hybrid approach. We believe that since _SA100_
starts at a high temperature, it has the ability to make non-local node
movements that could result in the re-orientation of an edge to remove a
crossing or to make it downward pointing. These non-local moves allow the
_Crowd-SA100_ approach to use _SA100_ to further optimize for the DP and EC
criteria. In contrast, the hybrid _Crowd-SA20_ approach performed better than
the _Crowd_ approach for distance-based criteria such as EL and ND. Here,
_SA20_ can move a node only to a nearby position and, therefore, allows
_Crowd-SA20_ to explore the local neighborhood of a layout state in a more
exhaustive manner compared to crowd workers. Surprisingly, the _Crowd_
approach outperformed the hybrid _Crowd-SA20_ approach on the NED criterion,
despite assistance in local moves from _SA20_ (Figure 12F). Overall, the
results show that the hybrid _Crowd-SA100_ approach, where simulated annealing
makes non-local jumps, performs as well as or better than the non-hybrid
_Crowd_ approach.

Figure 12. Distributions of the percentage difference between median per-
criterion scores achieved by the _Crowd_ approach in comparison to other
methods. The black dotted line corresponds to a value of zero. Positive values
(to the right of this dotted line) indicate that the _Crowd_ approach
performed better than another method. The negative values (to the left of this
dotted line) indicate the opposite.

_Rate of improvement_. Next, to evaluate the rate of improvement, we computed
the average improvement in total score per minute achieved by a crowd worker
or a simulated annealing run in the _SA_ , _Crowd_ , and _Hybrid_ approaches
(Figure 13). Here, we observed that the _Crowd_ and _Hybrid_ approaches
improved the scores at a faster rate than _SA_ in all three networks, while
also considerably outscoring it in networks G2 and G3. We also noted that
_Crowd-SA100_ had a better average improvement in total score per minute than
_Crowd_ for all three networks. These results show that while _SA_ and _Crowd_
generate layouts comparable to _Crowd-SA100_ in some networks, _Crowd-SA100_
offers a better rate of improvement than these methods. Separately, we also
observed that the automated methods — _Dig-Cola_ , _IPSEP-Cola_ , and _Spring
Electrical_ — generated the final layout within seconds. The _Crowd_ and
_Hybrid_ approaches were slower, but clearly outperformed the automated
methods within a few minutes. This observation is supported by Figure A6 in
Appendix showing the scores achieved by each approach over time for each
network for all game sequences.

Figure 13. Bar plot of the average improvement in the total score per minute
achieved by a crowd worker or a simulated annealing run in the _SA_ , _Crowd_
, and _Hybrid_ approaches.

_Qualitative comparisons of layouts._ Finally, we qualitatively compared the
best layouts generated using Flud and automated approaches (Figure 14 and 15).
Figure 14 shows the layouts generated for network G1, a network representing
crosstalk from the Estrogen signaling pathway to the HIF-1 signaling pathway.
While Dig-Cola generated a layout with several downward pointing edges (Figure
14b), it is hard to read the layout because of many edge crossings and node-
node and node-edge overlaps. In contrast, the Crowd and SA approaches (Figure
14a and Figure 14c, respectively) created layouts with many downward-pointing
paths while achieving better separation among nodes and edges. Figure 15 shows
the layouts generated for network G2, a network representing the Epithelial-
to-mesenchymal transition (EMT). In the crowdsourced layout (Figure 15(a)), we
can clearly see the downward-pointing path from FGF to SOS/GRB2 on the right,
whereas it is hard to clearly see this two-edge path in layouts generated
using _Dig-Cola_ (Figure 15(b)) and _Spring Electrical_ (Figure 15(d)) method.
We also note that Figure 15(b) gives the false impression that paths from
source nodes to the SNAI1 target node are very short. In contrast, it is clear
from the crowdsourced layout (Figure 15(a)) that SNAI1 is regulated by
multiple upstream source nodes via multiple paths or mechanisms.

(a) Crowd approach (Overall Score=2,903,703)

(b) Dig-Cola (Overall Score=1,749,105)

(c) SA (Overall Score=2,904,454)

(d) Spring Electrical Model (Overall Score=16,941)

Figure 14. Best layouts generated by Crowd and baseline methods for network
G1. Green and yellow colored nodes represent the source and target nodes,
respectively. The upward pointing edges are shown in red whereas downward
pointing edges are shown in blue color.

(a) Crowd approach (Overall Score=429439)

(b) Dig-Cola (Overall Score=39349)

(c) SA (Overall Score=178718)

(d) Spring Electrical Model (Overall Score=16749)

Figure 15. Best layouts generated by Crowd and baseline methods for network
G2. Green and yellow colored nodes represent the source and target nodes,
respectively. The upward pointing edges are shown in red whereas downward
pointing edges are shown in blue color.

###  5.3. RQ3: What are the dynamics of the mixed-initiative collaboration in
hybrid approach?

To answer this question, we compared the average improvement to the total
score contributed by the crowd workers in different approaches (Figure 16),
using the data collected in Experiment 2. We found that the contribution by
crowd workers is lower in hybrid approaches than in the _Crowd_ approach,
where the crowd workers work alone without any help from simulated annealing.
We also noticed that on average, the contribution by simulated annealing is
lower in hybrid approaches than in the _SA_ approach for networks G1 and G2.
We believe that this decrease in contribution from crowd and simulated
annealing in hybrid approaches is because of the distribution of the total
work between these two components. However, the _Crowd_ and _SA_ collaborate
with each other in the _Crowd-SA100_ approach, leading to higher scoring
layouts than either from _Crowd_ or from _SA_ alone (Figure 10).

We also found that simulated annealing’s contributions in hybrid approaches
increased in comparison to _SA_ for graph G3. This observation is supported by
Figure 16, which shows that the simulated annealing in _Crowd-SA100_ achieved
1,875% more average improvement in total score than in _SA_. To highlight the
increase in simulated annealing’s performance in _Crowd-SA100_ in comparison
to _Crowd_ , we present an example which shows the progression of the layout
as crowd workers and _SA100_ collaborate back to back during one of the games
(Figure 17). In this figure, we have highlighted two paths from source to
target, for illustration purposes. Figure 17a shows the layout at the
beginning before crowd workers and simulated annealing start optimizing it.
There are many upward pointing edges that need corrections to make the
highlighted paths downward pointing. During the crowd task, the worker
corrected all of these edges except one (Figure 17b). However, one of the
highlighted paths was still left with an upward pointing edge. Next, _SA100_
took over and fixed the other path via two major movements in the layout
(Figure 17c–d). We argue that _SA100_ was able to optimize DP in this scenario
(Figure 17b) because the number of moves required to create a downward
pointing path was small in comparison to the starting layout (Figure 17a).

Figure 16.  Bar plot showing average improvement in total score made by
simulated annealing and crowd workers in hybrid approach.

(a) Before crowd started.

(b) After crowd finished.

(c) During SA100 process.

(d) After SA100 finished.

Figure 17. G3 network layouts at four different stages in an example game,
illustrating how crowd workers and simulated annealing build on each other’s
progress with the _Crowd-SA100_ approach. a) Layout before crowd worker
started playing the game. b) Layout after the crowd worker finished playing
the game. c) Layout during the _SA100_ annealing process. d) Layout after the
_SA100_ annealing process ends. For illustration purposes, the node and edge
widths in these layouts have been modified to highlight two representative
paths from source node to target node.

We attribute such hybrid collaborations as the main reason behind simulated
annealing’s ability to escape local optima (see the nearly vertical lines
ending in squares in Figure 18) in the hybrid approaches, unlike in the case
of SA. Overall, these results indicate the importance of contributions from
the crowd workers in the hybrid approach, since _SA100_ is similar to the
early annealing phase in SA (Figure 8).

G3 Figure 18. Scores achieved by each approach over time for network G3 for a
representative sequence. The $x$-axis represents the time taken in hours to
reach a particular score and the $y$-axis represents the score. The circle and
square markers correspond to crowd workers and simulated annealing
respectively.

###  5.4. How did the players play the Flud game?

We analyzed the crowd workers’ gameplay, their interaction with the game
elements in the Flud interface, and its impact on their performance (Figures
20 and 19) using the data from Experiment 2. Figure 20A shows the distribution
of the number of moves made by the crowd workers in each criterion-specific
mode. We found that the crowd workers not only made the highest number of
moves (median=126) in the DP mode, but also used the downward pointing path
clue (median=28) more often in comparison to other criterion-specific clues
(median=19). We attribute this behavior to the higher increase in score when
the crowd workers are assigned DP mode (mean improvement in total score per
session $\approx 73,629$) and use the downward pointing path clue (mean
improvement in DP score per move $\approx 6.3$). This observation is supported
by Figure 20B and Figure 19. In contrast to the DP criterion, we found that
the node-edge separation criterion clue, which gave the lowest average
improvement per move (Figure 20B), was used the least across all criteria
(Figure 20A).

Figure 19. Distribution of average improvement in per-criterion scores
achieved by crowd workers in each mode.

Next, in order to understand if the clues helped the players, we compared the
average improvement per move for each criterion (Figure 20B). Our results show
that when the crowd workers moved a node not involved in a clue, they lost
points and decreased the criterion-specific score. In contrast, when players
changed the position of a node that was highlighted in a clue, the criterion-
specific score increased, on average. These results indicate that the
criterion-specific clues helped the crowd workers to improve the criterion-
specific scores.

Then, we analyzed the improvement in per-criterion scores made by crowd
workers in each criterion-specific mode as shown in Figure 19. We found that
the crowd workers improved the criterion-specific score while playing the game
in a criterion-specific mode.

(A)(B) Figure 20.  A) Distribution of number of times crowd workers moved
nodes with or without a clue in a criterion specific mode. B) Distribution of
average improvement in per-criterion score per move achieved by crowd workers
with or without using the criterion-specific clue.

##  6\. Discussion

In this paper, we presented Flud, an online game with a purpose that allows
humans with no expertise to design biologically meaningful graph layouts with
the help of algorithmically generated suggestions. Below, we discuss some key
takeaways from our evaluation, focusing on overall performance differences,
reflections, and design implications.

###  6.1. Crowd outperforms algorithms

We found that crowdsourcing the layout design task on Flud can generate more
meaningful layouts than state-of-the-art algorithms for laying out biological
networks. Specifically, our results indicated that crowd workers, in general,
are considerably better than the state-of-the-art algorithmic approaches at
the downward pointing path task, i.e., laying out downward pointing paths from
source nodes to target nodes in a directed network. We believe that there are
two main reasons for the crowds’ superior performance.

First, biological networks have feedback loops, and the crowd workers are able
to carefully position the nodes in a feedback loop with respect to each other
in order to optimize the number of downward paths. In contrast, an
optimization method such as simulated annealing may get stuck in local optima
in the presence of feedback loops or cycles, as seen in the network G3.
Second, algorithmically generated suggestions (clues) played an essential role
in the players’ performance. These suggestions streamlined the broader layout
design goal by asking the players to carefully solve a smaller puzzle (or
micro-task), e.g., to move the suggested elements in a certain way in the
given network so as to increase the total score. In other words, we were able
to reduce the overall challenge level by algorithmically breaking down the
layout design task into smaller puzzles that benefit from human judgment and
are solvable by untrained crowd workers.

In contrast, algorithmic approaches such as _Dig-Cola_ and _IPSEP-Cola_ focus
on optimizing the number of downward pointing edges instead of paths. We
stress that merely counting the number of downward pointing edges (Purchase,
2002) is not sufficient to capture the flow of information. For example, a
downward pointing path from a receptor (a protein molecule that receives
signals from outside a cell) through intermediary proteins to a transcription
factor (a protein that controls the cell’s response to the signal) might be
crucial to understand the underlying mechanism of cell signaling in a
biological network.

While the _Crowd_ approach was able to outperform the automated methods, the
hybrid _Crowd-SA100_ approach offered faster rate of improvement of the score.
Moreover, our results indicated that there is a symbiotic relationship between
crowd workers and simulated annealing in the hybrid approaches. On the one
hand, we believe that the crowd workers improve the layouts such that it is in
a state where simulated annealing can make a non-trivial modification to the
layout that increases the score. On the other hand, simulated annealing
relieves crowd workers of redundant and trivial tasks by improving the layout
whenever possible between crowd worker sessions.

###  6.2. Reflecting on design decisions

We now discuss some of the decisions we made while planning the scoring
system, experiments, and incentives.

####  6.2.1. Scoring system

One key decision we made was to normalize the per-criterion scores used to
compare the quality of different layouts. While the downward-pointing paths
criterion is new, quantitative metrics for rest of layout criteria have been
defined in prior work (Purchase, 2002; Purchase et al., 2001). However, many
of these metrics are on different scales, which makes it challenging to
compare layouts of different network sizes. Additionally, we cannot use the
same priorities (weights) to compute the weighted layout score for different
network sizes. Therefore, we normalized each per-criterion score to lie
between 0 and 1, with higher scores being more desirable. This strategy
allowed us to use the same priorities for networks G1–G3 in our experiments.

Minimizing the number of edge crossings is one of the most popular aesthetic
criteria. It has been empirically validated as an important measure for good
network drawing (Purchase et al., 2001; Taylor and Rodgers, 2005; Tamassia et
al., 1988). As an alternative to $\mathit{EC}$ score, we considered
_crosslessness_ (Purchase, 2002; Kwon et al., 2018). We discarded it as an
option since its values were very close to $EC(G)$ for all the networks we
used in our experiments. Moreover, we did not see any benefit of using
crosslessness over $EC(G)$ to give feedback to the game players. Hence, we
decided to use the $EC(G)$ metric.

Another design decision we made was to choose a very high priority (400) for
the downward pointing paths criterion score (DP) in our experiments. We
decided to assign the highest priority to DP because it is our sole domain-
oriented criterion, and we wanted it to be preferred over the aesthetic layout
criteria in case of conflicts. Moreover, due to our poor approximation of the
maximum possible number of downward pointing paths in networks with cycles,
the DP scores were prone to be very low for such networks. If we had selected
uniform priorities, due to these low DP scores, algorithms such as _Simulated
Annealing_ would choose to optimize for aesthetic layout criteria in case of a
conflict, despite even trying the priority of four (greater than the priority
of rest of the criteria) for the DP criterion. Therefore, we decided to select
a very high priority of 400 so that the weighted contribution of downward
pointing paths to the overall layout score is generally higher than other per-
criterion scores.

####  6.2.2. Worker incentives

In this work, we empirically showed that paid crowd workers recruited from
Amazon Mechanical Turk can help researchers by successfully playing the Flud
game and achieving high scores that correspond to improved network layouts. We
incentivized these workers to submit high-quality layouts by paying them based
on their scores (Ho et al., 2015). Paid workers offered useful advantages for
this research, allowing us to temporarily sidestep the need to build an online
community with a critical mass of game players while rapidly prototyping and
iterating on the Flud game mechanics in a scaleable, controlled environment.
However, prior work in crowdsourcing suggests (Rogstadius et al., 2011;
Borromeo and Toyama, 2016) that unpaid workers or volunteers submit higher
quality work in comparison to paid workers. Moreover, the volunteers may be
more motivated to perform the task if it supports a worthy cause (for example,
scientific research) (Katsuragawa et al., 2019). Given that Flud aims to aid
scientific researchers, we expect an intrinsically motivated subset of
volunteers would spend more time playing the game and make more improvements
in a game session. Moreover, as the players get familiar with the task, we
expect high-performing players to develop layout strategies they can reuse
across different games (networks), as has been observed in other games like
EteRNA and FoldIt. In future work, we are exploring what modifications are
necessary to the Flud platform to motivate volunteer gameplay, and
consequently, how volunteer player performance compares with paid crowd
workers from this study.

Currently, Flud only displays the current top score during a game and does not
have a leaderboard that shows the total points earned by the top performers.
However, prior work shows that leaderboard can play an important role in games
to motivate high performance (Hamari et al., 2014). In this work, we decided
not to use a leaderboard since our participants were crowd workers on MTurk
who are primarily motivated by compensation rather than by competitive
gameplay. Designing a leaderboard to motivate volunteer gameplay in a context
where players are essentially collaborating with each other is a promising
future direction.

###  6.3. Design implications

We now discuss some practical implications for our work.

####  6.3.1. Mixed-initiative systems are effective in layout tasks

Prior work shows that humans are adept at spatial reasoning skills and
strategic thinking (Williams et al., 2016). These qualities allow users to
successfully explore a search space by outperforming algorithms at tasks that
require visual perception. In our work, we found that humans are good at a
task that requires observation and spatial arrangement to maintain a certain
direction of network flow. Corroborating prior work, we found that combining
human intelligence with automated approaches can achieve results better than
what either could produce alone. One implication of this finding is that
systems can leverage mixed-initiative settings to solve for other types of
layout tasks that require careful relative arrangement of entities in a two-
dimensional space. Examples of such tasks, which manifest in many creative and
analytical disciplines, include drawing integrated circuits, mapping social
networks, and designing interior spaces in houses and buildings.

####  6.3.2. Enable preference elicitation to balance multiple criteria

Balancing multiple criteria in a design task can be challenging for novices.
Prior work found that novices are limited by their incomplete knowledge and
therefore need preference elicitation support from the system (An et al.,
2011). For example, it may be difficult for a non-expert to tell whether one
criterion is more important (and to what extent) than another criterion. It
may be even more difficult for a user to understand the consequences of
choosing to focus on one constraint before another. Therefore, preference
elicitation support is required to help the non-expert user decide on a
certain course of action. Flud overcomes this challenge by transparently
showing the per-criterion scores, their priorities, and the relative change
(increase/decrease) after each move. These features allows the players to take
informative decisions while trying to balance multiple criteria.

####  6.3.3. Computationally assign modes to break players out of unproductive
play strategies

Prior work shows that in human computation games, players can gravitate
towards gameplay strategies that are not advised under certain situations
(Williams et al., 2016). We saw a similar behavior when we allowed the players
to choose the mode instead of fixing a mode at the start of the game. We found
that players gravitate towards distance based modes such as edge length and
node distribution, ignoring the higher priority modes like downward pointing
paths. We attributed this behavior to players inexpertise in choosing the
appropriate criterion to focus on at a given stage in the game. We overcame
this challenge by passing the control to the Flud system and letting it decide
the modes for the player. In our work, we empirically showed that assigning
the modes in the order of their priorities generates better results than
assigning them randomly.

####  6.3.4. Automatic suggestions offer guidance when players are uncertain

Despite having superior intelligence and cognitive skills, players can
sometimes be overwhelmed by the complexity of the game. Under such
circumstances, Flud automatically provides players with a suggestion via the
clue feature. These suggestions guide players by focusing their attention on a
smaller, more tractable puzzle inside the overall game. This approach not only
reduces the challenge level, but also helps the player make progress when they
get stuck.

###  6.4. Limitations

One of the limitations of our evaluation is that the number of networks is
small. Since we sought to evaluate multiple game sequences for each of the
proposed approaches, we were limited to a small number of networks. A larger
number of networks would allow us to show the applicability of the proposed
methods to various types of networks. However, the main goals of this paper
were to show that the proposed approaches perform better than the automated
methods for networks with large number of cycles and that our results are
replicable. Therefore, we used three networks with different numbers of cycles
and repeated the game sequence for each approach three times.

Another limitation of our Flud implementation is that its network rendering is
currently optimized for small networks ($<100$ nodes). Prior work shows that
people with no expertise in network drawing find it difficult to handle large
networks (Dwyer et al., 2009). Therefore, we believe that optimizing the
system to support larger networks is not the way forward. Instead, we propose
to split the larger networks and ask the Flud players to work on small
subnetworks. Yuan et al. (Yuan et al., 2012) proposed a strategy to combine
user-generated layouts into a single layout for a large network. Adapting
their method to support the downward pointing path criterion for large
networks on Flud would be an important future goal.

##  7\. Conclusion

In this work, we explored the potential of crowd-algorithm collaboration for
visualizing biological networks. We describe how we gamified the visualization
task and made it more accessible to humans, even if they have no biological or
computer science expertise. Our results show that such a collaboration between
humans and algorithms leads to higher scoring layouts than either from humans
or algorithms alone. Our contributions include (i) a novel mixed-initiative
game with a purpose that combines crowdsourcing with computational engines to
create high-quality visualizations of biological networks and (ii) experiments
that provide empirical evidence of the benefits of mixed-initiative layout
schemes compared to algorithmic baselines.

###### Acknowledgements.

We thank Lee Lisle, Parker Irving, and Jeffrey Law. This research was
supported by NIH grant 1UH2CA203768-01.

## References

  * (1)
  * An et al. (2011) Bo An, Manish Jain, Milind Tambe, and Christopher Kiekintveld. 2011.  Mixed-Initiative Optimization in Security Games: A Preliminary Report. In _Help Me Help You: Bridging the Gaps in Human-Agent Collaboration, Papers from the 2011 AAAI Spring Symposium, Technical Report SS-11-05, Stanford, California, USA, March 21-23, 2011_. AAAI.  http://www.aaai.org/ocs/index.php/SSS/SSS11/paper/view/2375
  * Anderson-Lee et al. (2016) J. Anderson-Lee, E. Fisker, V. Kosaraju, M. Wu, J. Kong, J. Lee, M. Lee, M. Zada, A. Treuille, and R. Das. 2016.  Principles for Predicting RNA Secondary Structure Design Difficulty.  _J. Mol. Biol._ 428, 5 Pt A (Feb 2016), 748–757.
  * Barabasi and Oltvai (2004) A.L. Barabasi and Z.N. Oltvai. 2004.  Network biology: understanding the cell’s functional organization.  _Nat Rev Genet_ 5, 2 (2004), 101–13.
  * Batagelj and Mrvar (2001) Vladimir Batagelj and Andrej Mrvar. 2001.  Pajek - Analysis and Visualization of Large Networks.  In _Graph Drawing_. 477–478.  https://doi.org/10.1007/3-540-45848-4_54
  * Bauer et al. (2012) Andreas Bauer, Michael Kaufmann, Ignaz Rutter, and Julian Vordermeier.  CycleXings: Game Idea.
  * Baur and Brandes (2004) Michael Baur and Ulrik Brandes. 2004.  Crossing Reduction in Circular Layouts. In _Graph-Theoretic Concepts in Computer Science, 30th International Workshop,WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers_ _(Lecture Notes in Computer Science)_ , Juraj Hromkovic, Manfred Nagl, and Bernhard Westfechtel (Eds.), Vol. 3353. Springer, 332–343.  https://doi.org/10.1007/978-3-540-30559-0_28
  * Bennett et al. (2007) Chris Bennett, Jody Ryall, Leo Spalteholz, and Amy Gooch. 2007\.  The aesthetics of graph visualization.  _Computational aesthetics_ 2007 (2007), 57–64.
  * Bharadwaj et al. (2017) A. Bharadwaj, D. P. Singh, A. Ritz, A. N. Tegge, C. L. Poirel, P. Kraikivski, N. Adames, K. Luther, S. D. Kale, J. Peccoud, J. J. Tyson, and T. M. Murali. 2017\.  GraphSpace: stimulating interdisciplinary collaborations in network biology.  _Bioinformatics_ 33, 19 (Oct 2017), 3134–3136.
  * Borromeo and Toyama (2016) Ria Mae Borromeo and Motomichi Toyama. 2016.  An investigation of unpaid crowdsourcing.  _Human-centric Computing and Information Sciences_ 6, 1 (2016), 11\.
  * Chau et al. (2011) Duen Horng Chau, Aniket Kittur, Jason I. Hong, and Christos Faloutsos. 2011.  Apolo: making sense of large network data by combining rich user interaction and machine learning. In _Proceedings of the SIGCHI Conference on Human Factors in Computing Systems_ _(CHI ’11)_. ACM, 167–176.  https://doi.org/10.1145/1978942.1978967
  * Cheng and Bernstein (2015) Justin Cheng and Michael S. Bernstein. 2015.  Flock: Hybrid Crowd-Machine Learning Classifiers. In _Proceedings of the 18th ACM Conference on Computer Supported Cooperative Work & Social Computing, CSCW 2015, Vancouver, BC, Canada, March 14 - 18, 2015_, Dan Cosley, Andrea Forte, Luigina Ciolfi, and David McDonald (Eds.). ACM, 600–611.  https://doi.org/10.1145/2675133.2675214
  * Chung et al. (2017) Haeyong Chung, Sai Prashanth Dasari, Santhosh Nandhakumar, and Christopher Andrews. 2017\.  CRICTO: Supporting Sensemaking through Crowdsourced Information Schematization. In _2017 IEEE Conference on Visual Analytics Science and Technology, VAST 2017, Phoenix, AZ, USA, October 3-6, 2017_ , Brian Fisher, Shixia Liu, and Tobias Schreck (Eds.). IEEE Computer Society, 139–150.  https://doi.org/10.1109/VAST.2017.8585484
  * Cooper (2014) Seth Cooper. 2014\.  _A Framework for Scientific Discovery through Video Games (dissertation, updated version)_. ACM Books, Vol. 3.  ACM / Morgan & Claypool.
  * Cooper et al. (2010) Seth Cooper, Firas Khatib, Adrien Treuille, Janos Barbero, Jeehyung Lee, Michael Beenen, Andrew Leaver-Fay, David Baker, Zoran Popović, et al. 2010\.  Predicting protein structures with a multiplayer online game.  _Nature_ 466, 7307 (2010), 756.
  * Cowley et al. (2008) Ben Cowley, Darryl Charles, Michaela Black, and Ray Hickey. 2008.  Toward an Understanding of Flow in Video Games.  _Comput. Entertain._ 6, 2, Article 20 (July 2008), 27 pages.  https://doi.org/10.1145/1371216.1371223
  * Csikszentmihalyi (1990) M Csikszentmihalyi. 1990\.  _Flow: The Psychology of Optimal Experience._ HarperCollins Publishers.
  * Davidson and Harel (1996) Ron Davidson and David Harel. 1996.  Drawing graphs nicely using simulated annealing.  _ACM Transactions on Graphics (TOG)_ 15, 4 (1996), 301–331.
  * Di Battista et al. (1994) Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G Tollis. 1994.  Algorithms for drawing graphs: an annotated bibliography.  _Computational Geometry_ 4, 5 (1994), 235–282.
  * Duncan et al. (2012) Christian A. Duncan, Carsten Gutwenger, Lev Nachmanson, and Georg Sander. 2012.  Graph Drawing Contest Report. In _Graph Drawing - 20th International Symposium, GD 2012, Redmond, WA, USA, September 19-21, 2012, Revised Selected Papers_ _(Lecture Notes in Computer Science)_ , Walter Didimo and Maurizio Patrignani (Eds.), Vol. 7704. Springer, 575–579.  https://doi.org/10.1007/978-3-642-36763-2_58
  * Dwyer and Koren (2005) Tim Dwyer and Yehuda Koren. 2005.  DIG-COLA: Directed Graph Layout through Constrained Energy Minimization. In _IEEE Symposium on Information Visualization (InfoVis 2005), 23-25 October 2005, Minneapolis, MN, USA_ , John T. Stasko and Matthew O. Ward (Eds.). IEEE Computer Society, 65–72.  https://doi.org/10.1109/INFVIS.2005.1532130
  * Dwyer et al. (2006) Tim Dwyer, Yehuda Koren, and Kim Marriott. 2006.  IPSep-CoLa: An incremental procedure for separation constraint layout of graphs.  _IEEE Transactions on Visualization and Computer Graphics_ 12, 5 (2006), 821–828.
  * Dwyer et al. (2009) Tim Dwyer, Bongshin Lee, Danyel Fisher, Kori Inkpen Quinn, Petra Isenberg, George G. Robertson, and Chris North. 2009.  A Comparison of User-Generated and Automatic Graph Layouts.  _IEEE Trans. Vis. Comput. Graph._ 15, 6 (2009), 961–968.  https://doi.org/10.1109/TVCG.2009.109
  * Eades et al. (1996) Peter Eades, Qing-Wen Feng, and Xuemin Lin. 1996.  Straight-Line Drawing Algorithms for Hierarchical Graphs and Clustered Graphs. In _Graph Drawing, Symposium on Graph Drawing, GD ’96, Berkeley, California, USA, September 18-20, Proceedings_ _(Lecture Notes in Computer Science)_ , Stephen C. North (Ed.), Vol. 1190. Springer, 113–128.  https://doi.org/10.1007/3-540-62495-3_42
  * Eiglsperger et al. (2000) Markus Eiglsperger, Ulrich Fößmeier, and Michael Kaufmann. 2000\.  Orthogonal graph drawing with constraints.  In _Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, January 9-11, 2000, San Francisco, CA, USA._ , David B. Shmoys (Ed.). 3–11.  http://dl.acm.org/citation.cfm?id=338219.338225
  * Ellson et al. (2001) John Ellson, Emden R. Gansner, Eleftherios Koutsofios, Stephen C. North, and Gordon Woodhull. 2001\.  Graphviz - Open Source Graph Drawing Tools. In _International Symposium on Graph Drawing_. Springer, Springer, 483–484.  https://doi.org/10.1007/3-540-45848-4_57
  * Eppstein (2014) David Eppstein. 2014\.  Drawing Arrangement Graphs In Small Grids, Or How To Play Planarity.  _J. Graph Algorithms Appl._ 18, 2 (2014), 211–231.  https://doi.org/10.7155/jgaa.00319
  * Ferrara (2013) John Ferrara. 2013\.  Games for persuasion: Argumentation, procedurality, and the lie of gamification.  _Games and Culture_ 8, 4 (2013), 289–304.
  * Franz et al. (2016) M. Franz, C. T. Lopes, G. Huck, Y. Dong, O. Sumer, and G. D. Bader. 2016\.  Cytoscape.js: a graph theory library for visualisation and analysis.  _Bioinformatics_ 32, 2 (Jan 2016), 309–311.
  * Fruchterman and Reingold (1991) Thomas MJ Fruchterman and Edward M Reingold. 1991.  Graph drawing by force-directed placement.  _Software: Practice and experience_ 21, 11 (1991), 1129–1164.
  * Gansner and Koren (2006) Emden R. Gansner and Yehuda Koren. 2006.  Improved Circular Layouts. In _Graph Drawing, 14th International Symposium, GD 2006, Karlsruhe, Germany, September 18-20, 2006. Revised Papers_ _(Lecture Notes in Computer Science)_ , Michael Kaufmann and Dorothea Wagner (Eds.), Vol. 4372. Springer, 386–398.  https://doi.org/10.1007/978-3-540-70904-6_37
  * Gansner et al. (1993) Emden R Gansner, Eleftherios Koutsofios, Stephen C North, and K-P Vo. 1993.  A technique for drawing directed graphs.  _IEEE Transactions on Software Engineering_ 19, 3 (1993), 214–230.
  * Gibson et al. (2013) Helen Gibson, Joe Faith, and Paul Vickers. 2013.  A survey of two-dimensional graph layout techniques for information visualisation.  _Information visualization_ 12, 3-4 (2013), 324–357.
  * Green et al. (2014) Spence Green, Jason Chuang, Jeffrey Heer, and Christopher D. Manning. 2014.  Predictive translation memory: a mixed-initiative system for human language translation. In _The 27th Annual ACM Symposium on User Interface Software and Technology, UIST ’14, Honolulu, HI, USA, October 5-8, 2014_ , Hrvoje Benko, Mira Dontcheva, and Daniel Wigdor (Eds.). ACM, 177–187.  https://doi.org/10.1145/2642918.2647408
  * Hagberg et al. (2008) Aric Hagberg, Pieter Swart, and Daniel S Chult. 2008\.  _Exploring network structure, dynamics, and function using NetworkX_.  Technical Report. Los Alamos National Lab.(LANL), Los Alamos, NM (United States).
  * Hamari et al. (2014) Juho Hamari, Jonna Koivisto, and Harri Sarsa. 2014\.  Does Gamification Work? - A Literature Review of Empirical Studies on Gamification. In _47th Hawaii International Conference on System Sciences, HICSS 2014, Waikoloa, HI, USA, January 6-9, 2014_. IEEE Computer Society, 3025–3034.  https://doi.org/10.1109/HICSS.2014.377
  * Harel and Sardas (1995) David Harel and Meir Sardas. 1995.  _An incremental drawing algorithm for planar graphs_.  Technical Report. Cornell University.
  * Hashi Puzzle Bridges Game ([n. d.]) Hashi Puzzle Bridges Game.  Puzzle Bridges.  https://www.puzzle-bridges.com/
  * Heer (2019) Jeffrey Heer. 2019\.  Agency plus automation: Designing artificial intelligence into interactive systems.  _Proceedings of the National Academy of Sciences_ 116, 6 (2019), 1844–1850.
  * Heer et al. (2007) Jeffrey Heer, Fernanda B. Viégas, and Martin Wattenberg. 2007\.  Voyagers and voyeurs: supporting asynchronous collaborative information visualization. In _Proceedings of the 2007 Conference on Human Factors in Computing Systems, CHI 2007, San Jose, California, USA, April 28 - May 3, 2007_ , Mary Beth Rosson and David J. Gilmore (Eds.). ACM, 1029–1038.  https://doi.org/10.1145/1240624.1240781
  * Ho et al. (2015) Chien-Ju Ho, Aleksandrs Slivkins, Siddharth Suri, and Jennifer Wortman Vaughan. 2015.  Incentivizing High Quality Crowdwork. In _Proceedings of the 24th International Conference on World Wide Web, WWW 2015, Florence, Italy, May 18-22, 2015_ , Aldo Gangemi, Stefano Leonardi, and Alessandro Panconesi (Eds.). ACM, 419–429.  https://doi.org/10.1145/2736277.2741102
  * Hu (2005) Yifan Hu. 2005.  Efficient, high-quality force-directed graph drawing.  _Mathematica Journal_ 10, 1 (2005), 37–71.
  * Jacomy et al. (2014) Mathieu Jacomy, Tommaso Venturini, Sebastien Heymann, and Mathieu Bastian. 2014.  ForceAtlas2, a continuous graph layout algorithm for handy network visualization designed for the Gephi software.  _PloS one_ 9, 6 (2014), e98679.
  * Kamada et al. (1989) Tomihisa Kamada, Satoru Kawai, et al. 1989\.  An algorithm for drawing general undirected graphs.  _Information processing letters_ 31, 1 (1989), 7–15.
  * Kandel et al. (2011) Sean Kandel, Andreas Paepcke, Joseph M. Hellerstein, and Jeffrey Heer. 2011.  Wrangler: interactive visual specification of data transformation scripts. In _Proceedings of the International Conference on Human Factors in Computing Systems, CHI 2011, Vancouver, BC, Canada, May 7-12, 2011_ , Desney S. Tan, Saleema Amershi, Bo Begole, Wendy A. Kellogg, and Manas Tungare (Eds.). ACM, 3363–3372.  https://doi.org/10.1145/1978942.1979444
  * Katsuragawa et al. (2019) Keiko Katsuragawa, Qi Shu, and Edward Lank. 2019.  PledgeWork: Online Volunteering through Crowdwork. In _Proceedings of the 2019 CHI Conference on Human Factors in Computing Systems, CHI 2019, Glasgow, Scotland, UK, May 04-09, 2019_ , Stephen A. Brewster, Geraldine Fitzpatrick, Anna L. Cox, and Vassilis Kostakos (Eds.). ACM, 311\.  https://doi.org/10.1145/3290605.3300541
  * Kawrykow et al. (2012) Alexander Kawrykow, Gary Roumanis, Alfred Kam, Daniel Kwak, Clarence Leung, Chu Wu, Eleyine Zarour, Luis Sarmenta, Mathieu Blanchette, Jérôme Waldispühl, et al. 2012\.  Phylo: a citizen science approach for improving multiple sequence alignment.  _PloS one_ 7, 3 (2012), e31362.
  * Kim et al. (2013) Juho Kim, Haoqi Zhang, Paul André, Lydia B. Chilton, Wendy E. Mackay, Michel Beaudouin-Lafon, Robert C. Miller, and Steven P. Dow. 2013.  Cobi: a community-informed conference scheduling tool. In _The 26th Annual ACM Symposium on User Interface Software and Technology, UIST’13, St. Andrews, United Kingdom, October 8-11, 2013_ , Shahram Izadi, Aaron J. Quigley, Ivan Poupyrev, and Takeo Igarashi (Eds.). ACM, 173–182.  https://doi.org/10.1145/2501988.2502034
  * Kim et al. (2014b) Jinseop S Kim, Matthew J Greene, Aleksandar Zlateski, Kisuk Lee, Mark Richardson, Srinivas C Turaga, Michael Purcaro, Matthew Balkam, Amy Robinson, Bardia F Behabadi, et al. 2014b.  Space–time wiring specificity supports direction selectivity in the retina.  _Nature_ 509, 7500 (2014), 331.
  * Kim et al. (2014a) J. S. Kim, M. J. Greene, A. Zlateski, K. Lee, M. Richardson, S. C. Turaga, M. Purcaro, M. Balkam, A. Robinson, B. F. Behabadi, M. Campos, W. Denk, and H. S. Seung. 2014a.  Space-time wiring specificity supports direction selectivity in the retina.  _Nature_ 509, 7500 (May 2014), 331–336.
  * Koren (2003) Yehuda Koren. 2003\.  On Spectral Graph Drawing. In _Computing and Combinatorics, 9th Annual International Conference, COCOON 2003, Big Sky, MT, USA, July 25-28, 2003, Proceedings_ _(Lecture Notes in Computer Science)_ , Tandy J. Warnow and Binhai Zhu (Eds.), Vol. 2697. Springer, 496–508.  https://doi.org/10.1007/3-540-45071-8_50
  * Koren (2005) Yehuda Koren. 2005\.  Drawing graphs by eigenvectors: theory and practice.  _Computers & Mathematics with Applications_ 49, 11-12 (2005), 1867–1888.
  * Kwon et al. (2018) Oh-Hyun Kwon, Tarik Crnovrsanin, and Kwan-Liu Ma. 2018\.  What Would a Graph Look Like in This Layout? A Machine Learning Approach to Large Graph Visualization.  _IEEE transactions on visualization and computer graphics_ 24, 1 (2018), 478–488.
  * Lee et al. (2014) J. Lee, W. Kladwang, M. Lee, D. Cantu, M. Azizyan, H. Kim, A. Limpaecher, S. Yoon, A. Treuille, and R. Das. 2014.  RNA design rules from a massive open laboratory.  _Proc. Natl. Acad. Sci. U.S.A._ 111, 6 (Feb 2014), 2122–2127.
  * Li et al. (2018) Tianyi Li, Asmita Shah, Kurt Luther, and Chris North. 2018\.  Crowdsourcing Intelligence Analysis with Context Slices.  _CHI 2018 Workshop on Sensemaking in a Senseless World_ (2018).
  * Pavlopoulos et al. (2008) Georgios A Pavlopoulos, Anna-Lynn Wegener, and Reinhard Schneider. 2008.  A survey of visualization tools for biological network analysis.  _Biodata mining_ 1, 1 (2008), 12.
  * Purchase (2002) Helen C Purchase. 2002\.  Metrics for graph drawing aesthetics.  _Journal of Visual Languages & Computing_ 13, 5 (2002), 501–516.
  * Purchase et al. (2001) Helen C. Purchase, Matthew McGill, Linda Colpoys, and David A. Carrington. 2001.  Graph Drawing Aesthetics and the Comprehension of UML Class Diagrams: An Empirical Study. In _Australasian Symposium on Information Visualisation, InVis.au, Sydney, Australia, 3-4 December 2001_ _(CRPIT)_ , Peter Eades and Tim Pattison (Eds.), Vol. 9. Australian Computer Society, 129–137.  http://crpit.com/confpapers/CRPITV9Purchase2.pdf
  * Rogstadius et al. (2011) Jakob Rogstadius, Vassilis Kostakos, Aniket Kittur, Boris Smus, Jim Laredo, and Maja Vukovic. 2011\.  An Assessment of Intrinsic and Extrinsic Motivation on Task Performance in Crowdsourcing Markets. In _Proceedings of the Fifth International Conference on Weblogs and Social Media, Barcelona, Catalonia, Spain, July 17-21, 2011_ , Lada A. Adamic, Ricardo A. Baeza-Yates, and Scott Counts (Eds.). The AAAI Press.  http://www.aaai.org/ocs/index.php/ICWSM/ICWSM11/paper/view/2778
  * Sarma et al. (2015) Akash Das Sarma, Ayush Jain, Arnab Nandi, Aditya G. Parameswaran, and Jennifer Widom. 2015\.  Surpassing Humans and Computers with JELLYBEAN: Crowd-Vision-Hybrid Counting Algorithms. In _Proceedings of the Third AAAI Conference on Human Computation and Crowdsourcing, HCOMP 2015, November 8-11, 2015, San Diego, California, USA._ , Elizabeth Gerber and Panos Ipeirotis (Eds.). AAAI Press, 178–187.  http://www.aaai.org/ocs/index.php/HCOMP/HCOMP15/paper/view/11593
  * Schrier (2018) Karen Schrier. 2018\.  Designing Learning with Citizen Science and Games.  _The Emerging Learning Design Journal_ 4, 1 (2018), 3\.
  * Shannon et al. (2003) Paul Shannon, Andrew Markiel, Owen Ozier, Nitin S Baliga, Jonathan T Wang, Daniel Ramage, Nada Amin, Benno Schwikowski, and Trey Ideker. 2003.  Cytoscape: a software environment for integrated models of biomolecular interaction networks.  _Genome research_ 13, 11 (2003), 2498–2504.
  * Siangliulue et al. (2016) Pao Siangliulue, Joel Chan, Steven P. Dow, and Krzysztof Z. Gajos. 2016.  IdeaHound: Improving Large-scale Collaborative Ideation with Crowd-Powered Real-time Semantic Modeling. In _Proceedings of the 29th Annual Symposium on User Interface Software and Technology_ _(UIST ’16)_. ACM, 609–624.  https://doi.org/10.1145/2984511.2984578
  * Singh et al. (2018) Divit P. Singh, Lee Lisle, T. M. Murali, and Kurt Luther. 2018\.  CrowdLayout: Crowdsourced Design and Evaluation of Biological Network Visualizations. In _Proceedings of the 2018 CHI Conference on Human Factors in Computing Systems, CHI 2018, Montreal, QC, Canada, April 21-26, 2018_ , Regan L. Mandryk, Mark Hancock, Mark Perry, and Anna L. Cox (Eds.). ACM, 232.  https://doi.org/10.1145/3173574.3173806
  * Smoot et al. (2010) Michael E Smoot, Keiichiro Ono, Johannes Ruscheinski, Peng-Liang Wang, and Trey Ideker. 2010.  Cytoscape 2.8: new features for data integration and network visualization.  _Bioinformatics_ 27, 3 (2010), 431–432.
  * Sugiyama et al. (1981) Kozo Sugiyama, Shojiro Tagawa, and Mitsuhiko Toda. 1981\.  Methods for visual understanding of hierarchical system structures.  _IEEE Transactions on Systems, Man, and Cybernetics_ 11, 2 (1981), 109–125.
  * Tamassia (2013) Roberto Tamassia. 2013\.  _Handbook of graph drawing and visualization_.  Chapman and Hall/CRC.
  * Tamassia et al. (1988) Roberto Tamassia, Giuseppe Di Battista, and Carlo Batini. 1988\.  Automatic graph drawing and readability of diagrams.  _IEEE Transactions on Systems, Man, and Cybernetics_ 18, 1 (1988), 61–79.
  * Taylor and Rodgers (2005) Martyn Taylor and Peter Rodgers. 2005.  Applying Graphical Design Techniques to Graph Visualisation. In _9th International Conference on Information Visualisation, IV 2005, 6-8 July 2005, London, UK_. IEEE Computer Society, 651–656.  https://doi.org/10.1109/IV.2005.19
  * Tripathi et al. (2014) Shailesh Tripathi, Matthias Dehmer, and Frank Emmert-Streib. 2014.  NetBioV: an R package for visualizing large network data in biology and medicine.  _Bioinformatics_ 30, 19 (2014), 2834–2836.
  * van Ham and Perer (2009) Frank van Ham and Adam Perer. 2009.  ”Show Context, Expand on Demand”: Supporting Large Graph Exploration with Degree-of-Interest.  _IEEE Transactions on Visualization and Computer Graphics_ 15, 6 (2009), 953–960.  https://doi.org/10.1109/TVCG.2009.108
  * van Ham and Rogowitz (2008) Frank van Ham and Bernice Rogowitz. 2008.  Perceptual organization in user-generated graph layouts.  _IEEE Transactions on Visualization and Computer Graphics_ 14, 6 (2008), 1333–1339.
  * Viégas et al. (2007) Fernanda B. Viégas, Martin Wattenberg, Frank van Ham, Jesse Kriss, and Matthew M. McKeon. 2007\.  ManyEyes: a Site for Visualization at Internet Scale.  _IEEE Trans. Vis. Comput. Graph._ 13, 6 (2007), 1121–1128.  https://doi.org/10.1109/TVCG.2007.70577
  * Von Ahn and Dabbish (2008) Luis Von Ahn and Laura Dabbish. 2008.  Designing games with a purpose.  _Commun. ACM_ 51, 8 (2008), 58–67.
  * von Ahn et al. (2006) Luis von Ahn, Ruoran Liu, and Manuel Blum. 2006.  Peekaboom: a game for locating objects in images. In _Proceedings of the 2006 Conference on Human Factors in Computing Systems, CHI 2006, Montréal, Québec, Canada, April 22-27, 2006_. ACM SIGCHI, 55–64.  https://doi.org/10.1145/1124772.1124782
  * Williams et al. (2016) Michael Williams, Hassen Gharbi, Aybike Ulusan, Özlem Ergun, Xiaofeng Zhu, Shiyu Zhang, and Casper Harteveld. 2016.  Toward Human in the Loop Optimization Through Game-Based Experiments. In _Proceedings of the 2016 Annual Symposium on Computer-Human Interaction in Play, Companion Extended Abstracts, CHI PLAY 2016, Austin, TX, USA, October 16 - 19, 2016_ , Anna L. Cox, Zachary O. Toups, Regan L. Mandryk, Paul A. Cairns, Vero Vanden Abeele, and Daniel M. Johnson (Eds.). ACM, 351–358.  https://doi.org/10.1145/2968120
  * Wongsuphasawat et al. (2016) Kanit Wongsuphasawat, Dominik Moritz, Anushka Anand, Jock D. Mackinlay, Bill Howe, and Jeffrey Heer. 2016.  Voyager: Exploratory Analysis via Faceted Browsing of Visualization Recommendations.  _IEEE Trans. Vis. Comput. Graph._ 22, 1 (2016), 649–658.  https://doi.org/10.1109/TVCG.2015.2467191
  * Yuan et al. (2012) Xiaoru Yuan, Limei Che, Yifan Hu, and Xin Zhang. 2012\.  Intelligent graph layout using many users’ input.  _IEEE transactions on visualization and computer graphics_ 18, 12 (2012), 2699–2708.
  * Zhang et al. (2012) Haoqi Zhang, Edith Law, Rob Miller, Krzysztof Gajos, David Parkes, and Eric Horvitz. 2012\.  Human computation tasks with global constraints. In _Proceedings of the 2012 ACM annual conference on Human Factors in Computing Systems_ _(CHI ’12)_. ACM, 217–226.  https://doi.org/10.1145/2207676.2207708

## Appendix

##  1\. How we compute per-criterion scores?

To prevent pathological layouts that move nodes indiscriminately far apart
from each other, we set the per-criterion scores to zero if any node is moved
outside a bounding box of fixed page width $w$ and height $h$. We chose
$w=5000$ and $h=6000$ in our implementation. The aspect ratio of our bounding
box approximately matches that of a page in a scientific journal, i.e., $0.8$.

  1. (1)

_Downward pointing paths_ : We count the number of downward-pointing paths in
a layout using a dynamic program that runs in time linear in the number of
edges in the network. Note that this algorithm does not assign node positions
in order to maximize the number of downward-pointing paths since this task
will be undertaken by Flud players. The subgraph composed only of downward-
pointing edges is acyclic. Hence, for any node $v$ in the network, we can
compute $\pi(v)$, the number of downward-pointing paths that start at $v$
using the following recurrence:

$\pi(v)=\sum\limits_{\begin{subarray}{c}(v,u)\text{ is}\\\ downward\\\
pointing\end{subarray}}\pi(u)$

Here, the sum is taken only over outgoing neighbors of $v$ that have smaller
$y$-coordinate than $u$, i.e., if the edge $(v,u)$ is pointing downward. The
base case is a node $v$ that has no downward-pointing edges leaving it:
$\pi(v)=0$ in this case. We can compute the total number $\pi(G)$ of downward-
pointing paths in the graph by summing $\pi(v)$ over all nodes $v$ that have
no downward-pointing edges entering them. Note the maximum possible value of
$\pi(G)$ is the number of paths (all directed paths, not just downward-
pointing ones) in $G$. We count this number $\rho(G)$ using a depth-first
search based algorithm. Although this algorithm has worst-case running time
that is exponential in the graph size, it was very efficient in our
experiments. Finally, we compute a normalized _downward pointing_ score as
follows:

$\mathit{DP}(G)=\frac{\pi(G)}{\rho(G)}.$

  2. (2)

_Non-crossing edge pairs_ : We count the number $\chi(G)$ of edge pairs that
do not cross by checking for each pair of edges whether they intersect or not.
Since the maximum number of edge crossings possible in $G$ is $m(m-1)/2$, we
compute the _non-crossing edge pairs score_ as

$\mathit{EC}(G)=\frac{2\chi(G)}{m(m-1)}.$

  3. (3)

_Edge length_ : A trivial but undesirable solution that satisfies this
criterion is to place all nodes at the same location. Note that such a layout
may have a high score despite the node distribution constraint (described
next) because of the per-criterion priorities. Therefore, we require every
edge to have a minimum fixed length (300 pixels, in our implementation). We
now define the cost $c(e)$ of an edge to be equal to its length $l(e)$ if
$l(e)\geq 300$ or equal to a large number (say, $10,000$), otherwise. We
normalize the cost of each edge by the largest possible edge length (a
diagonal of the screen) and compute the _edge length score_ of a layout as

$\mathit{EL}(G)=\max\Big{\\{}0,1-\frac{1}{m}\sum_{e\in
E}\frac{c(e)}{\sqrt{w^{2}+h^{2}}}\Big{\\}}$

where $w$ and $h$ represent the width and height of the bounding box,
respectively.

  4. (4)

_Node edge separation_ : To evaluate the fidelity of a layout to this
aesthetic criterion, we compute the distance $d(v,e)$ between every node $v$
and every edge $e$ in $G$ as follows: we check if the projection of $v$ into
the line containing $e$ falls within $e$. If it does, $d(v,e)$ is the distance
between $v$ and this projection. Otherwise, $d(v,e)$ is the distance from $v$
to the endpoint of $e$ that is closer to $v$. With these values in hand, we
define the _node edge separation score_ as

$\mathit{NED}(G)=\frac{1}{n}{\sum}\limits_{u\in
V}\frac{\min\limits_{\begin{subarray}{c}e=\\{t,v\\}\in E\\\ u\neq t\neq
v\end{subarray}}d(u,e)}{\sqrt{w^{2}+h^{2}}}$

where $w$ and $h$ represent the width and height of the bounding box,
respectively.

##  2\. Fine-tuning procedure

At the end of the sequence, we fine-tuned the best layout so far to generate
the final output layout by using it as the input to simulated annealing with a
small value of the initial temperature ($T_{0}=10$). Due to the low initial
temperature, the random moves are “local,” i.e., a node can move only to
nearby position. Additionally, we did not accept moves that decrease the
score. We expected fine tuning to improve the distance-based components of the
layout scores without dramatically affecting the components for downward
pointing paths and edge crossings. In their work on incremental improvement of
layouts of planar networks, Harel and Sardas (Harel and Sardas, 1995)
concluded that when applied to a preprocessed network, fine-tuning can yield
significant improvements over simulated annealing without any preprocessing.
This work serves as an inspiration for us to use fine-tuning as a way to make
local moves that improve a player’s layout.

##  3\. Supplementary Figures

Figure A1. Distributions of the EC scores of layouts created by different
approaches. CROWD-SAX corresponds to the hybrid approach where crowd workers
and SAX (say SA20) iteratively improve upon one another’s results. Figure A2.
Distributions of the EL scores of layouts created by different approaches.
CROWD-SAX corresponds to the hybrid approach where crowd workers and SAX (say
SA20) iteratively improve upon one another’s results. Figure A3. Distributions
of the ND scores of layouts created by different approaches. CROWD-SAX
corresponds to the hybrid approach where crowd workers and SAX (say SA20)
iteratively improve upon one another’s results. Figure A4. Distributions of
the NED scores of layouts created by different approaches. CROWD-SAX
corresponds to the hybrid approach where crowd workers and SAX (say SA20)
iteratively improve upon one another’s results. Figure A5.  Plots showing the
rate at which each approach improved the overall layout score. Each row
corresponds to a network and shows the time taken by different approaches to
increase the total layout score. The $x$-axis represents the time taken in
hours to reach a particular score and the $y$-axis represents the score. The
circle and square markers correspond to crowd workers and simulated annealing
respectively.

G1G2G3 Figure A6.  Each row corresponds to a network. Each row shows the time
taken by three game sequences of different approaches to increase the total
layout score. The $x$-axis represents the time taken in hours to reach a
particular score and the $y$-axis represents the score. The circle and square
markers correspond to crowd workers and simulated annealing respectively.

(a) Crowd approach.

(b) Dig-Cola.

(c) SA.

(d) Spring Electrical Model.

Figure A7. Best layouts generated by Crowd and baseline methods for network
G3. Green and yellow colored nodes represent the source and target nodes,
respectively. The upward pointing edges are shown in red whereas downward
pointing edges are shown in blue color.