Large Graph Visualization by Hierarchical Clustering
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [28]
  • |
  • Related
  • |
  • Cited by [2]
  • | |
  • Comments
    Abstract:

    This paper proposes a new technique for visualizing large graphs of several ten thousands of vertices and edges. To achieve a graph abstraction, a hierarchical clustered graph is extracted from a general large graph based on the community structures discovered in the graph. An enclosure geometrical partitioning algorithm is then applied to achieving the space optimization. For graph drawing, it uses a combination of spring-embbeder and circular drawing algorithms that archives the goal of optimization of display space and aesthetical niceness. The paper also discusses an interaction mechanism accompanied with the layout solution. The interaction not only allows users to navigate hierarchically through the entire clustered graph, but also provides a way to navigate multiple clusters concurrently. Animation is also implemented to preserve user mental maps during the interaction.

    Reference
    [1]Herman I,Melancon G,Marshall MS.Graph visualization in information visualization:A survey.IEEE Trans.on Visualization and Computer Graphics,2000,(6):24-44.
    [2]Marshall S.Methods and tools for the visualization and navigation of graphs[Ph.D.Thesis].Bordeaux:University Bordeaux I,2001.
    [3]Auber D.Tulip:a huge graph visualization framework.In:Mutzel P,Junger M,eds.Graph Drawing Software,Mathematics and Visualization.Springer-Verlag,2003,105-126.
    [4]Eades P,Feng Q.Multilevel visualization of clustered graphs.In:North SC,ed.Graph Drawing (GD'96).California:Springer,1996.101-112.
    [5]Feng Q.Algorithms for drawing clustered graphs[Ph.D.Thesis].Newcastle:University of Newcastle,1997.
    [6]Ware C.Information Visualization:Perception for Design.San Francisco:Morgan Kaufmann Publishers,2004.
    [7]Wilkins AJ.Visual Stress.Oxford:Oxford University Press,1995.
    [8]Harel D,Koren Y.Graph drawing by high-dimensional embedding.Journal of Graph Algorithms and Applications,2004,8(2):195-214.
    [9]Walshaw C.A multilevel algorithm for force-directed graph drawing.Mathematics Research Report 00/IM/60,University of Greenwich,2000.
    [10]Abello J,van Ham F,Krishnan N.ASK-GraphView:A large scale graph visualization system.IEEE Trans.on Visualization and Computer Graphics,2006,12(5):669-676.
    [11]Harel D,Koren Y.A fast multi-scale method for drawing large graphs.In:Marks J,ed.Graph Drawing.Colonial Williamsburg:Springer-Verlag,2000.183-196.
    [12]Hachul S,Junger M.An experimental comparison of fast algorithms for drawing general large graphs.In:Healy P,Nikolov NS,ed.Graph Drawing.Limerick:Springer-Verlag,2005.235-250.
    [13]Auber D,Chiricota Y,Jourdan F,Malancon G.Multiscale visualization of small world networks.In:IEEE Symp.on Information Visualization.Seattle:IEEE Computer Society,2003.75-81.
    [14]Auber D,Jourdan F.Interactive refinement of multi-scale network clusterings.In:Int'l Conf.on Information Visualization.London:IEEE,2005.703-709.
    [15]Archambault D,Munzner T,Auber D.TopoLayout:Multi-Level graph layout by topological features.IEEE Trans.on Visualization and Computer Graphics,2007,13(2):305-317.
    [16]Fekete JD,Wang D,Dang N,Aris A,Plaisant C.Overlaying graph links on treemaps.In:IEEE Symp.on Information Visualization -Symp.Poster Compendium.Seattle:IEEE Computer Society,2003.82-83.
    [17]Johnson B,Shneiderman B.Tree-Maps:A space-filling approach to the visualization of hierarchical information structures.In:Kaufman AE,ed.1991 IEEE Visualization.IEEE Computer Society,1991.284-291.
    [18]Newman MEJ.Fast algorithm for detecting community structure in networks.Physical Review E,2004,69:066133.
    [19]Nguyen QV,Huang ML.EncCon:An approach to constructing interactive visualization of large hierarchical data.Information Visualization Journal,2005,4(1):1-21.
    [20]Nguyen QV,Huang ML.Space-Optimized tree:A connection+enclosure approach for the visualization of large hierarchies.Information Visualization Journal,2003,2(1):3-15.
    [21]Eades P.A heuristic for graph drawing.Congressus Numerantium,1984,42:149-160.
    [22]Robert JC.On encouraging multiple views for visualisation.In:Int'l Conf.on Information Visualization.London:IEEE,1998.8-14.
    [23]Kernighan G,Lin S.An efficient heuristic procedure for partitioning graphs.The Bell System Technical Journal,1970,29(2):291-307.
    [24]Newman MEJ,Girvan M.Finding and evaluating community structure in networks.Physical Review E,2004,69:026113.
    [25]di Battista G,Eades P,Tamassia R,Tollis IG.Graph Drawing:Algorithms for the Visualization of Graphs.Prentice Hall,1999.
    [26]Ware C,Purchase H,Colpoys L,McGill M.Cognitive measurements of graph aesthetics.Information Visualization Journal,2002,1(2):103-110.
    [27]Huang ML,Nguyen QV.A fast algorithm for balanced graph clustering.In:Proc.of the Int'l Conf.on Information Visualization.Zürich:IEEE,2007.46-52.
    [28]Duncan CA,Goodrich MT,Kobourov SG.Balanced aspect ratio trees and their use for drawing large graphs.Journal of Graph Algorithms and Applications,2000,4(3):19-46.
    Related
    Comments
    Comments
    分享到微博
    Submit
Get Citation

黄茂林,NGUYEN Quang Vinh.用多层次聚类法完成的大规模关系图的可视化.软件学报,2008,19(8):1933-1946

Copy
Share
Article Metrics
  • Abstract:8675
  • PDF: 8164
  • HTML: 0
  • Cited by: 0
History
  • Received:April 18,2008
  • Revised:January 22,2008
You are the first2042105Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063