Giga Graph Cities: Their Buckets, Buildings, Waves, and Fragments

Area of Science:

• Graph theory
• Data visualization
• Network analysis

Background:

• Graphs are fundamental data structures, but visualizing large-scale graphs remains challenging.
• Existing methods struggle with interpretability and scalability for massive networks.

Purpose of the Study:

• To introduce Graph Cities, a novel 3-D visualization technique for graph partitions.
• To enable humanly interpretable descriptions of large graphs irrespective of size.

Main Methods:

• Partitioning graph edges into maximal connected subgraphs (fixed points).
• Representing subgraphs as 3-D 'Buildings' and positioning them via polylog bucketization.
• Generating street networks using Delaunay triangulation of building locations.

Main Results:

• Demonstrated Graph Cities on large networks: Friendster (1.8B edges), IMDb (115M edges), patent citations (16.5M edges).
• Efficiently generated Graph Cities for up to 2 billion edges within minutes (excluding I/O).

Conclusions:

• Graph Cities offer a scalable and interpretable approach to visualizing massive graphs.
• The method facilitates understanding complex network structures across diverse domains.