Contest webpage: http://www.cs.ubc.ca/~tmm/papers/contest04

Authors and Affiliations:

• Maylis Delest, LaBRI, Universite de Bordeaux I, maylis \at labri.fr
• Tamara Munzner, Department of Computer Science, University of British Columbia tmm \at cs.ubc.ca
• David Auber, LaBRI, Universite de Bordeaux I auber \at labri.fr
• Jean-Philippe Domenger, LaBRI, Universite de Bordeaux I domenger \at labri.fr

Tool(s):

Tulip - A Huge Graph Visualization Framework

David Auber

Graph Drawing Software, Springer-Verlag, Mathematics and Visualization series, Petra Mutzel and Michael Jünger, pages 105-126, 2003

ISBN: 3-540-00881-0

Strahler based graph clustering using convolution

David Auber, Maylis Delest, and Yves Chiricota

8th International IEEE Conference, Information Visualisation, London, 2004

Multiscale Visualization of Small World Networks

David Auber, Yves Chiricota, Fabien Jourdan, and Guy Melançon

InfoVis'03, 2003, pages 75-81

Using Strahler numbers for real time visual exploration of huge graphs

David Auber

International Conference on Computer Vision and Graphics 2002, pages 56-69

TASK 1: Static Overview of 10 years of Infovis

1. InfoVis Evolution Over Time
   • Process: See InfoVis Evolution over Time Task.
   • Image 1.1 :
     
   • Insight:
     See InfoVis Evolution over Time Task.
   • Caption for exhibit:
     We show the evolution of the interconnections between InfoVis authors and papers, including coauthorship and cocitation. Papers are white, and authors are colored by how many InfoVis papers they wrote.

2. InfoVis Papers and Authors
   • Process: See InfoVis Evolution over Time Task.
   • Image 1.2 :
     
   • Insight:
     See InfoVis Evolution over Time Task.
   • Caption for exhibit:
     We show the interconnections between InfoVis authors and papers, including coauthorship and cocitation. Papers are white, and authors are colored by how many InfoVis papers they wrote.

3. InfoVis Papers and Conferences
   • Process: See InfoVis Authors and Conferences Overview Task.
   • Image 1.3 :
     
   • Insight:
     See InfoVis Authors and Conferences Overview Task.
   • Caption for exhibit:
     We show the interconnections between authors and conferences in the field of information visualization. cocitation. Authors are colored blue, and with conferences in green.

TASK 2: Characterize the research areas and their evolution

1. Comparing Metrics
   • Process:
     
     • Data: all papers
     • Selection: delete authors and conferences
     • Color: rainbow colormap (yellow low, red high). Stahler metric (1,3-4); citation count (2)
   • Images:
     
   • Insight:
     We use the Strahler metric extensively in this submission, and begin by comparing it to the more obvious metric of citation count. We first show the set of all papers colored by the Strahler metric, then colored by the number of citations to papers. The Strahler metric takes into account the global branching structure of the dataset, whereas finding the citation count is a simply local computation at each node. For each node in the graph, we compute the branching of the DFS spanning directed acyclic graph (DAG) and the number of nested cycles induced by edges that are not in the spanning DAG. Notice that the Strahler view includes all of the features available in the simpler citation count view, and also conveys more structural information: for instance, the cyan edges in the upper left of the central component and the additional red edges within it. We next show a closeup view of the two red nodes in the center, which are the papers Generalized Fisheye Views (Furnas) and Cone Trees (Card, Mackinlay, and Robertson). Finally, we zoom in to show that the next highest ranking node, in blue, is Tufte's first book. As we discuss in more detail in the other subtasks, these three publications are very central.

2. Evolution over Time: All Papers

   • Process:
     
     • Data: authors and papers
     • Plugin: Create coauthorship edges linking authors who write papers together and cocitation edges between authors who cite each other.
     • Color: papers white, authors colored in rainbow by the "longevity" metric (number of years between first and last publications).
   • Images:
     
   
   • Insight:
     This sequence shows the evolution of the set of all papers. From 1988 to 1995, we show all of the data. We see that Tufte's and Cleveland's books begin to accrete a core component of infovis-related work. From 1995-1999 we show only the first of two clusters, where we separate the papers from the authors in order to control clutter. We also show a 2002 image where we have applied the clustering once more recursively, which allows us to see more structure in this subset of the data.

