Proceedings: GI 2009

Structural differences between two graphs through hierarchies

Daniel Archambault

Proceedings of Graphics Interface 2009: Kelowna, British Columbia, Canada, 25 - 27 May 2009, 87-94

  • BibTex

    @inproceedings{Archambault:2009:,
    author = {Archambault, Daniel},
    title = {Structural differences between two graphs through hierarchies},
    booktitle = {Proceedings of Graphics Interface 2009},
    series = {GI 2009},
    year = {2009},
    issn = {0713-5424},
    isbn = {978-1-56881-470-4},
    location = {Kelowna, British Columbia, Canada},
    pages = {87--94},
    numpages = {8},
    publisher = {Canadian Human-Computer Communications Society},
    address = {Toronto, Ontario, Canada},
    }

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.