Visualization of Large-Scale Weighted Clustered Graph: A Genetic Approach

Jiayu Zhou, Youfang Lin, Xi Wang

Abstract

Visualizing large-scale weighted clustered graphs is a computationally intensive task, often exceeding the capabilities of traditional Genetic Algorithms (GAs). This paper presents a Hierarchical Genetic Algorithm (HGA) that utilizes a bottom-up approach and a novel "sub-graph rotating and scaling" (RS) process to achieve scalability. By abstracting clusters into centroids and optimizing their relative orientations, the HGA maintains high layout quality while exhibiting near-linear time complexity. Experimental results show that HGA significantly outperforms standard GAs in speed while preserving a strong correlation between edge weights and node distances.

Introduction

Large-scale graph visualization is critical for understanding complex systems like social networks or biological structures. While Genetic Algorithms are prized for their flexibility in handling complex constraints, they typically suffer from poor scalability; as node counts increase, the search space for an optimal layout grows exponentially. This research addresses the need for a visualization method that combines the optimization power of GAs with the efficiency required for datasets containing thousands of nodes.

Methodology

The authors propose a hierarchical framework to mitigate the computational burden of global optimization. The HGA process consists of three primary stages:

  1. Bottom-Up Drawing: The algorithm begins at the "leaf" level, applying a traditional GA to position nodes within small, ground-level clusters.
  2. Abstraction via Centroids: Once a cluster is laid out, it is abstracted into a single "centroid." This allows the algorithm to ignore internal cluster complexity when calculating higher-level relationships, drastically reducing the number of calculations per generation.
  3. Sub-Graph Rotating and Scaling (RS): To approximate global optimization without moving every individual node, sub-graphs are treated as rigid bodies. Each node or centroid is represented as a 4-tuple $(x, y, r, s)$, where $x,y$ are coordinates, $r$ is the rotation angle, and $s$ is the scaling ratio.

The fitness function optimizes for a "correlation relationship" where the physical distance between nodes in the visualization is inversely proportional to the edge weight.

Experimental Evaluation

The HGA was tested on clustered graphs with 500, 1000, 2500, and 5000 nodes, comparing its performance against a Planar GA (PGA), a Force-Directed Algorithm (FDA), and random drawing.

Computational Efficiency

A key insight from the study is the transition from exponential to near-linear scaling. As shown in Figure 1, the time cost for HGA remains manageable even as the node count reaches 5000. Specifically, HGA with RS completed the 5000-node layout in approximately 91.56 seconds, whereas the standard PGA exceeded 1000 seconds.

Figure 1: Time cost comparison showing HGA's superior scalability compared to traditional PGA.

Layout Quality

The quality of the visualization is measured by the correlation between edge weights and physical distances. While PGA maintains the highest correlation (above 0.9), it is too slow for large-scale use. HGA with RS serves as an effective middle ground, achieving a correlation score of 0.65 at 5000 nodes. Without the RS process, the correlation drops significantly to 0.3, highlighting the necessity of the rotating and scaling mechanism for maintaining global structure.

Figure 2: Correlation scores across different algorithms, demonstrating the impact of the RS process on layout quality.

Conclusion

The Hierarchical Genetic Algorithm (HGA) provides a scalable solution for large-scale graph visualization. By combining local optimization with hierarchical abstraction and rigid-body transformations (RS), the algorithm achieves a balance between speed and layout accuracy. Future work will explore refining the fitness functions to further improve correlation and integrating automated clustering to enhance the algorithm's robustness for unorganized datasets.

Summary updated

Abstract

In this paper, a bottom-up hierarchical genetic algorithm is proposed to visualize clustered data into a planar graph. To achieve global optimization by accelerating local optimization process, we introduce subgraph rotating and scaling processes into the genetic algorithm. Compared with existing methods, the proposed approach is more feasible and promising, with more accurate graph layout and more satisfiable computationally efficient performance, as demonstrated by the experimental results.
BibTeX
@inproceedings{zhou2008visualization,
  author = {Jiayu Zhou and Youfang Lin and Xi Wang},
  title = {{Visualization of Large-Scale Weighted Clustered Graph: A Genetic Approach}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure