Large-Scale Graph Layouts & 2D Visualization with Zog ⚡

Mix.install([
  # {:zog, "~> 0.6.0"},
  {:zog, path: Path.expand("~/repos/elixir/zog")},
  {:kino, "~> 0.12"},
  {:jason, "~> 1.4"}
])

1. Overview & Zog Layout Architecture

Network visualization is critical for understanding graph topologies, community modularity, and structural clustering. Traditional BEAM graph layouts either rely on slow pure-Elixir iterative loops or require external command-line tools like Graphviz.

Zog provides high-performance, native 2D layout algorithms backed by Zig engines:

1. Pivot-MDS (High-Dimensional Embedding): Sub-second classical multidimensional scaling using distances from $k$ well-separated pivot nodes ($O(k(V + E))$). Capable of embedding $100,000+$ nodes in under a second.
2. Multi-Level Coarsening: Macro-layout via Louvain/Leiden super-nodes, Vogel/sunflower spiral prolongation, and local Barnes-Hut force refinement.
3. Spring / Force-Directed: Fruchterman-Reingold physical model with exact $O(V^2)$ repulsion or $O(V \log V)$ Barnes-Hut quadtree spatial acceleration.
4. Geometric Layouts: Uniform Circular, Shell (concentric $k$-core shells), Multipartite (hierarchical layers), Grid, and Random.
5. Planar Barycentric Embedding: Tutte's planar embedding via Gauss-Seidel relaxation.
6. Packed Binary Streaming: Compact little-endian float buffers (<<x::float-32, y::float-32>>) suitable for WebGL / Canvas / Sigma.js integrations.

2. Ingesting Real-World Social Circles (SNAP ego-Facebook)

Let's test our layout engine on the SNAP ego-Facebook social network (4,039 nodes, 88,234 edges). If the dataset is not already present, we download and decompress it:

{:ok, txt_path} = Zog.Dataset.fetch_snap(:facebook)

Kino.Markdown.new("""
> **Dataset Ready**: `#{txt_path}` (~4,039 users, 88,234 friendship connections).
""")

Now let's ingest the graph into native memory:

alias Zog.IO, as: ZogIO
alias Zog.ResourceGraph

{load_time_micro, graph} =
  :timer.tc(fn ->
    ZogIO.load(txt_path, directed: false, integer_labels: true)
  end)

node_count = ResourceGraph.node_count(graph)
edge_count = ResourceGraph.edge_count(graph)
undirected_edges = div(edge_count, 2)

Kino.Markdown.new("""
### ⚡ Graph Loaded into Native Memory
- **Nodes**: `#{node_count}`
- **Undirected Friendship Connections**: `#{undirected_edges}`
- **Stored Directed Half-Edges**: `#{edge_count}`
- **Native Ingestion Time**: **#{Float.round(load_time_micro / 1000, 2)} ms**
""")

3. Detecting Communities for Cluster Coloring

To visualize structural communities, let's partition the network using native Louvain modularity optimization:

{time_louvain_micro, communities} =
  :timer.tc(fn ->
    ResourceGraph.louvain(graph)
  end)

# Find top communities
top_comms =
  communities
  |> Enum.group_by(fn {_node, comm_id} -> comm_id end)
  |> Enum.map(fn {comm_id, members} -> {comm_id, length(members)} end)
  |> Enum.sort_by(&elem(&1, 1), :desc)

Kino.Markdown.new("""
### 🎨 Community Detection (Louvain)
- **Time**: **#{Float.round(time_louvain_micro / 1000, 2)} ms**
- **Discovered Communities**: `#{length(top_comms)}`
- **Top 5 Largest Circles**: `#{inspect(Enum.take(top_comms, 5))}`
""")

4. Benchmark: Layout Engine Performance Comparison

Let's benchmark the layout algorithms side-by-side on this 4,039-node network:

# 1. Circular
{t_circ, _} = :timer.tc(fn -> ResourceGraph.layout_circular(graph) end)

# 2. Shell (grouped by Louvain community)
{t_shell, _} =
  :timer.tc(fn ->
    shells =
      communities
      |> Enum.group_by(fn {_node, c} -> c end, fn {node, _} -> node end)
      |> Map.values()

    ResourceGraph.layout_shell(graph, shells)
  end)

# 3. Pivot-MDS (k = 50 pivots)
{t_pmds, _} =
  :timer.tc(fn ->
    ResourceGraph.layout_pivot_mds(graph, pivots: 50, seed: 42)
  end)

# 4. Multi-Level Coarsening (Louvain macro + 20 Barnes-Hut refine iterations)
{t_ml, _} =
  :timer.tc(fn ->
    ResourceGraph.layout_multi_level(graph, refine_iterations: 20, seed: 42)
  end)

