We present an information visualization tool, known as GreenMax, to visually explore large small-world graphs with up to a million graph nodes on a desktop computer. A major motivation for scanning a small-world graph in such a dynamic fashion is the demanding goal of identifying not just the well-known features but also the unknown–known and unknown–unknown features of the graph. GreenMax uses a highly effective multilevel graph drawing approach to pre-process a large graph by generating a hierarchy of increasingly coarse layouts that later support the dynamic zooming of the graph. This paper describes the graph visualization challenges, elaborates our solution, and evaluates the contributions of GreenMax in the larger context of visual analytics on large small-world graphs. We report the results of two case studies using GreenMax and the results support our claim that we can use GreenMax to locate unexpected features or structures behind a graph.
MilgramS.The small world problem. Psychology Today1967; 2: 60–67.
2.
WattsDJStrogatzSH. Collective dynamics of small-world networks. Nature1998; 393: 440–442.
3.
Di BattistaGEadesPTamassiaRTollisIG. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall: Englewood Cliffs, NJ, 1999.
4.
SugiyamaK.Graph Drawing and Applications. World Scientific Publishing: Singapore, 2002.
5.
WongPCChinGJrFooteHMackeyPThomasJ.Have green—a visual analytics framework for large semantic graphs. Proceedings of the IEEE Symposium on Visual Analytics Science and Technology (VAST) 2006 (Baltimore, MD), IEEE Computer Society: Piscataway, NJ, 2006; 67–74.
6.
KoldaTBrownDCoronesJCritchlowTEliassi-RadTGetoorLHendricksonBKumarVLambertDMatarazzoCMcCurleyKMerrillMSamatovaNSpeckDSrikantRThomasJWertheimerMWongPC. Data Sciences Technology for Homeland Security Information Management and Knowledge Discovery. Report of the DHS Workshop on Data Sciences. Jointly released by Sandia National Laboratories and Lawrence Livermore National Laboratory, Alexandria, VA, 22–23 September 2004.
7.
ThomasJJCookKA (Eds). Illuminating the Path: The Research and Development Agenda for Visual Analytics. IEEE CS Press: Los Alamitos, CA, 2005.
AbelloJvan HamF.Matrix Zoom: A visual interface to semi-external graphs. Proceedings IEEE Symposium on Information Visualization 2004 (Austin, TX), IEEE Computer Society: Los Alamitos, CA, 2004; 180–190.
WongPCFooteHChinGJr.MackeyPPerrineK.Graph signatures for visual analytics. IEEE Transactions on Visualization and Computer Graphics2006; 12: 1399–1413.
14.
WongPCFooteHMackeyPPerrineKChinG.Jr.Generating graphs for visual analytics through interactive sketching. IEEE Transactions on Visualization and Computer Graphics2006; 12: 1386–1398.
15.
WongPCMackeyPPerrineKEaganJFooteHThomasJ.Dynamic visualization of graphs with extended labels. Proceedings of the IEEE Symposium on Information Visualization 2005 (Minneapolis, MN), IEEE Computer Society: Washington, DC, 2005; 73–80.
16.
GD2008.16th International Symposium on Graph Drawing 2008, http://www.gd2008.org/ (accessed 29 February 2008).
17.
CardSKMackinlayJDShneidermanB.Readings in Information Visualization, Using Vision to Think. Morgan Kaufmann: San Mateo, CA, 1999.
18.
ChenC.Information Visualization Beyond the Horizon. 2nd ednSpringer-Verlag: London, 2004.
19.
HermanIMelanconGMarshallMS. Graph visualization and navigation in information visualization: A survey. IEEE Transactions on Visualization and Computer Graphics2000; 6: 24–43.
ShneidermanB.Network visualization by semantic substrates. IEEE Transactions on Visualization and Computer Graphics2006; 12: 733–740.
22.
ArisAShneidermanB.Designing semantic substrates for visual network exploration. Information Visualization2007; 4: 1–20.
23.
HarelDKorenY.A fast multi-scale algorithm for drawing large graphs. Journal of Graph Algorithms and Applications2003; 6: 179–202.
24.
WalshawC.A multilevel algorithm for forced-directed graph-drawing. Journal of Graph Algorithms and Applications2003; 7: 253–285.
25.
BarnardSTSimonHD. A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. Concurrency: Practice and Experience1994; 6: 101–107.
KeaheyARobertsonEL. Nonlinear magnification fields. Proceedings IEEE Symposium on Information Visualization 98, 1998 (Research Triangle Park, NC), IEEE CS Press: Los Alamitos, CA, 1998; 51–58.
28.
BierEAStoneMCPierKBuxtonWDeRoseTD. Toolglass and magic lenses: The see-through interface. Proceedings of Siggraph ′93, 1993 (Anaheim, August), Computer Graphics Annual Conference Series, ACM: New York, 1993; 73–80.
29.
StoneMCFishkinKBierEA. The movable filter as a user interface tool. Proceedings of the SIGCHI Conference on Human Factors in Computing Systems (CHI ′94) 1994 (Boston, MA), ACM Press: New York, NY, 1994; 306–312.
EllisGDixA.The Plot, the Clutter, the Sampling and its Lens: Occlusion Measures for Automatic Clutter Reduction. AVI ′06, 2006 (Venice), ACM: New York, 2006; 266–269.
32.
WongNCarpendaleMSTGreenbergS.EdgeLens: An interactive method for managing congestion in graphs. Proceedings IEEE Symposium on Information Visualization 2003 (Seattle, WA), IEEE Computer Society Press: Los Alamitos, CA, 2003; 51–58.
33.
FruchtermanTMJReingoldEM. Graph drawing by force-directed placement, software. Practice & Experience1991; 21: 1129–1164.
34.
KamadaTKawaiS.An algorithm for drawing general undirected graphs. Information Processing Letters, 1989; 31: 7–15.
35.
YinR.Application of Case Study Research. Sage Publishing: Newbury Park, CA, 1993.
36.
LesneA.Complex network: From graph theory to biology. Letters in Mathematical Physics2006; 78: 235–262.
37.
ShannonPMarkielAOzierOBaligaNSWangJTRamageDAminNSchwikowskiBIdekerT.Cytoscape: A software environment for integrated models in biomolecular interaction networks. Genome Research2003; 13: 2498–2504.
38.
MediniDCovacciADonatiC.Protein homology network families reveal step-wise diversification of type III and type IV secretion systems. PLOS Computational Biology2006; 2: 1543–1551.
