Tasks Taxonomy for Graphs: Difference between revisions

From InfoVis:Wiki
Jump to navigation Jump to search
mNo edit summary
m (Reverted edits by 94.23.1.18 (Talk); changed back to last version by Markus)
 
(5 intermediate revisions by 4 users not shown)
Line 1: Line 1:
[http://wc1.worldcrossing.com/WebX/.1de60a1a free mtv ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=109&forum=13 cheap levitra] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=127&forum=13 pharmacy online online] [http://www.psfc.mit.edu/~jinseok/bbse/view.php?id=presentations&no=361 free real ringtones] [http://wc1.worldcrossing.com/WebX/.1de609df cheap ambien] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=98&forum=13 cheap diethylpropion] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=158&forum=13 cheap xanax] [http://news.engin.brown.edu/forums/thread-view.asp?tid=172 lorazepam] [http://wc1.worldcrossing.com/WebX/.1de609ff real ringtones] [http://news.engin.brown.edu/forums/thread-view.asp?tid=220 free punk ringtones] [http://wc1.worldcrossing.com/WebX/.1de609dc albuterol online] [http://wc1.worldcrossing.com/WebX/.1de60a2e xanax online] [http://news.engin.brown.edu/forums/thread-view.asp?tid=156 fioricet] [http://wc1.worldcrossing.com/WebX/.1de60a10 cheap didrex] [http://wc1.worldcrossing.com/WebX/.1de60a35 verizon ringtones] [http://news.engin.brown.edu/forums/thread-view.asp?tid=176 buy ultracet] [http://www.psfc.mit.edu/~jinseok/bbse/view.php?id=presentations&no=356 free tracfone ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=92&forum=13 clomid online] [http://www.psfc.mit.edu/~jinseok/bbse/view.php?id=presentations&no=344 ativan] [http://news.engin.brown.edu/forums/thread-view.asp?tid=155 buy xanax] [http://news.engin.brown.edu/forums/thread-view.asp?tid=178 buy nexium] [http://wc1.worldcrossing.com/WebX/.1de60a04 free sonyericsson ringtones] [http://news.engin.brown.edu/forums/thread-view.asp?tid=182 cheap clomid] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=82&forum=13 cheap adipex] [http://www.psfc.mit.edu/~jinseok/bbse/view.php?id=presentations&no=343 cialis online] [http://news.engin.brown.edu/forums/thread-view.asp?tid=170 hydrocodone online] [http://news.engin.brown.edu/forums/thread-view.asp?tid=169 cheap levitra] [http://wc1.worldcrossing.com/WebX/.1de609f3 midi ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=111&forum=13 order lisinopril] [http://news.engin.brown.edu/forums/thread-view.asp?tid=224 free wwe ringtones] [http://news.engin.brown.edu/forums/thread-view.asp?tid=153 cheap phentermine] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=147&forum=13 tracfone ringtones] [http://news.engin.brown.edu/forums/thread-view.asp?tid=181 cheap sildenafil] [http://news.engin.brown.edu/forums/thread-view.asp?tid=212 verizon ringtones] [http://news.engin.brown.edu/forums/thread-view.asp?tid=223 free midi ringtones] [http://www.psfc.mit.edu/~jinseok/bbse/view.php?id=presentations&no=335 buy phentermine] [http://wc1.worldcrossing.com/WebX/.1de60a00 cheap rivotril] [http://wc1.worldcrossing.com/WebX/.1de60a0a vicodin] [http://news.engin.brown.edu/forums/thread-view.asp?tid=187 celexa online] [http://wc1.worldcrossing.com/WebX/.1de609eb free funny ringtones] [http://news.engin.brown.edu/forums/thread-view.asp?tid=197 cheap flexeril] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=105&forum=13 cheap hoodia] [http://news.engin.brown.edu/forums/thread-view.asp?tid=188 cheap tenuate] [http://news.engin.brown.edu/forums/thread-view.asp?tid=180 buy prozac] [http://wc1.worldcrossing.com/WebX/.1de60a05 free sprint ringtones] [http://wc1.worldcrossing.com/WebX/.1de609f9 norco online] [http://wc1.worldcrossing.com/WebX/.1de609f2 meridia] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=145&forum=13 sprint ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=96&forum=13 buy diazepam] [http://www.psfc.mit.edu/~jinseok/bbse/view.php?id=presentations&no=338 fioricet online] [http://www.psfc.mit.edu/~jinseok/bbse/view.php?id=presentations&no=358 mp3 ringtones] [http://wc1.worldcrossing.com/WebX/.1de60a21 paxil online] [http://wc1.worldcrossing.com/WebX/.1de60a31 buy zanaflex] [http://wc1.worldcrossing.com/WebX/.1de609de but alprazolam] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=141&forum=13 soma online] [http://www.psfc.mit.edu/~jinseok/bbse/view.php?id=presentations&no=342 cheap diazepam] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=157&forum=13 free wwe ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=161&forum=13 zoloft] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=112&forum=13 lorazepam online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=124&forum=13 online norco] [http://www.psfc.mit.edu/~jinseok/bbse/view.php?id=presentations&no=355 free free ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=88&forum=13 carisoprodol online] [http://www.psfc.mit.edu/~jinseok/bbse/view.php?id=presentations&no=360 qwest ringtones] [http://news.engin.brown.edu/forums/thread-view.asp?tid=167 clonazepam online] [http://wc1.worldcrossing.com/WebX/.1de60a0e cheap celexa] [http://wc1.worldcrossing.com/WebX/.1de609e4 cheap clonazepam] [http://wc1.worldcrossing.com/WebX/.1de60a17 buy lipitor] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=123&forum=13 free nokia ringtones] [http://news.engin.brown.edu/forums/thread-view.asp?tid=184 lisinopril online] [http://wc1.worldcrossing.com/WebX/.1de60a24 cheap propecia] [http://wc1.worldcrossing.com/WebX/.1de609f8 nokia ringtones] [http://wc1.worldcrossing.com/WebX/.1de609fd free punk ringtones] [http://news.engin.brown.edu/forums/thread-view.asp?tid=154 buy carisoprodol] [http://www.psfc.mit.edu/~jinseok/bbse/view.php?id=presentations&no=339 cheap ultram] [http://wc1.worldcrossing.com/WebX/.1de60a34 free sony ericsson ringtones] [http://news.engin.brown.edu/forums/thread-view.asp?tid=202 tracfone ringtones] [http://news.engin.brown.edu/forums/thread-view.asp?tid=199 cheap zyban] [http://news.engin.brown.edu/forums/thread-view.asp?tid=198 hoodia online] [http://www.psfc.mit.edu/~jinseok/bbse/view.php?id=presentations&no=332 tramadol online] [http://wc1.worldcrossing.com/WebX/.1de60a1d cingular ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=107&forum=13 free jazz ringtones] [http://news.engin.brown.edu/forums/thread-view.asp?tid=219 free alltel ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=101&forum=13 but flexeril] [http://www.psfc.mit.edu/~jinseok/bbse/view.php?id=presentations&no=359 nextel ringtones] [http://wc1.worldcrossing.com/WebX/.1de60a15 free kyocera ringtones] [http://www.psfc.mit.edu/~jinseok/bbse/view.php?id=presentations&no=363 free samsung ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=117&forum=13 motorola ringtones] [http://www.psfc.mit.edu/~jinseok/bbse/view.php?id=presentations&no=346 meridia online] [http://wc1.worldcrossing.com/WebX/.1de60a30 cheap xenical] [http://wc1.worldcrossing.com/WebX/.1de60a03 sony ringtones] [http://news.engin.brown.edu/forums/thread-view.asp?tid=168 cheap paxil] [http://wc1.worldcrossing.com/WebX/.1de60a01 free sagem ringtones] [http://news.engin.brown.edu/forums/thread-view.asp?tid=160 ativan online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=136&forum=13 rivotril online] [http://wc1.worldcrossing.com/WebX/.1de609fb ortho online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=89&forum=13 celexa online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=139&forum=13 free sharp ringtones] [http://news.engin.brown.edu/forums/thread-view.asp?tid=163 adipex online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=125&forum=13 cheap ortho] [http://wc1.worldcrossing.com/WebX/.1de609ee hydrocodone] [http://news.engin.brown.edu/forums/thread-view.asp?tid=177 cheap propecia] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=91&forum=13 cingular ringtones] [http://wc1.worldcrossing.com/WebX/.1de609f7 nextel ringtones] [http://news.engin.brown.edu/forums/thread-view.asp?tid=215 free sagem ringtones] [http://www.psfc.mit.edu/~jinseok/bbse/view.php?id=presentations&no=347 adipex] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=132&forum=13 punk ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=97&forum=13 didrex online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=144&forum=13 free sonyericsson ringtones] [http://news.engin.brown.edu/forums/thread-view.asp?tid=179 cheap didrex] [http://news.engin.brown.edu/forums/thread-view.asp?tid=158 cheap diazepam] [http://wc1.worldcrossing.com/WebX/.1de60a25 free samsung ringtones] [http://wc1.worldcrossing.com/WebX/.1de60a26 sharp ringtones] [http://news.engin.brown.edu/forums/thread-view.asp?tid=162 order meridia] [http://news.engin.brown.edu/forums/thread-view.asp?tid=217 free mono ringtones] [http://news.engin.brown.edu/forums/thread-view.asp?tid=152 valium online] [http://wc1.worldcrossing.com/WebX/.1de609ec buy hgh] [http://news.engin.brown.edu/forums/thread-view.asp?tid=205 nextel ringtones] [http://www.psfc.mit.edu/~jinseok/bbse/view.php?id=presentations&no=357 free funny ringtones] [http://news.engin.brown.edu/forums/thread-view.asp?tid=191 cheap lortab] [http://wc1.worldcrossing.com/WebX/.1de60a2b but ultracet] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=153&forum=13 viagra online] [http://news.engin.brown.edu/forums/thread-view.asp?tid=183 albuterol] [http://www.psfc.mit.edu/~jinseok/bbse/view.php?id=presentations&no=349 cheap vicodin] [http://wc1.worldcrossing.com/WebX/.1de60a18 motorola ringtones] [http://wc1.worldcrossing.com/WebX/.1de609f0 lorazepam online] [http://wc1.worldcrossing.com/WebX/.1de60a12 free ericsson ringtones] [http://wc1.worldcrossing.com/WebX/.1de60a19 mp3 ringtones] [http://news.engin.brown.edu/forums/thread-view.asp?tid=216 free sonyericsson ringtones] [http://news.engin.brown.edu/forums/thread-view.asp?tid=161 viagra online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=95&forum=13 cyclobenzaprine online] [http://news.engin.brown.edu/forums/thread-view.asp?tid=192 but vigrx] [http://wc1.worldcrossing.com/WebX/.1de60a0d wwe ringtones] [http://news.engin.brown.edu/forums/thread-view.asp?tid=185 cheap zoloft] [http://wc1.worldcrossing.com/WebX/.1de609e3 clomid online] [http://wc1.worldcrossing.com/WebX/.1de60a13 fioricet online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=138&forum=13 samsung ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=83&forum=13 albuterol online] [http://wc1.worldcrossing.com/WebX/.1de60a29 buy tramadol] [http://news.engin.brown.edu/forums/thread-view.asp?tid=173 cheap xenical] [http://www.psfc.mit.edu/~jinseok/bbse/view.php?id=presentations&no=350 alprazolam] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=93&forum=13 clonazepam online] [http://news.engin.brown.edu/forums/thread-view.asp?tid=204 free mp3 ringtones] [http://news.engin.brown.edu/forums/thread-view.asp?tid=164 norco online] [http://www.psfc.mit.edu/~jinseok/bbse/view.php?id=presentations&no=337 xanax] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=119&forum=13 free mtv ringtones] [http://news.engin.brown.edu/forums/thread-view.asp?tid=206 free qwest ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=151&forum=13 valium] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=140&forum=13 cheap sildenafil] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=162&forum=13 cheap zyban] [http://news.engin.brown.edu/forums/thread-view.asp?tid=166 alprazolam online] [http://www.psfc.mit.edu/~jinseok/bbse/view.php?id=presentations&no=353 levitra] [http://www.psfc.mit.edu/~jinseok/bbse/view.php?id=presentations&no=333 cheap soma] [http://news.engin.brown.edu/forums/thread-view.asp?tid=189 ortho online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=159&forum=13 cheap xenical] [http://wc1.worldcrossing.com/WebX/.1de60a36 cheap zyban] [http://wc1.worldcrossing.com/WebX/.1de60a23 free polyphonic ringtones] [http://news.engin.brown.edu/forums/thread-view.asp?tid=208 motorola ringtones] [http://wc1.worldcrossing.com/WebX/.1de60a1f cheap lisinopril] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=137&forum=13 free sagem ringtones] [http://wc1.worldcrossing.com/WebX/.1de60a1b free music ringtones] [http://wc1.worldcrossing.com/WebX/.1de609e0 cheap ativan] [http://news.engin.brown.edu/forums/thread-view.asp?tid=229 free jazz ringtones] [http://wc1.worldcrossing.com/WebX/.1de609e5 free cool ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=99&forum=13 free ericsson ringtones] [http://wc1.worldcrossing.com/WebX/.1de60a07 tracfone ringtones] [http://www.psfc.mit.edu/~jinseok/bbse/view.php?id=presentations&no=348 cheap norco] [http://wc1.worldcrossing.com/WebX/.1de60a09 cheap viagra] [http://news.engin.brown.edu/forums/thread-view.asp?tid=218 free sony ericsson ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=121&forum=13 nexium online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=126&forum=13 cheap paxil] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=94&forum=13 free cool ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=154&forum=13 vicodin online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=108&forum=13 free kyocera ringtones] [http://wc1.worldcrossing.com/WebX/.1de60a14 free jazz ringtones] [http://news.engin.brown.edu/forums/thread-view.asp?tid=210 sprint ringtones] [http://wc1.worldcrossing.com/WebX/.1de60a0f cialis online] [http://news.engin.brown.edu/forums/thread-view.asp?tid=175 cyclobenzaprine online] [http://news.engin.brown.edu/forums/thread-view.asp?tid=200 free nokia ringtones] [http://www.psfc.mit.edu/~jinseok/bbse/view.php?id=presentations&no=352 cheap paxil] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=110&forum=13 lipitor online] [http://wc1.worldcrossing.com/WebX/.1de609e6 buy cyclobenzaprine] [http://wc1.worldcrossing.com/WebX/.1de60a33 cheap prozac] [http://news.engin.brown.edu/forums/thread-view.asp?tid=157 cheap ultram] [http://news.engin.brown.edu/forums/thread-view.asp?tid=190 pharmacy online online] [http://news.engin.brown.edu/forums/thread-view.asp?tid=195 cheap rivotril] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=143&forum=13 free sony ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=100&forum=13 fioricet online] [http://wc1.worldcrossing.com/WebX/.1de60a06 tenuate online] [http://www.psfc.mit.edu/~jinseok/bbse/view.php?id=presentations&no=345 viagra online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=135&forum=13 real ringtones] [http://news.engin.brown.edu/forums/thread-view.asp?tid=193 zanaflex online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=115&forum=13 midi ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=87&forum=13 cheap ativan] [http://www.psfc.mit.edu/~jinseok/bbse/view.php?id=presentations&no=351 clonazepam online] [http://wc1.worldcrossing.com/WebX/.1de60a11 diethylpropion online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=152&forum=13 free verizon ringtones] [http://wc1.worldcrossing.com/WebX/.1de609ea free ringtones] [http://wc1.worldcrossing.com/WebX/.1de609fa online pharmacy] [http://news.engin.brown.edu/forums/thread-view.asp?tid=151 order soma] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=102&forum=13 free free ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic
== Low-Level Tasks ==
 
From [Amar et al. 2005] and [Lee et al 2006].
 
* General Tasks
{|border="1"
|-
|'''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
{|border="1"
|-
|'''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 ===
 
{| border="1"
|-
|'''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?
|}
 
=== Attribute-based Tasks ===
 
{| border="1"
|-
|'''Task'''||'''Description''' || '''Examples'''
|-
| On the Nodes
|
* Find the nodes having a specific attribute value.
* Review the set of nodes.
||
*(FOAF)  Who do you know from the people currently shown on screen?
*(FOAF)  How many people do you know from the ones currently shown on screen?
*(FOAF)  Are there any foreign-sounding names?
|-
| On the Links
|
* Given a node, find the nodes connected only by certain types of links.
* Which node is connected by a link having the largest/smallest value?
||
*(GO)  Find the nodes connected by “is-a” relationships from the “Biological Process” node.
*(FW)  If a link has an attribute representing the percentage of the diet, what is main food of American crow?
|}
 
=== Browsing Tasks ===
{| border="1"
|-
|'''Task'''||'''Description''' || '''Examples'''
|-
| Follow Path
|
* Follow a given path
||
* (FOAF) A user looks into A’s friend B, B’s friend C, and C’s friend D.
* (FW) Follow the flow of energy from grasses, to a rabbit that eats grass, to a carnivore that eats the rabbit, and to a carnivore that eats that carnivore.
|-
| Revisit
|
* Return to a previously visited node.
||
*(FOAF) After they follow a path in the above task, they may want to see A’s other friends.
*(FW) Find another carnivore that eats the same rabbit.
|}
 
=== Overview Tasks ===
This is a compound exploratory task to get estimated values quickly. For example, we might ask users to estimate the size of the social network. Note that sometimes it is more important to be able to estimate the answer than to get an accurate one. Some of the topology tasks can be done easily using an overview of the graph as well. For example, using particular layout algorithms, it is easy to see whether or not there are clusters and connected components. Other algorithms help to find shortest paths between nodes. Overview also helps to find patterns.
 
Examples:
* estimate size of the network
* estimate the number of connected components
* is the network clustered?
* can you identify different patterns of connection?
* (FOAF) has the network a small-world structure?
 
== High-Level Tasks ==
 
High-Level tasks which are not a combination of lower level tasks.
 
* When we compare two or more food webs, we can ask the following questions: What do they have in common? What are the differences among those food webs? Is there any missing or conflicting information?
* Due to errors in the data, several nodes may represent the same entity. For example, the co-authorship graphs often have duplicate author nodes. One important task is to identify whether two or more nodes represent the same person.
* How has the graph changed over time?
 
== Other tasks ==
 
There seems to be a set of tasks in the world that match very few of these, but show up often. I welcome others' ideas of how to categorize them:
 
"what is the general structure of this graph?"
http://www.networkweaving.com/blog/2006/09/nola-networks.html
 
"what is the distribution of vertex degree in this graph?" (That is, "how are well-linked nodes different from under-linked nodes?")
http://research.microsoft.com/research/pubs/view.aspx?type=Publication&id=1601
 
"how many As are linked to Bs? How many As link to other As?"
http://www.crookedtimber.org/2005/05/25/cross-ideological-conversations-among-bloggers/  
 
I see things like this so often that they seem to dominate my understanding of how people think of graphing today. (Wattenberg obviously saw the same; his paper from CHI ’06 would do poorly on almost all of the tasks you discuss, but is incredibly effective for questions like “is Sales talking to Engineering?”)
 
 
== 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.

Latest revision as of 22:39, 4 June 2012

Low-Level Tasks[edit]

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[edit]

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[edit]

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?

Attribute-based Tasks[edit]

Task Description Examples
On the Nodes
  • Find the nodes having a specific attribute value.
  • Review the set of nodes.
  • (FOAF) Who do you know from the people currently shown on screen?
  • (FOAF) How many people do you know from the ones currently shown on screen?
  • (FOAF) Are there any foreign-sounding names?
On the Links
  • Given a node, find the nodes connected only by certain types of links.
  • Which node is connected by a link having the largest/smallest value?
  • (GO) Find the nodes connected by “is-a” relationships from the “Biological Process” node.
  • (FW) If a link has an attribute representing the percentage of the diet, what is main food of American crow?

Browsing Tasks[edit]

Task Description Examples
Follow Path
  • Follow a given path
  • (FOAF) A user looks into A’s friend B, B’s friend C, and C’s friend D.
  • (FW) Follow the flow of energy from grasses, to a rabbit that eats grass, to a carnivore that eats the rabbit, and to a carnivore that eats that carnivore.
Revisit
  • Return to a previously visited node.
  • (FOAF) After they follow a path in the above task, they may want to see A’s other friends.
  • (FW) Find another carnivore that eats the same rabbit.

Overview Tasks[edit]

This is a compound exploratory task to get estimated values quickly. For example, we might ask users to estimate the size of the social network. Note that sometimes it is more important to be able to estimate the answer than to get an accurate one. Some of the topology tasks can be done easily using an overview of the graph as well. For example, using particular layout algorithms, it is easy to see whether or not there are clusters and connected components. Other algorithms help to find shortest paths between nodes. Overview also helps to find patterns.

Examples:

  • estimate size of the network
  • estimate the number of connected components
  • is the network clustered?
  • can you identify different patterns of connection?
  • (FOAF) has the network a small-world structure?

High-Level Tasks[edit]

High-Level tasks which are not a combination of lower level tasks.

  • When we compare two or more food webs, we can ask the following questions: What do they have in common? What are the differences among those food webs? Is there any missing or conflicting information?
  • Due to errors in the data, several nodes may represent the same entity. For example, the co-authorship graphs often have duplicate author nodes. One important task is to identify whether two or more nodes represent the same person.
  • How has the graph changed over time?

Other tasks[edit]

There seems to be a set of tasks in the world that match very few of these, but show up often. I welcome others' ideas of how to categorize them:

"what is the general structure of this graph?" http://www.networkweaving.com/blog/2006/09/nola-networks.html

"what is the distribution of vertex degree in this graph?" (That is, "how are well-linked nodes different from under-linked nodes?") http://research.microsoft.com/research/pubs/view.aspx?type=Publication&id=1601

"how many As are linked to Bs? How many As link to other As?" http://www.crookedtimber.org/2005/05/25/cross-ideological-conversations-among-bloggers/

I see things like this so often that they seem to dominate my understanding of how people think of graphing today. (Wattenberg obviously saw the same; his paper from CHI ’06 would do poorly on almost all of the tasks you discuss, but is incredibly effective for questions like “is Sales talking to Engineering?”)


References[edit]

  • [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.