# 5. Spring with Barnes-Hut Quadtree (50 iterations)
{t_bh, _} =
  :timer.tc(fn ->
    ResourceGraph.layout_spring(graph, barnes_hut: true, iterations: 50, seed: 42)
  end)

benchmark_rows = [
  %{
    "Algorithm" => "Pivot-MDS (HDE, 50 pivots)",
    "Execution Time (ms)" => Float.round(t_pmds / 1000, 2),
    "Throughput (nodes/s)" => round(node_count / (t_pmds / 1_000_000)),
    "Complexity" => "O(k · (V + E))",
    "Best For" => "Instant macro projection for massive networks (10⁵+)"
  },
  %{
    "Algorithm" => "Multi-Level Coarsening",
    "Execution Time (ms)" => Float.round(t_ml / 1000, 2),
    "Throughput (nodes/s)" => round(node_count / (t_ml / 1_000_000)),
    "Complexity" => "O(C² + V log V)",
    "Best For" => "Untangled modular cluster separation"
  },
  %{
    "Algorithm" => "Spring (Barnes-Hut Quadtree, 50 iters)",
    "Execution Time (ms)" => Float.round(t_bh / 1000, 2),
    "Throughput (nodes/s)" => round(node_count / (t_bh / 1_000_000)),
    "Complexity" => "O(iters · V log V)",
    "Best For" => "Equilibrium force-directed physical models"
  },
  %{
    "Algorithm" => "Shell Layout (by Community)",
    "Execution Time (ms)" => Float.round(t_shell / 1000, 2),
    "Throughput (nodes/s)" => round(node_count / (t_shell / 1_000_000)),
    "Complexity" => "O(V)",
    "Best For" => "Concentric hierarchy and k-core visualization"
  },
  %{
    "Algorithm" => "Circular Layout",
    "Execution Time (ms)" => Float.round(t_circ / 1000, 2),
    "Throughput (nodes/s)" => round(node_count / (t_circ / 1_000_000)),
    "Complexity" => "O(V)",
    "Best For" => "Uniform chord / circular overview"
  }
]

Kino.Layout.grid(
  [
    Kino.Markdown.new("""
    ### 🏆 2D Layout Benchmark Results (N = 4,039, E = 88,234)
    """),
    Kino.DataTable.new(benchmark_rows, name: "Layout Performance Benchmark")
  ],
  columns: 1
)

5. Packed Binary Streaming (format: :binary)

Zog supports direct binary coordinate output. Instead of constructing $4,000+$ Elixir map keys and float tuples, Zig returns a single contiguous memory buffer containing packed little-endian 32-bit floats:

$$\text{Buffer} = \Big\langle \underbrace{x_0, y_0}{8\text{ bytes}}, \underbrace{x_1, y_1}{8\text{ bytes}}, \dots, \underbrace{x_{N-1}, y_{N-1}}_{8\text{ bytes}} \Big\rangle$$

bin = ResourceGraph.layout_pivot_mds(graph, pivots: 50, format: :binary)

byte_len = byte_size(bin)
expected_len = node_count * 8

Kino.Markdown.new("""
### 📦 Binary Streaming Verification
- **Packed Buffer Size**: `#{byte_len}` bytes (exact match with `#{node_count} × 8 bytes` = `#{expected_len}`).
- **Memory Footprint**: Only **#{Float.round(byte_len / 1024, 2)} KB**!
- **Compact Binary Format**: Decodable in JavaScript via `new Float32Array(buffer)` without coordinate JSON parsing.
""")

6. Interactive Livebook Canvas Visualizer

Let's build an interactive HTML5 Canvas visualizer. Select the layout algorithm below to re-render the network in real-time:

layout_selector =
  Kino.Input.select(
    "Layout Algorithm",
    [
      multi_level: "Multi-Level Coarsening (Louvain + Barnes-Hut)",
      pivot_mds: "Pivot-MDS (High-Dimensional Embedding)",
      spring: "Spring Force-Directed (Barnes-Hut, 30 iters)",
      circular: "Circular Layout",
      shell: "Shell Layout (by Community)"
    ]
  )

Kino.Layout.grid([layout_selector], columns: 1)

selected_algo = Kino.Input.read(layout_selector)

# Canvas dimensions
canvas_w = 800
canvas_h = 600