3. Evolution over Time: InfoVis papers only

   • Process:
     • Data: InfoVis authors and papers only
     • Plugin: Start with dataset above that includes coauthorship and cocitation links, and extract only InfoVis authors and papers. Specifically, find InfoVis conferences, follow links to all papers published there, then follow links to all authors of those papers. Then, delete conferences.
     • Selection: For each frame, select all papers published after year in question and delete them. (Always show all InfoVis authors.)
     • Color: papers white, authors colored by the "prolificness" metric (number of publications, in InfoVis) in rainbow.
   • Images:
     
   • Insight:
     In 1995, there is of course no cocitation between InfoVis papers. We see that in 1996 a few cocitations appear, with the largest connected component around Themescapes and Galaxies. This central core grows much larger in 1997, retaining the Themescapes paper at its heart, with only a few scattered cocitations that are disconnected from it. This pattern continues in later years, with the intercitation connection structure in the central core growing more complex. In the final year of 2002, only 20 papers drawn around the periphery are completely disconnected from any other InfoVis paper, and a 21st connected component near the bottom, with the label of Alan MacEachren visible, shows connections between three geographic visualization papers.

4. Top Topics and Authors
   • Process:
     • Data: authors, conferences, and papers
     • Color: "longevity" metric (length of time between first and last published paper), rainbow colormap with yellow low to red high
     • Clustering: Convolution with Strahler metric
     We clustered the dataset separately year by year from 1995-2002, using Strahler convolution. We found that the clustering was remarkably stable as the years progressed: in all but one year there were five clusters, and many of these clusters were identical for several years in a row.

   • Images:
     
     • Top Cluster: 95-97, 00, 98-99/01-02
       

     • Second Cluster: 95-97, 98/00-02, 99
       

     • Third Cluster: 95-97, 98, 99, 01, 02
       

     • Fourth Cluster 95, 96, 97, 98, 99-01, 02
       

     • Fifth Cluster 95, ...
       

   • Insight:
     

     • Focus+Context: the very top cluster grew from the Furnas Generalized Fisheye Views paper in 95-97. The early F+C work (Cone Trees, Perspective Wall) from PARC (Card, Mackinlay, and Robertson) was 3rd ranked then, and moved into the top cluster from 98-02. The Rubber Sheet paper by Sarkar and Brown is a 4th ranked component in 97 that dramatically expands into a large 4th ranked group in 1998, and moves into a large 3rd place clump for 99-02 that includes dynamic queries and treemaps (Shneiderman).

     • Tufte: Tufte's first book rises from being 4th ranked in 95-97 to being 2nd in 98-02, and for three of those years it is the only item at the 2nd rank.

     • PARC: The Cognitive Coprocessor paper by Card, Mackinlay, and Robertson was 2nd in 95-97 and in the top cluster from 98-02. Sensemaking papers were a 4th ranked component in 99-01. And, of course, all but one of the first-ranked F+C papers above are also from PARC.

     • Bell Labs: 4th rank components grow around Cleveland and Becker's work on statistical graphics and brushing from 98-02.

     • High dimensionality: the Worlds within Worlds paper by Feiner and Beshers was 3rd in 98. Several systems for exploring high-dimensional data (Bead from Chalmers, InfoCrystal by Spoerri, n-vision by XXX) formed a component that grew around the PNNL Wise {\it et al.} Themescapes/Galaxies paper from 99-02. Many of these papers explicitly dealt with the application domain of document corpora.

     • Dynamic Queries: these papers from Shneiderman {\it et al.} at the Univ. of Maryland papers were a 4th ranked component in 96-97, a 3rd ranked component in 98, both 2nd and 3rd ranked components in 99, and part of the large 3rd ranked group in 01-02 (which included F+C and ZUIs).

     • Zoomable User Interfaces: Pad/Pad++/EditWear by Bederson et al., along with the Toolglass interaction paper from Beier and Stone from PARC and a graphics paper by Clark, were a 4th ranked clump in 98, 00, and 02.

     • Everything Else: everything else was relegated to the last cluster. We only show this for 1995 to give a sense of scale, because the graph is too cluttered to use for noticing individual topics.

TASK 3: The people in InfoVis

1. Previous Answers See Tasks Task 2.1 and Task 2.2 for a combined answer.

