Project Goal

The goal of this project is to re-implement the key visualization techniques from the paper "Multilevel Visual Analysis of Aggregate Geo-Networks" by Deng et al. The paper addresses the challenge of visualizing multiple geo-networks (networks with geographically positioned nodes) simultaneously without creating visual clutter.

Visualization Technique

The implemented technique uses a metro map-inspired stacking approach where:

• Multiple networks sharing the same geographic edges are stacked parallel to each other (like metro lines sharing a track)
• A gray background layer shows all unique connections across all networks
• Colored foreground edges represent individual networks with distinct colors
• Bézier curves are used for edge routing to reduce visual clutter at nodes
• Interactive controls allow filtering, toggling visibility, and adjusting visual parameters

Algorithm Summary

The visualization pipeline consists of several preprocessing steps followed by interactive rendering:

1. Background Aggregation

Computes the union of all network edges to create a single background graph that shows the overall connectivity structure. This provides context for the individual networks displayed on top.

2. Crossing Minimization

Determines the stacking order of networks at each shared edge to minimize visual crossings. The implementation uses:

• Barycenter heuristic for initial ordering
• Simulated Annealing for global optimization
• Explicit crossing detection and counting at each node

The paper proposes an ILP (Integer Linear Programming) formulation; this implementation uses a heuristic approach for better performance.

3. K-Coloring

Assigns distinguishable colors to networks considering:

• Adjacent networks (sharing stacking positions)
• Intersecting networks (having crossings)
• Co-edge networks (sharing the same background edge)

Uses a greedy graph coloring approach with originally 8 distinguishable colors from the Tableau-10 palette. Since the reimplementation of the paper only contains 5 datasets, the coloring algorithm was adjusted to use 4 colors from the Tableau-10 palette.

4. Smart Bézier Routing

Edges are rendered as Bézier curves with intelligent direction selection:

• Tests both curve directions (left and right of straight line)
• Detects potential node collisions along the curve
• Falls back to straight lines when both directions would cause collisions
• Short edges (< 30px on screen) use straight lines for clarity

Installation

Prerequisites

• Python 3.8+ with pip
• Node.js (optional, for development)
• A modern web browser (Chrome, Firefox, Edge, Safari)

Setup

1. Clone the repository:

git clone https://gitlab.tuwien.ac.at/e193-02-visvu-students/visvu-2025-deng_2023-chang-rieger

2. Install Python dependencies:

pip install networkx numpy scipy

No additional npm packages are required for the visualization (vanilla JavaScript).

3. Prepare your data:

Place your input network data in the networks/basic/ directory. The expected format is a JSON file with the following structure:

{
  "networks": [
    {
      "id": "network_1",
      "nodes": [
        {"key": "node_id", "label": "Node Label", "x": 10.5, "y": 48.2}
      ],
      "edges": [
        {"source": "node_id_1", "target": "node_id_2", "weight": 0.75}
      ]
    }
  ]
}

• x: Longitude (geographic coordinate)
• y: Latitude (geographic coordinate)
• weight: Optional edge weight (0-1 range recommended)

4. Run the preprocessing pipeline:

cd preprocessing
python run_pipeline.py

This executes all preprocessing steps and outputs networks_final.json.

5. Start the visualization server:

cd visualization
python -m http.server 8000

6. Open in browser:

Navigate to http://localhost:8000

Usage Guide

Map Configuration

To display a geographic map background, create a map_config.json file in the visualization/ directory:

{
  "image": "worldmap.png",
  "bounds": {
    "min_lon": -180,
    "max_lon": 180,
    "min_lat": -90,
    "max_lat": 90
  }
}

Place the corresponding map image (PNG, JPG, or SVG) in the same directory. A default world map is already existing in the repository and used by the visualization.

Interactive Controls

Header Controls

Control	Description
Show Map	Toggle the geographic map background on/off
Show City Names	Toggle node labels
Line Width	Adjust the thickness of network edges (1-10)
Gap	Adjust spacing between stacked edges (0-5)

