Effective and Efficient PageRank-based Positioning for Graph Visualization

Shiqi Zhang, Renchi Yang, Xiaokui Xiao*, Xiao Yan, Bo Tang*

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

Abstract

Graph visualization is a vital component in many real-world applications (e.g., social network analysis, web mining, and bioinformatics) that enables users to unearth crucial insights from complex data. Lying in the core of graph visualization is the node distance measure, which determines how the nodes are placed on the screen. A favorable node distance measure should be informative in reflecting the full structural information between nodes and effective in optimizing visual aesthetics. However, existing node distance measures yield sub-par visualization quality as they fall short of these requirements. Moreover, most existing measures are computationally inefficient, incurring a long response time when visualizing large graphs. To overcome such deficiencies, we propose a new node distance measure, PDist, geared towards graph visualization by exploiting a well-known node proximity measure,personalized PageRank. Moreover, we propose an efficient algorithm Tau-Push for estimating PDist under both single- and multi-level visualization settings. With several carefully-designed techniques, TauPush offers non-trivial theoretical guarantees for estimation accuracy and computation complexity. Extensive experiments show that our proposal significantly outperforms 13 state-of-the-art graph visualization solutions on 12 real-world graphs in terms of both efficiency and effectiveness (including aesthetic criteria and user feedback). In particular, our proposal can interactively produce satisfactory visualizations within one second for billion-edge graphs.
Original languageEnglish
Article number76
Number of pages27
JournalProceedings of the ACM on Management of Data
Volume1
Issue number1
DOIs
Publication statusPublished - May 2023

User-Defined Keywords

  • approximate algorithm
  • personalized pagerank
  • graph visualization

Fingerprint

Dive into the research topics of 'Effective and Efficient PageRank-based Positioning for Graph Visualization'. Together they form a unique fingerprint.

Cite this