research-article

Free access

Structural differences between two graphs through hierarchies

Author:

Daniel ArchambaultAuthors Info & Claims

GI '09: Proceedings of Graphics Interface 2009

Pages 87 - 94

Published: 25 May 2009 Publication History

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]

J. Abello, F. van Ham, and N. Krishnan. ASK-Graph View: A large scale graph visualization system. IEEE Trans. on Visualization and Computer Graphics (Proc. Vis/InfoVis '06), 12(5):669--676, 2006.

Digital Library

[2]

D. Archambault, T. Munzner, and D. Auber. GrouseFlocks: Steerable exploration of graph hierarchy space. IEEE Trans. on Visualization and Computer Graphics, 14(4):900--913, 2008.

Digital Library

[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.

Digital Library

[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.

Digital Library

[6]

U. Brandes and D. Wagner. A bayesian paradigm for dynamic graph layout. In Proc. of Graph Drawing (GD '97), volume 1353 of LNCS, pages 236--247, 1997.

Digital Library

[7]

S. A. Cook. The complexity of theorem-proving procedures. In Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, pages 151--158, 1971.

Digital Library

[8]

E. Di Giacomo, W. Didimo, L. Grilli, and G. Liotta. Graph visualization techniques for web clustering engines. IEEE Trans. on Visualization and Computer Graphics, 13(2):294--304, March/April 2007.

Digital Library

[9]

S. Diehl and C. Görg. Graphs, they are a changing -- dynamic graph drawing for a sequence of graphs. In Proc. of Graph Drawing (GD '02), volume 2528 of LNCS, pages 23--31. Springer-Verlag, 2002.

Digital Library

[10]

P. Eades and Q. Feng. Multilevel visualization of clustered graphs. In Proc. Graph Drawing (GD '96), volume 1190 of LNCS, pages 101--112. Springer-Verlag, 1996.

Digital Library

[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]

Y. Frishman and A. Tal. Dynamic drawing of clustered graphs. In Proc. IEEE Symposium on Information Visualization (InfoVis '04), pages 191--198, 2004.

Digital Library

[14]

Y. Frishman and A. Tal. Online dynamic graph drawing. In Proc. Eurographics/IEEE VGTC Symp. on Visualization (EuroVis '07), pages 75--82, 2007.

Digital Library

[15]

E. Gansner, Y. Koren, and S. North. Topological fisheye views for visualizing large graphs. IEEE Trans. on Visualization and Computer Graphics, 11(4):457--468, 2005.

Digital Library

[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.

Digital Library

[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.

Digital Library

[18]

Y. Jia, J. Hoberock, M. Garland, and J. C. Hart. On the visualization of social and other scale free networks. IEEE Trans. on Visualization and Computer Graphics, 14(6):1285--1292, 2008.

Digital Library

[19]

G. Kumar and M. Garland. Visual exploration of complex time-varying graphs. IEEE Trans. on Visualization and Computer Graphics (Proc. Vis/InfoVis 2006), 12(5):805--812, 2006.

Digital Library

[20]

S. North. Incremental layout in dynaDAG. In Proc. of Graph Drawing, volume 1027 of LNCS, pages 409--418. Springer-Verlag, 1995.

Digital Library

[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.

Digital Library

[22]

G. Robertson, R. Fernandez, D. Fisher, B. Lee, and J. Stasko. Effectiveness of animation in trend visualization. IEEE Trans. on Visualization and Computer Graphics (Proc. Vis/InfoVis '08), 14(6):1325--1332, 2008.

Digital Library

[23]

D. Schaffer, Z. Zuo, S. Greenberg, L. Bartram, J. Dill, S. Dubs, and M. Roseman. Navigating hierarchically clustered networks through fisheye and full-zoom methods. ACM Trans. on Computer-Human Interaction (TOCHI), 3(2):162--188, 1996.

Digital Library

[24]

F. van Ham and J. van Wijk. Interactive visualization of small world graphs. In Proc. IEEE Symposium on Information Visualization (Info-Vis '04), pages 199--206, 2004.

Digital Library

Cited By

Wallner GPohl Mvon Landesberger TBallweg K(2019)Perception of Differences in Directed Acyclic Graphs: Influence Factors & Cognitive StrategiesProceedings of the 31st European Conference on Cognitive Ergonomics10.1145/3335082.3335083(57-64)Online publication date: 10-Sep-2019
https://dl.acm.org/doi/10.1145/3335082.3335083
Vogogias AKennedy JArchambault DBach BSmith VCurrant H(2018)BayesPilesACM Transactions on Intelligent Systems and Technology10.1145/323062310:1(1-23)Online publication date: 28-Nov-2018
https://dl.acm.org/doi/10.1145/3230623
Hasitschka PSabol VGlowacka DMilios ESoto APaulovich F(2017)Visual Exploration and Analysis of Recommender HistoriesProceedings of the 2017 ACM Workshop on Exploratory Search and Interactive Data Analytics10.1145/3038462.3038467(33-40)Online publication date: 13-Mar-2017
https://dl.acm.org/doi/10.1145/3038462.3038467
Show More Cited By

Index Terms

Structural differences between two graphs through hierarchies
1. Human-centered computing
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms

Recommendations

On 4-γt -critical graphs of diameter two

A vertex subset S of graph G is a total dominating set of G if every vertex of G is adjacent to a vertex in S. For a graph G with no isolated vertex, the total domination number of G, denoted by @c"t(G), is the minimum cardinality of a total dominating ...
Total domination in planar graphs of diameter two

MacGillivary and Seyffarth [G. MacGillivray, K. Seyffarth, Domination numbers of planar graphs, J. Graph Theory 22 (1996) 213-229] proved that planar graphs of diameter two have domination number at most three. Goddard and Henning [W. Goddard, M.A. ...
Some structural properties of minimally contraction-critically 5-connected graphs

An edge of a k-connected graph is said to be k-removable (resp. k-contractible) if the removal (resp. the contraction ) of the edge results in a k-connected graph. A k-connected graph with neither k-removable edge nor k-contractible edge is said to be ...

Comments

Information & Contributors

Information

Published In

cover image Guide Proceedings

GI '09: Proceedings of Graphics Interface 2009

May 2009

257 pages

ISBN:9781568814704

Program Chairs:
Amy Gooch
University of Victoria, Canada
,
Melanie Tory
University of Victoria, Canada

Sponsors

The Canadian Human-Computer Communications Society / Société Canadienne du Dialogue Humaine Machine (CHCCS/SCDHM)

Publisher

Canadian Information Processing Society

Canada

Publication History

Published: 25 May 2009

Qualifiers

Research-article

Acceptance Rates

GI '09 Paper Acceptance Rate 28 of 77 submissions, 36%;

Overall Acceptance Rate 206 of 508 submissions, 41%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
380
Total Downloads

Downloads (Last 12 months)23
Downloads (Last 6 weeks)11

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wallner GPohl Mvon Landesberger TBallweg K(2019)Perception of Differences in Directed Acyclic Graphs: Influence Factors & Cognitive StrategiesProceedings of the 31st European Conference on Cognitive Ergonomics10.1145/3335082.3335083(57-64)Online publication date: 10-Sep-2019
https://dl.acm.org/doi/10.1145/3335082.3335083
Vogogias AKennedy JArchambault DBach BSmith VCurrant H(2018)BayesPilesACM Transactions on Intelligent Systems and Technology10.1145/323062310:1(1-23)Online publication date: 28-Nov-2018
https://dl.acm.org/doi/10.1145/3230623
Hasitschka PSabol VGlowacka DMilios ESoto APaulovich F(2017)Visual Exploration and Analysis of Recommender HistoriesProceedings of the 2017 ACM Workshop on Exploratory Search and Interactive Data Analytics10.1145/3038462.3038467(33-40)Online publication date: 13-Mar-2017
https://dl.acm.org/doi/10.1145/3038462.3038467
Blascheck TSchweizer MBeck FErtl T(2017)Visual Comparison of Eye Movement PatternsComputer Graphics Forum10.1111/cgf.1317036:3(87-97)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1111/cgf.13170
Stitz HLuger SStreit MGehlenborg N(2016)AVOCADOComputer Graphics Forum10.5555/3071534.307158535:3(481-490)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.5555/3071534.3071585
Liao QShi LWang C(2013)Visual analysis of large-scale network anomaliesIBM Journal of Research and Development10.1147/JRD.2013.224935657:3-4(13-13)Online publication date: 1-May-2013
https://dl.acm.org/doi/10.1147/JRD.2013.2249356
Kriglstein SWallner GRinderle-Ma S(2013)A visualization approach for difference analysis of process models and instance trafficProceedings of the 11th international conference on Business Process Management10.1007/978-3-642-40176-3_18(219-226)Online publication date: 26-Aug-2013
https://dl.acm.org/doi/10.1007/978-3-642-40176-3_18
Zaman LKalra AStuerzlinger WBrooks SIrani P(2011)The effect of animation, dual view, difference layers, and relative re-layout in hierarchical diagram differencingProceedings of Graphics Interface 201110.5555/1992917.1992947(183-190)Online publication date: 25-May-2011
https://dl.acm.org/doi/10.5555/1992917.1992947
Archambault DPurchase HPinaud B(2010)Difference map readability for dynamic graphsProceedings of the 18th international conference on Graph drawing10.5555/1964371.1964377(50-61)Online publication date: 21-Sep-2010
https://dl.acm.org/doi/10.5555/1964371.1964377
Archambault DPurchase HPinaud B(2010)The readability of path-preserving clusterings of graphsProceedings of the 12th Eurographics / IEEE - VGTC conference on Visualization10.1111/j.1467-8659.2009.01683.x(1173-1182)Online publication date: 9-Jun-2010
https://dl.acm.org/doi/10.1111/j.1467-8659.2009.01683.x

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten