|
Introduction Wikipedia is an interesting dataset for visualization. As an encyclopedia, it's articles span millions of topics. Being a human edited entity, connections between topics are diverse, interesting, and sometimes perplexing - five hops takes you from subatomic particles to Snoop Dog. Wikipedia is revealing in how humans organize data and how interconnected seemingly unrelated topics can be. During my time at AT&T Labs, which coincidently has a great information visualization group, I started think about how to visualizing something as massive as Wikipedia. With roughly 1.5 million articles (vertices) and tens of millions of article links (edges), a comprehensive visualization package would have to found or built. After playing around with GraphViz, but getting frustrated with layout limitations, I decided on the latter option: build! I don't buy into the reuse-recycle methodology. That's great for software development, but not research. I believe great ideas and innovations come about by redoing and rethinking existing problems. If you always use what has already been "solved" and built, how do you know it can't be done better? And so I leaped head first into my own large-scale data visualization project, from scratch. I hope to publish the novel graph layout techniques I developed during this process.
WikiViz
v5
WikiViz v1 to v4 Layout is done using a spring model - each edge in the graph acts like a spring, pushing connected nodes apart if they are too close and pulling connected nodes together. The spring constant and optimal spring length can be adjusted. Overlapping nodes are nudged apart using a separate, non-spring-based method. The code base is under a thousand lines of Java code, and was whipped together a few hours at a time over the course of a week. Tweaking the layout code (dampening, overlap detection, etc.) consumed most of that time. Although called WikiViz, there is nothing specifically Wikipedia about it. It's a general graph layout and render engine that can be used with many sources. The input is a simplified version of GraphViz's already simple DOT format:
Initially, the graph was rendered real-time on screen. With about 1000 edges, the graph was interactive. However, as I pushed the edge count into the tens of thousands, it became clear that watching the graph balance into an energy minimized state was going to take serious processing time (hours). Not only was each iteration taking about half a second (2 fps), but the number of iterations required to properly layout the graph was large (tens of thousands). It was clear that the computation needed to be run non-graphically and saved to file when complete. This also allowed me to escape the low resolution of monitors and produce high-resolution images (20,000x20,000 pixels or more). For the time being, I am using Wikipedia's category links database (cl_to and cl_sortkey fields), which includes ~178k vertices and 6.5 million edges. Expanding to Wikipedia's full 1.5 million vertices is going to be a huge challenge (memory requirements alone!). However, the former data set is plenty interesting. Currently, I am working with various subsets of the database: two to fifty hops out, starting from Humans, History, Politics, Mathematics and Physics.
WikiViz v1 to v4 Images Below are some visualizations that have been produced. Various
layout duration and spring attributes were used. Beware of the high
resolution links. Some JPEGs are 30+ MB, which can seriously tax
your hardware.
GraphViz
Images
Go
to Home Page
|
| chris.harrison@cs.cmu.edu | © Chris Harrison |