2. Focusing on a Single Author: Raw Dataset
   • Process:
     
     • Data: authors and papers and conferences
     • Color: number of citations, with rainbow mapping
     • Layout: circular (1), hierarchical (2)
   • Images:
     

   • Insight:
     In all of our other examples we described our actions at a relatively high level. In this case, we will give the full details of the interaction that the user would do in order to replicate these pictures.

     We pick a single author to investigate, in this case George Robertson. First, we interactively select that node by hitting Control-F for the find panel, choosing the {\it titleshort} property, the {\it =} filter, and the regular expression {\it G.*Rob.*}. We then quickly check to see how he is connected to the entire graph by temporarily moving that node away from the others to see roughly how many edges are attached to it, in the first picture.

     We then select the menu item Property->Selection->ReachableSubGraph, type 1 for the depth into the popup panel and 0 for the direction of the edges (outgoing). We then select the menu item Edit->New subgraph to save this selection for further manipulation, naming it GR.1hop.outgoing. We then select this new subgraph in the hierarchy window, and lay out this subgraph using using a hierarchical drawing algorithm. We can see simply from the drawing which papers were published first, as they are cited by the later ones. The result is shown in the second picture: Robertson has published 11 papers in this database. The coloring by the number of citations shows that Cone Trees is his most influential work. When we consider how Robertson fits into the topics described above in Task 2.4 above, it is clear that he is one of the most central contributors to the Focus+Context topics.

     Finally, we select all papers by hitting Control-F for the find panel, choosing the {\it type} property, the {\it =} filter, and the value 0 for papers. We explicitly add Robertson to the selection using the ViewSelection property, and save this whole set to a new subgraph that we name GRCite. We then select the Robertson node again as above, use the Property->Selection->ReachableSubGraph, pick a depth of 2 to find all papers that cite a paper written by Robertson, and save the resulting subgraph using the Edit->New subgraph menu. The final image shows the result of using the Property->Layout->Hierarchical Graph layout. property.

3. Focusing on a Single Author: Augmented Dataset
   • Process:
     
     • Data: same as above
     • Plugin: Create coauthorship edges linking authors who write papers together.
     • Color: number of citations, with rainbow mapping
     • Layout: circular (1,2), hierarchical (3), Frick force-directed (4)
   • Images:
     
   • Insight:
     We use the same dataset as before as a base, but use a plugin to add coauthorship links between authors. The first picture shows that as before, we select Robertson and move that node away from the main dataset. This time, we can see more links. The second picture shows the reachable subgraph that is 1 hop away from this node, and it is considerably bigger than before. We again save that subgraph so that we can apply different layouts to it. The third picture shows a hierarchical layout, and we see not only Robertson's papers but also his coauthors. The hierarchical layout automatically places the coauthors near the top, and the papers near the bottom, again with the ability to quickly see the rough order in which the papers were written. The fourth picture shows the usual force-directed layout that we have been using in most images, and it is easier to see coauthorship clusters in this view.

1. Focusing on Two Authors
   • Process:
     
     • Data: authors and papers and conferences
     • Plugin: Create coauthorship edges linking authors who write papers together.
     • Color: number of citations, with rainbow mapping
     • Layout: circular (1,2), hierarchical (3), Frick force-directed (4)
   • Images:
     

   • Insight:
     Here we focus on the relationship between two authors, in this case Robertson and Card. The first picture shows moving those selected nodes away from the main layout. The second shows a hierarchical layout of the neighborhood of all outgoing edges one hop away; that is, the publications and coauthors of the union of Card and Robertson. Note the third image for Robertson only, and the fourth image for Card only. The similarity of these final three images shows the very strong ties between these two authors.

2. Central Authors and Conferences: Overview
   • Process:
     • Data: authors and conferences
     • Plugin: Create links between author and conference by following links from author to paper, and from paper to conference. Then, delete papers.
     • Color: author blue, conf green (1,2); blue low - red high colormap with prolificness metric (3); rainbow colormap with yellow low to red high (4,5) with Strahler metric
   • Images:
     
     
   • Insight:
     We show an overview of the entire author-conference dataset with three different colorings: first, a simple blue=conferences and green=authors segmentation to show the large-scale structure of this dataset. Second, we select only the large connected component where we color papers in white and color the authors by the Strahler metric, which shows the branching structure of the dataset. We give preference to conference names in labelling of the middle image, and to author names on the right.

     In the second row, we zoom in to roughly the same section and view three colorings: the author/green and conference/blue; the Strahler coloring showing that van Wijk and Chuah are very important in the branching structure of the graph; and a blue to red colomap (where blue is low, red is high) with a "prolificness" metric that shows the number of InfoVis papers published. In this case, we see many high ranking people, including the previous two and also Chi, Hetzler, and Keahey. Although the label is not visible in the snapshot, the bright red box near the bottom of the image is Roth. Notice that Mackinlay and Shneiderman are not highly ranked by this local metric.

     Although we experimented with creating separate graphs for paper coauthoring and paper cocitation, we found the combined graph to be much more useful.

