Structural differences between two graphs through hierarchies

ABSTRACT

This paper presents a technique for visualizing the differences between two graphs. The technique assumes that a unique labeling of the nodes for each graph is available, where if a pair of labels match, they correspond to the same node in both graphs. Such labeling often exists in many application areas: IP addresses in computer networks, namespaces, class names, and function names in software engineering, to name a few. As many areas of the graph may be the same in both graphs, we visualize large areas of difference through a graph hierarchy. We introduce a path-preserving coarsening technique for degree one nodes of the same classification. We also introduce a path-preserving coarsening technique based on betweenness centrality that is able to illustrate major differences between two graphs.

REFERENCES

• 1: James Abello , Frank van Ham , Neeraj Krishnan, ASK-GraphView: A Large Scale Graph Visualization System, IEEE Transactions on Visualization and Computer Graphics, v.12 n.5, p.669-676, September 2006 [doi>10.1109/TVCG.2006.120]
• 2: Daniel Archambault , Tamara Munzner , David Auber, GrouseFlocks: Steerable Exploration of Graph Hierarchy Space, IEEE Transactions on Visualization and Computer Graphics, v.14 n.4, p.900-913, July 2008 [doi>10.1109/TVCG.2008.34]
• 3: K. Boitmanis, U. Brandes, and C. Pich. Visualizing internet evolution on the autonomous systems level. In Proc. of Graph Drawing (GD '07), volume 4875 of LNCS, pages 365--376, 2007.
• 4: U. Brandes. A faster algorithm for betweenness centrality. J. Math. Soc., 25(2):163--177, 2001.
• 5: U. Brandes, D. Fleischer, and T. Puppe. Dyanmic sprectral layout of small worlds. In Proc. of Graph Drawing (GD '05), number 3843 in LNCS, pages 25--36, 2005.
• 6: Ulrik Brandes , Dorothea Wagner, A Bayesian Paradigm for Dynamic Graph Layout, Proceedings of the 5th International Symposium on Graph Drawing, p.236-247, September 18-20, 1997
• 7: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 8: Emilio Di Giacomo , Walter Didimo , Luca Grilli , Giuseppe Liotta, Graph Visualization Techniques for Web Clustering Engines, IEEE Transactions on Visualization and Computer Graphics, v.13 n.2, p.294-304, March 2007 [doi>10.1109/TVCG.2007.40]
• 9: Stephan Diehl , Carsten Görg, Graphs, They Are Changing, Revised Papers from the 10th International Symposium on Graph Drawing, p.23-30, August 26-28, 2002
• 10: Peter Eades , Qing-Wen Feng, Multilevel Visualization of Clustered Graphs, Proceedings of the Symposium on Graph Drawing, p.101-112, September 18-20, 1996
• 11: C. Erten, P. J. Harding, S. Kobourov, K. Wampler, and G. V. Yee. GraphAEL: Graph animations with evolving layouts. In Proc. of Graph Drawing (GD '03), volume 2912 of LNCS, pages 98--110. Springer-Verlag, 2003.
• 12: L. C. Freeman. A set of measures of centrality based upon betweeness. Sociometry, 40(1):35--41, 1977.
• 13: Yaniv Frishman , Ayellet Tal, Dynamic Drawing of Clustered Graphs, Proceedings of the IEEE Symposium on Information Visualization, p.191-198, October 10-12, 2004 [doi>10.1109/INFOVIS.2004.18]
• 14: Y. Frishman and A. Tal. Online dynamic graph drawing. In Proc. Eurographics/IEEE VGTC Symp. on Visualization (EuroVis '07), pages 75--82, 2007.
• 15: Emden R. Gansner , Yehuda Koren , Stephen C. North, Topological Fisheye Views for Visualizing Large Graphs, IEEE Transactions on Visualization and Computer Graphics, v.11 n.4, p.457-468, July 2005 [doi>10.1109/TVCG.2005.66]
• 16: C. Görg, P. Birke, M. Pohl, and S. Diehl. Dynamic graph drawing of sequences of orthogonal and hierarchical graphs. In Proc. of Graph Drawing (GD '04), volume 3383 of LNCS, pages 228--238, 2004.
• 17: S. Hachul and M. Jünger. Drawing large graphs with a potential-field-based multilevel algorithm. In Proc. Graph Drawing (GD '04), volume 3383 of LNCS, pages 285--295. Springer-Verlag, 2004.
• 18: Yuntao Jia , Jared Hoberock , Michael Garland , John Hart, On the Visualization of Social and other Scale-Free Networks, IEEE Transactions on Visualization and Computer Graphics, v.14 n.6, p.1285-1292, November 2008 [doi>10.1109/TVCG.2008.151]
• 19: Gautam Kumar , Michael Garland, Visual Exploration of Complex Time-Varying Graphs, IEEE Transactions on Visualization and Computer Graphics, v.12 n.5, p.805-812, September 2006 [doi>10.1109/TVCG.2006.193]
• 20: Stephen C. North, Incremental Layout in DynaDAG, Proceedings of the Symposium on Graph Drawing, p.409-418, September 20-22, 1995
• 21: H. Purchase, E. Hoggan, and C. Görg. How important is the "mental map"? -- an empirical investigation of a dynamic graph layout algorithm. In Proc. Graph Drawing (GD '06), volume 4372 of LNCS, pages 184--195, 2006.
• 22: George Robertson , Roland Fernandez , Danyel Fisher , Bongshin Lee , John Stasko, Effectiveness of Animation in Trend Visualization, IEEE Transactions on Visualization and Computer Graphics, v.14 n.6, p.1325-1332, November 2008 [doi>10.1109/TVCG.2008.125]
• 23: Doug Schaffer , Zhengping Zuo , Saul Greenberg , Lyn Bartram , John Dill , Shelli Dubs , Mark Roseman, Navigating hierarchically clustered networks through fisheye and full-zoom methods, ACM Transactions on Computer-Human Interaction (TOCHI), v.3 n.2, p.162-188, June 1996 [doi>10.1145/230562.230577]
• 24: Frank van Ham , Jarke J. van Wijk, Interactive Visualization of Small World Graphs, Proceedings of the IEEE Symposium on Information Visualization, p.199-206, October 10-12, 2004 [doi>10.1109/INFOVIS.2004.43]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.0 General

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms