Tasks Taxonomy for Graphs

Low-Level Tasks

From [Amar et al. 2005] and [Lee et al 2006].

• General Tasks

Task	Description
Retrieve Value	Given a set of cases, find attributes of those cases.
Filter	Given some conditions on attributes values, find data cases satisfying those conditions.
Compute Derived Value	Given a set of data cases, compute an aggregate numeric representation of those data cases.(e.g. average, median, and count)
Find Extremum	Find data cases possessing an extreme value of an attribute over its range within the data set.
Sort	Given a set of data cases, rank them according to some ordinal metric. Determine Range Given a set of data cases and an attribute of interest, find the span of values within the set.
Characterize Distribution	Given a set of data cases and a quantitative attribute of interest, characterize the distribution of that attribute’s values over the set.
Find Anomalies	Identify any anomalies within a given set of data cases with respect to a given relationship or expectation, e.g. statistical outliers.
Cluster	Given a set of data cases, find clusters of similar attribute values.
Correlate	Given a set of data cases and two attributes, determine useful relationships between the values of those attributes.
Scan	Quickly review a set of items.
Set Operation	Given multiple sets of items, perform set operations on them. For example, find the intersection of the set of nodes.

• Graph Specific Tasks

Task	Description
Find Adjacent Nodes	Given a node, find its adjacent nodes.

Graph Task Taxonomy

Examples are illustrated using 4 types of graphs:

• (FOAF): friend-of-a-friend
• (FW): food web
• (GO): gene ontology
• (ARM): airport routing map

Topology-based Tasks

Task	Description	Examples
Adjacency (direct connection)	Find the set of nodes adjacent to a node? How many nodes are adjacent to a node? Which node has a maximum number of adjacent nodes?	(FOAF) Find the names of the direct friends of Eric. (FW) How many kinds of organisms do golden eagles eat? (FOAF) Who is the most popular person?
Accessibility (direct or indirect connection)	Find the set of nodes accessible from a node. How many nodes are accessible from a node? Find the set of nodes accessible from a node where the distance is less than or equal to n. How many nodes are accessible from a node where the distance is less than or equal to n?	(FOAF) Who are your friends, your friends’ friends, and so on? (FOAF) How many friends are you connected to in this way? (ARM) To what cities can we go from Seoul, Korea by changing planes only once?
Commmon Connection	Given nodes, find a set of nodes that are connected to all of them.	(FOAF)Find all the people who know both John and Jack.
Connectivty	Find the shortest path between two nodes. Identify clusters. Identify connected components. Find bridges. Find articulation points.	(ARM) What is the shortest path from Seoul, Korea to Athens, Greece? (FOAF) Count the number of clusters. (FW) There may be subgraphs independent of each other. Count the number of connected components in the graph. (FOAF) Who is the person whose removal from the graph results in an unconnected graph? (FW) Which is the eating link whose removal from the graph results in an unconnected graph?

References

• [Amar et al. 2005] Amar, R., Eagan, J., and Stasko, J. Low-Level Components of Analytic Activity in Information Visualization, Proceedings of the Symposium on Information Visualization (InfoVis ’05), pp. 111-117, 2005.

• [Lee et al. 2006] Lee, B., Plaisant, C., Parr, CS., Fekete, JD. and Henry, N. Task Taxonomy for Graph Visualization, In BEyond time and errors: novel evaLuation methods for Information Visualization (BELIV'06), Venice, Italy, May 2006, to be published.