3. Central Authors and Conferences: Top Authors

   • Process:
     • Data: same as above
     • Plugin: same as above
     • Color: Strahler metric, rainbow colormap with yellow low to red high
     • Clustering: Strahler-convolution
     • Layout: Frick's Gem force-directed placement alg (1,2,5-7); circular (3,4)
   • Images:
     

   • Insight:
     We see a big connected component in the middle with authors and conferences that have strong ties (Vis, UIST, SIGGRAPH, SIGCHI, SIGMOD), including some blue and red indicating the most critical authors. There are many small connected components in a surrounding fringe, and the labels show that these are indeed quite peripheral (Interactions, CACM, SOCG, CIKM, JASIS etc). The Strahler-convolution clustering yields five clusters, according to increasing centrality. The first cluster is mostly yellow, and contains most of the data. The second cluster contains a next tier of 26 authors that have had a relatively strong impact. The third cluster contains a group of 7 influential authors (Chi, Bederson, Eick, Rao, Pirolli, Ward, and Brown), and the fourth cluster (Roth, Robertson, Keim, and Stasko) is yet more central. The fifth cluster is the single node of Mackinlay, and the most central cluster of two is Card and Shneiderman. Our automatic clustering method clearly yields very believeable results in this case.

4. Hierarchical Structure of Interauthor Connections
   • Process:
     • Data: all authors and conferences
     • Selection: central connected component in Task 3.2.2 above
     • Color: conferences white, authors colored in rainbow by prolificness metric, edges colored by eccentricity metric.
     • Clustering: small-world clustering using the strength metric, quotient graphs to see results

   • Images:
     

   • Insight:
     The overview image from Task 3.2.2, showing the graph of all authors and papers, is extremely cluttered. In the previous task we show one way to extricate more information, by finding the most important items via convolution clustering. Another clustering approach, small-worlds clustering, allows us to instead navigate through a hierarchical subdivision of the entire dataset. The simplified overview allows us to understand the graph's high level structure. The strength metric computes the number of cycles of length 3 and 4 passing through each edge, normalized by the maximum possible value. The first image shows the twice-clustered dataset. Small-world navigation is useful when exploring an unfamiliar graph to quickly find the structure of complex components. The eccentricity metric, which measures whether nodes are peripheral (here in yellow) or central (here in blue), guides us to complexity immediately. This metric is O(n^3), but the small-world decomposition simplifies the graph, making the computation tractable. The next frame shows zooming in towards the most central node that has many blue lines leading to it. We then jump inside that cluster, which is itself a small-world graph. We once again zoom towards the most central node with many blue edges, where we see a cluster that has the InfoVis 96 conference and all the authors who only published the infovis community in that year. We see this star shape small-world decomposition only for the InfoVis symposia, because of the nature of this dataset: it is only the InfoVis symposia that have a complete set of authors and papers available. (In this final image we see error in the dataset, where "M. Sheelagh" is a singleton duplicate node for the more prolific author Sheelagh Carpendale.)

OTHER TASKS

1. Pre-InfoVis Conference Evolution:
   • Process:
     
     • Data: all authors and papers and conferences
     • Plugin: same as Conference-Author example
     • Selection: only draw labels for conferences, only include items through given year
     • Color: all nodes are colored by the Strahler metric. conference nodes are round, paper and author nodes are square.
   • Images:
     
   • Insight:
     This sequence from 1986 to 1994 shows that SIGGRAPH and SIGCHI were the main conferences where infovis-related papers were published before the InfoVis Symposium was established. A cluster of theory venues, such as TOCS, finally joins up with the main connected component in 1994.

2. What happened in 1997?
   • Process: Charting the connected components vs. number of nodes in the author-paper graph with Excel
     
   • Images:
     
   • Insight:
     We were intrigued by the dramatic transition that was visually apparent in the year 1997 when we saw the InfoVis papers evolving over time in Task 2.3.3. We investigated further with standard charting tools to understand this phenomenon, and saw that when we consider the entire author-paper-conference dataset used for Pre-InfoVis Conference Evolution that 1997 is indeed where the normalized curves for number of connected components and the number of nodes cross.

COMMENTS

Many of our answers span tasks 2 and 3: showing some combination of topics, the relationship between authors and topics, and the relationship between authors and authors, and the evolution of all these aspects over time.

We use rainbow colormaps as a quick shortcut for true segmented colormap: we are usually interested in the high ranking part of the dataset where the reds and pinks and blues are clearly distinguishable, and less interested in the more uniform yellow-green region at the low end of the ramp.