Legend Panel (Right Side)

Element	Description
Toggle All	Show/hide all networks at once
Background	Toggle the gray background edge layer
Network Items	Click individual networks to show/hide them
Edge Weight Filter	Dual-slider to filter edges by weight (0-1 range)
Reset Filter	Reset weight filter to show all edges

Mouse Interaction

Action	Description
Drag	Pan the visualization
Scroll	Zoom in/out
Hover on Node	Highlight all connected edges and neighboring nodes

Adjustable Parameters

Preprocessing Parameters

Edit the Python scripts in preprocessing/ to adjust:

Parameter	File	Default	Description
sa_iterations	crossing_minimization_crossingaware.py	1000	Simulated annealing iterations
initial_temp	crossing_minimization_crossingaware.py	10.0	SA initial temperature
cooling_rate	crossing_minimization_crossingaware.py	0.995	SA cooling rate
k	k_coloring.py	8	Number of distinct colors

Rendering Parameters

Edit MetroRenderer.js to adjust:

Parameter	Default	Description
EDGE_WIDTH	3	Base edge width in pixels
STACK_GAP	1	Gap between stacked edges
NODE_RADIUS	6	Node circle radius
BG_OPACITY	0.7	Background layer opacity
BEZIER_CURVATURE	0.15	Curvature factor for Bézier curves

Project Structure

visvu-2025-deng_2023-chang-rieger/
├── preprocessing/
│   ├── run_pipeline.py              # Main pipeline script
│   ├── background_aggregation.py    # Step 0: Aggregate background
│   ├── crossing_minimization_improved.py  # Step 1: Minimize crossings
│   ├── k_coloring.py                # Step 2: Assign colors
├── visualization/
│   ├── index.html                   # Main visualization page
│   ├── MetroRenderer.js             # Canvas-based renderer
│   ├── map_config.json              # Map configuration
│   └── worldmap.png                 # Background map image
├── networks/
│   └── basic/
│       ├── networks.json            # Input data
│       └── networks_final.json      # Processed output
└── docs/
    └── README.md                    # This documentation

Implementation Status

Feature	Status	Notes
Background Aggregation	✅ Complete	Section 4.1
Hierarchical Clustering	❌ Not implemented	Section 4.2.1, Equations 1-2
Crossing Minimization	⚠️ Partial	Heuristic instead of ILP
K-Coloring	✅ Complete	Section 4.2.3
Metro-style Rendering	✅ Complete	Stacked parallel edges
Bézier Edge Routing	⚠️ Partial	Smart collision avoidance
Geographic Map Background	✅ Complete	PNG/SVG support
Weight-based Filtering	✅ Complete	Interactive dual-slider
Node Hover Highlighting	✅ Complete	Connected edges/nodes
Drill-down Interaction	❌ Not implemented	Split/Merge UI

References

Original Paper

Deng, Z., Chen, S., Xie, X., Sun, G., Xu, M., Weng, D., & Wu, Y. (2024). Multilevel Visual Analysis of Aggregate Geo-Networks. IEEE Transactions on Visualization and Computer Graphics, 30(7), 3135-3150.

DOI: 10.1109/TVCG.2022.3229953

Key Concepts from Paper

• Section 4.1: Basic design with background/foreground layers and metro-style edge stacking
• Section 4.2.1: Level-of-detail rendering via hierarchical clustering
• Section 4.2.2: Progressive crossing minimization using Integer Linear Programming (ILP)
• Section 4.2.3: K-coloring algorithm with four constraint types (adjacency, intersecting, co-edge, hierarchy)

Libraries and Resources Used

• NetworkX: Graph algorithms for Python (networkx.org)
• SciPy: Scientific computing, used for hierarchical clustering (scipy.org)
• PuLP: Linear programming solver for ILP-based crossing minimization (coin-or.github.io/pulp)
• Tableau-10 Colors: Perceptually distinguishable color palette (8 colors used)
• OpenStreetMap: Geographic map tiles (openstreetmap.org)