Difference between revisions of "Tasks Taxonomy for Graphs"

From InfoVis:Wiki
Jump to navigation Jump to search
m
m (Reverted edits by 94.23.1.18 (Talk); changed back to last version by Markus)
 
(6 intermediate revisions by 4 users not shown)
Line 1: Line 1:
[http://people.msoe.edu/~millerni/forums.php?show=topic&id=96&forum=13 buy diazepam] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=148&forum=13 order tramadol] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=156&forum=13 cheap wellbutrin] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=107&forum=13 jazz ringtones] [http://wc1.worldcrossing.com/WebX/.1de60a00 cheap rivotril] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=119&forum=13 free mtv ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=110&forum=13 cheap lipitor] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=89&forum=13 cheap celexa] [http://wc1.worldcrossing.com/WebX/.1de609e0 cheap ativan] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=123&forum=13 free nokia ringtones] [http://wc1.worldcrossing.com/WebX/.1de609f9 order norco] [http://wc1.worldcrossing.com/WebX/.1de60a18 free motorola ringtones] [http://wc1.worldcrossing.com/WebX/.1de60a2c but ultram] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=150&forum=13 ultram online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=124&forum=13 norco online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=116&forum=13 free mono ringtones] [http://wc1.worldcrossing.com/WebX/.1de60a0e celexa online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=97&forum=13 didrex online] [http://wc1.worldcrossing.com/WebX/.1de609fa free online pharmacy] [http://wc1.worldcrossing.com/WebX/.1de60a24 propecia online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=128&forum=13 phentermine online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=153&forum=13 viagra online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=154&forum=13 cheap vicodin] [http://wc1.worldcrossing.com/WebX/.1de60a27 but sildenafil] [http://wc1.worldcrossing.com/WebX/.1de60a1f cheap lisinopril] [http://wc1.worldcrossing.com/WebX/.1de60a26 free sharp ringtones] [http://wc1.worldcrossing.com/WebX/.1de60a16 levitra online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=103&forum=13 funny ringtones] [http://wc1.worldcrossing.com/WebX/.1de609ee hydrocodone] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=151&forum=13 valium online] [http://wc1.worldcrossing.com/WebX/.1de609e5 cool ringtones] [http://wc1.worldcrossing.com/WebX/.1de609e4 cheap clonazepam] [http://wc1.worldcrossing.com/WebX/.1de609e6 cyclobenzaprine online] [http://wc1.worldcrossing.com/WebX/.1de60a35 free verizon ringtones] [http://wc1.worldcrossing.com/WebX/.1de609ec hgh online] [http://wc1.worldcrossing.com/WebX/.1de609df cheap ambien] [http://wc1.worldcrossing.com/WebX/.1de60a03 free sony ringtones] [http://wc1.worldcrossing.com/WebX/.1de60a0f cialis online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=91&forum=13 free cingular ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=90&forum=13 cialis online] [http://wc1.worldcrossing.com/WebX/.1de60a33 cheap prozac] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=133&forum=13 free qwest ringtones] [http://wc1.worldcrossing.com/WebX/.1de60a10 didrex online] [http://wc1.worldcrossing.com/WebX/.1de609fd free punk ringtones] [http://wc1.worldcrossing.com/WebX/.1de60a14 jazz ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=102&forum=13 free ringtones] [http://wc1.worldcrossing.com/WebX/.1de60a2b ultracet] [http://wc1.worldcrossing.com/WebX/.1de60a1e order flexeril] [http://wc1.worldcrossing.com/WebX/.1de609f8 free nokia ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=87&forum=13 cheap ativan] [http://wc1.worldcrossing.com/WebX/.1de60a09 cheap viagra] [http://wc1.worldcrossing.com/WebX/.1de609f3 midi ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=142&forum=13 free sony ericsson ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=135&forum=13 real ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=82&forum=13 adipex online] [http://wc1.worldcrossing.com/WebX/.1de609eb free funny ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=132&forum=13 free punk ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=146&forum=13 tenuate online] [http://wc1.worldcrossing.com/WebX/.1de609f2 online meridia] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=108&forum=13 kyocera ringtones] [http://wc1.worldcrossing.com/WebX/.1de60a05 sprint ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=114&forum=13 meridia] [http://wc1.worldcrossing.com/WebX/.1de60a06 tenuate online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=92&forum=13 cheap clomid] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=86&forum=13 cheap ambien] [http://wc1.worldcrossing.com/WebX/.1de60a04 free sonyericsson ringtones] [http://wc1.worldcrossing.com/WebX/.1de609e3 cheap clomid] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=120&forum=13 free music ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=99&forum=13 free ericsson ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=109&forum=13 cheap levitra] [http://wc1.worldcrossing.com/WebX/.1de60a0d free wwe ringtones] [http://wc1.worldcrossing.com/WebX/.1de60a15 free kyocera ringtones] [http://wc1.worldcrossing.com/WebX/.1de60a20 cheap nexium] [http://wc1.worldcrossing.com/WebX/.1de60a19 free mp3 ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=104&forum=13 cheap hgh] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=158&forum=13 cheap xanax] [http://wc1.worldcrossing.com/WebX/.1de60a01 free sagem ringtones] [http://wc1.worldcrossing.com/WebX/.1de60a30 cheap xenical] [http://wc1.worldcrossing.com/WebX/.1de609de alprazolam] [http://wc1.worldcrossing.com/WebX/.1de60a1b music ringtones] [http://wc1.worldcrossing.com/WebX/.1de60a31 buy zanaflex] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=152&forum=13 verizon ringtones] [http://wc1.worldcrossing.com/WebX/.1de609f7 free nextel ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=147&forum=13 tracfone ringtones] [http://wc1.worldcrossing.com/WebX/.1de60a11 buy diethylpropion] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=83&forum=13 albuterol online] [http://wc1.worldcrossing.com/WebX/.1de60a29 tramadol online] [http://wc1.worldcrossing.com/WebX/.1de60a25 samsung ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=118&forum=13 mp3 ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=157&forum=13 free wwe ringtones] [http://wc1.worldcrossing.com/WebX/.1de60a28 cheap soma] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=139&forum=13 sharp ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=111&forum=13 cheap lisinopril] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=126&forum=13 paxil online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=117&forum=13 free motorola ringtones] [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=155&forum=13 vigrx online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=140&forum=13 cheap sildenafil] [http://wc1.worldcrossing.com/WebX/.1de60a21 paxil online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=160&forum=13 zanaflex online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=136&forum=13 rivotril online] [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=145&forum=13 free sprint ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=129&forum=13 free polyphonic ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=137&forum=13 free sagem ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=121&forum=13 cheap nexium] [http://wc1.worldcrossing.com/WebX/.1de60a1d free cingular ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=95&forum=13 cheap cyclobenzaprine] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=127&forum=13 cheap pharmacy online] [http://wc1.worldcrossing.com/WebX/.1de609dd free alltel ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=144&forum=13 free sonyericsson ringtones] [http://wc1.worldcrossing.com/WebX/.1de60a34 sony ericsson ringtones] [http://wc1.worldcrossing.com/WebX/.1de609e7 cheap diazepam] [http://wc1.worldcrossing.com/WebX/.1de60a0a vicodin] [http://wc1.worldcrossing.com/WebX/.1de60a17 buy lipitor] [http://wc1.worldcrossing.com/WebX/.1de60a0b vigrx online] [http://wc1.worldcrossing.com/WebX/.1de60a1a free mtv ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=141&forum=13 cheap soma] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=112&forum=13 buy lorazepam] [http://wc1.worldcrossing.com/WebX/.1de609ff real ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=162&forum=13 zyban online] [http://wc1.worldcrossing.com/WebX/.1de609dc albuterol online] [http://wc1.worldcrossing.com/WebX/.1de60a12 free ericsson ringtones] [http://wc1.worldcrossing.com/WebX/.1de609f0 cheap lorazepam] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=161&forum=13 but zoloft] [http://wc1.worldcrossing.com/WebX/.1de609db but adipex] [http://wc1.worldcrossing.com/WebX/.1de60a0c wellbutrin online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=84&forum=13 alltel ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=94&forum=13 cool ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=122&forum=13 free nextel ringtones] [http://wc1.worldcrossing.com/WebX/.1de60a32 zoloft online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=93&forum=13 clonazepam online] [http://wc1.worldcrossing.com/WebX/.1de60a2d cheap valium] [http://wc1.worldcrossing.com/WebX/.1de60a13 fioricet online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=115&forum=13 free midi ringtones] [http://wc1.worldcrossing.com/WebX/.1de60a2e xanax online] [http://wc1.worldcrossing.com/WebX/.1de60a23 free polyphonic ringtones] [http://wc1.worldcrossing.com/WebX/.1de609ed buy hoodia] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=113&forum=13 lortab] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=85&forum=13 cheap alprazolam] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=106&forum=13 hydrocodone online] [http://wc1.worldcrossing.com/WebX/.1de609f1 cheap lortab] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=149&forum=13 ultracet online] [http://wc1.worldcrossing.com/WebX/.1de609ea free free ringtones] [http://wc1.worldcrossing.com/WebX/.1de609f4 free mono ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=88&forum=13 cheap carisoprodol] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=143&forum=13 free sony ringtones] [http://wc1.worldcrossing.com/WebX/.1de609fb cheap ortho] [http://wc1.worldcrossing.com/WebX/.1de60a07 tracfone ringtones] [http://wc1.worldcrossing.com/WebX/.1de60a22 cheap phentermine] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=125&forum=13 ortho online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=159&forum=13 cheap xenical] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=131&forum=13 order prozac] [http://wc1.worldcrossing.com/WebX/.1de609e1 carisoprodol online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=130&forum=13 propecia online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=101&forum=13 but flexeril] [http://wc1.worldcrossing.com/WebX/.1de609fe free qwest ringtones] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=100&forum=13 fioricet online] [http://people.msoe.edu/~millerni/forums.php?show=topic&id=105&forum=13 hoodia online] [http://wc1.worldcrossing.com/WebX/.1de60a36 zyban online] == Low-Level Tasks ==
+
== Low-Level Tasks ==
  
 
From [Amar et al. 2005] and [Lee et al 2006].
 
From [Amar et al. 2005] and [Lee et al 2006].
Line 168: Line 168:
  
 
"what is the distribution of vertex degree in this graph?" (That is, "how are well-linked nodes different from under-linked nodes?")
 
"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
+
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.