# Compute layout
{layout_time_micro, pos_map} =
  :timer.tc(fn ->
    case selected_algo do
      :multi_level ->
        ResourceGraph.layout_multi_level(graph,
          width: canvas_w - 80,
          height: canvas_h - 80,
          center: {canvas_w / 2, canvas_h / 2},
          refine_iterations: 20,
          seed: 42
        )

      :pivot_mds ->
        ResourceGraph.layout_pivot_mds(graph,
          pivots: 50,
          width: canvas_w - 80,
          height: canvas_h - 80,
          center: {canvas_w / 2, canvas_h / 2},
          seed: 42
        )

      :spring ->
        ResourceGraph.layout_spring(graph,
          barnes_hut: true,
          iterations: 30,
          width: canvas_w - 80,
          height: canvas_h - 80,
          center: {canvas_w / 2, canvas_h / 2},
          seed: 42
        )

      :circular ->
        ResourceGraph.layout_circular(graph,
          radius: min(canvas_w, canvas_h) * 0.42,
          center: {canvas_w / 2, canvas_h / 2}
        )

      :shell ->
        shells =
          communities
          |> Enum.group_by(fn {_node, c} -> c end, fn {node, _} -> node end)
          |> Map.values()

        ResourceGraph.layout_shell(graph, shells,
          center: {canvas_w / 2, canvas_h / 2}
        )
    end
  end)

Zog.Kino.render(graph, pos_map,
  edge_file: txt_path,
  color_by: communities,
  title: "Visualizing #{node_count} Nodes & 88,234 Edges",
  subtitle: "(Algorithm: #{selected_algo}) • Layout computed in #{Float.round(layout_time_micro / 1000, 2)} ms",
  width: canvas_w,
  height: canvas_h
)

7. Ultra-Scale Demo: Pivot-MDS on 50,000 Nodes

How does Pivot-MDS perform on an order-of-magnitude larger network? Let's generate a synthetic 50,000-node ring-plus-chord graph and run Pivot-MDS:

large_n = 50_000

IO.puts("Generating synthetic graph with #{large_n} nodes...")

# Build a deterministic ring + modular chord graph in SoA
{t_gen, large_graph} =
  :timer.tc(fn ->
    Enum.reduce(0..(large_n - 1), Zog.undirected(), fn i, acc ->
      # Ring topology
      acc = Zog.add_edge(acc, i, rem(i + 1, large_n), 1.0)
      # Random chords
      target = rem(i * 7919 + 31, large_n)
      Zog.add_edge(acc, i, target, 1.0)
    end)
  end)

IO.puts("Running Pivot-MDS (k = 30 pivots) on #{large_n} nodes...")

{t_pmds_large, pos_large} =
  :timer.tc(fn ->
    Zog.layout_pivot_mds(large_graph, pivots: 30, format: :binary, seed: 42)
  end)

# Extract edges for GPU line rendering
{from_ids, to_ids, _} = Zog.to_edge_arrays(large_graph)

large_edges_bin =
  Enum.zip(from_ids, to_ids)
  |> Enum.filter(fn {u, v} -> u < v end)
  |> Enum.map(fn {u, v} -> <<u::unsigned-32-little, v::unsigned-32-little>> end)
  |> IO.iodata_to_binary()

b64_large_edges = Base.encode64(large_edges_bin)
large_edge_count = div(byte_size(large_edges_bin), 8)

Kino.Markdown.new("""
### 🚀 Pivot-MDS on 50,000 Nodes & #{large_edge_count} Edges
- **Graph Generation**: `#{Float.round(t_gen / 1000, 2)} ms`
- **Pivot-MDS Execution**: **#{Float.round(t_pmds_large / 1000, 2)} ms**
- **Throughput**: **#{round(large_n / (t_pmds_large / 1_000_000))} nodes/sec**
- **Result**: Complete 2D coordinates embedded in **sub-second time**!
""")

8. WebGL Hardware-Accelerated Rendering (50,000 Nodes & 100,000 Edges at 60 FPS)

Traditional DOM or SVG elements choke when rendering more than 1,000 elements. With Zog's format: :binary, the 50,000 {x, y} float coordinates and 100,000 edge indices can be represented as compact buffers for WebGL VBO/EBO upload:

webgl_canvas_w = 800
webgl_canvas_h = 600

# Stream packed binary coordinates and edge indices directly into GPU VBO/EBO
Zog.Kino.render(large_graph, pos_large,
  edges: large_edges_bin,
  engine: :webgl,
  title: "WebGL GPU Shaders: 50,000 Nodes & #{large_edge_count} Edges",
  subtitle: "Compact VBO/EBO Buffers • 60 FPS GPU Pipeline",
  width: webgl_canvas_w,
  height: webgl_canvas_h
)

9. Clean Native Memory

Always release native allocations when done:

ResourceGraph.destroy(graph)
Kino.Markdown.new("✓ Native memory successfully freed.")