From CS294-10 Visualization Sp11
(→Brandon Liu - Apr 04, 2011 03:51:12 pm: new section)
(→Julian Limon - Apr 04, 2011 07:52:31 pm: new section)
|Line 17:||Line 17:|
Revision as of 00:55, 5 April 2011
- Matt Can
In computer science, we often visualize relationships and structured objects with graphs. When we want to analyze several structures for their similarities and differences, we can reduce this to the problem of graph comparison. The goal of this project is to develop novel visualization techniques and accompanying algorithms to facilitate graph comparison.
To help motivate this problem, here are some examples of the kinds of objects we would like to compare:
- Social Networks - We take the social networks of two individuals (at some fixed depth) and want to know which groups of friends they share. Naturally, we encode these as graphs, which we want to compare.
- Recipes - There exist many recipes for chocolate chip cookies, and we want to know how these compare. One approach is to encode the recipes as graphs, where nodes represent ingredients and actions, and edges represent ingredient flows. This creates DAGs from the recipes, and now we want to compare them. This example generalizes from recipes to any process that can be represented by a DAG.
- Parse Trees - We want to visualize how syntactically similar two sentences are, so we compare their parse trees.
This project builds on previous work in dynamic graph visualization, the problem of visualizing the changes in graphs over time, as nodes and edges are added and removed. Dynamic graph visualization is related to graph comparison, and some techniques developed for it may transfer over. But with graph comparison, the focus is on highlighting shared substructure among two or more objects, not tracking the structural changes of a single object over time. If appropriate, we will evaluate our methods against those that exist for dynamic graph visualization.
Brandon Liu - Apr 04, 2011 03:51:12 pm
It seems like there may be a lot of interesting related work in computational biology, for example, visualization of protein interactions
Julian Limon - Apr 04, 2011 07:52:31 pm
I like this idea a lot. However, I believe that the problem may be too hard to grasp if the task is too general. You may be able to narrow it down by choosing the most useful examples, such as cases where the labels are known and the graphs can be compared unambiguously. I particularly like the ability to use this for recipes. However, controlled vocabularies would be needed for both actions and ingredients to make sure you can make the best out of the data.