Web Graph & The Bow-Tie Model with Zog ⚡

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

1. Overview: The Anatomy of the Web Graph

In 2000, Andrei Broder and colleagues published a landmark discovery in network science: "Graph structure in the web" (Computer Networks, 33(1-6), 2000).

Rather than being a uniform, randomly connected mesh, the World Wide Web's directed hyperlink structure organizes into a macroscopic Bow-Tie:

graph LR
    IN["IN Component\n(Pages that reach Core)"] --> SCC["SCC Core\n(Giant Strongly Connected Component)"]
    SCC --> OUT["OUT Component\n(Pages reached from Core)"]
    IN --> TUBES["TUBES\n(Bypass Core)"] --> OUT
    IN -.-> T1["TENDRILS\n(Hanging off IN)"]
    T2["TENDRILS\n(Feeding into OUT)"] -.-> OUT
    DISC["DISCONNECTED\n(Isolated components & islands)"]

The Six Bow-Tie Components:

1. SCC (Core): The central giant strongly connected component. Every page in the core can reach every other page via directed hyperlinks.
2. IN: Pages that can reach the SCC along directed paths, but cannot be reached from it (e.g., new websites, specialized directories).
3. OUT: Pages that can be reached from the SCC, but cannot reach back into it (e.g., corporate websites, leaf pages).
4. TUBES: Direct pathways that lead from IN to OUT without ever passing through the SCC.
5. TENDRILS: Pages hanging off IN (reachable from IN but not reaching SCC or OUT), or feeding into OUT (reaching OUT but not from IN or SCC).
6. DISCONNECTED: Separate components and unlinked web pages with no directed paths to or from the core.

In this notebook, we analyze the Stanford University Web Graph (web-Stanford) from SNAP, containing 281,903 web pages and 2,312,497 hyperlinks.

2. Ingestion & Zero-Copy Native Allocation

Let's download, decompress, and remap web-Stanford.txt.gz using Zog.Dataset:

{:ok, remapped_path} = Zog.Dataset.fetch_snap(:stanford_web)

Kino.Markdown.new("""
> **Dataset Ready**: `#{remapped_path}` with dense zero-based IDs (~32 MB uncompressed directed edge list).
""")

Now we ingest the remapped directed edge list into Zog's native ArrayGraph (SoA layout):

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

beam_mem_before = :erlang.memory(:total)

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

beam_mem_after = :erlang.memory(:total)
beam_mem_delta_mb = (beam_mem_after - beam_mem_before) / (1024 * 1024)
load_ms = time_load_micro / 1000

node_count = ResourceGraph.node_count(graph)
edge_count = ResourceGraph.edge_count(graph)

Kino.Markdown.new("""
### ⚡ Web Graph Ingestion Summary
- **Nodes (Web Pages)**: `#{node_count}`
- **Edges (Hyperlinks)**: `#{edge_count}`
- **Native Parsing & Ingestion Time**: **#{Float.round(load_ms, 2)} ms**
- **BEAM Heap Overhead**: **#{Float.round(beam_mem_delta_mb, 2)} MB** *(zero garbage collection pressure!)*
""")

3. SNAP Ground Truth Cross-Check

Let's compute strongly and weakly connected components and verify our calculations against SNAP's published ground truth:

{time_scc_micro, scc_assignments} =
  :timer.tc(fn -> ResourceGraph.strongly_connected_components(graph, raw: true) end)

{time_wcc_micro, wcc_assignments} =
  :timer.tc(fn -> ResourceGraph.weakly_connected_components(graph, raw: true) end)

scc_freq = Enum.frequencies(scc_assignments)
largest_scc = scc_freq |> Map.values() |> Enum.max()

wcc_freq = Enum.frequencies(wcc_assignments)
largest_wcc = wcc_freq |> Map.values() |> Enum.max()

scc_ms = time_scc_micro / 1000
wcc_ms = time_wcc_micro / 1000

exact_status = fn actual, expected ->
  if actual == expected, do: "✓ Exact Match", else: "⚠ Expected #{expected}"
end

verification_table = [
  %{
    "Metric" => "Nodes (Pages)",
    "SNAP Published" => "281,903",
    "Zog Computed" => "#{node_count}",
    "Status" => exact_status.(node_count, 281_903)
  },
  %{
    "Metric" => "Edges (Hyperlinks)",
    "SNAP Published" => "2,312,497",
    "Zog Computed" => "#{edge_count}",
    "Status" => exact_status.(edge_count, 2_312_497)
  },
  %{
    "Metric" => "Nodes in Largest WCC",
    "SNAP Published" => "255,265 (90.6%)",
    "Zog Computed" => "#{largest_wcc} (#{Float.round(largest_wcc / node_count * 100, 1)}%)",
    "Status" => exact_status.(largest_wcc, 255_265)
  },
  %{
    "Metric" => "Nodes in Largest SCC (Core)",
    "SNAP Published" => "150,532 (53.4%)",
    "Zog Computed" => "#{largest_scc} (#{Float.round(largest_scc / node_count * 100, 1)}%)",
    "Status" => exact_status.(largest_scc, 150_532)
  }
]

Kino.Layout.grid(
  [
    Kino.Markdown.new("""
    ### 🔬 Ground Truth Cross-Check
    - **SCC Execution Time (Tarjan)**: `#{Float.round(scc_ms, 2)} ms`
    - **WCC Execution Time (Union-Find)**: `#{Float.round(wcc_ms, 2)} ms`
    """),
    Kino.DataTable.new(verification_table, name: "SNAP Ground Truth vs Zog")
  ],
  columns: 1
)

4. Native Bow-Tie Decomposition

Now we perform full Bow-Tie decomposition using ResourceGraph.bow_tie_decomposition/1. This performs graph transposition and multi-source forward/backward BFS passes in native Zig:

{time_bt_micro, bowtie} =
  :timer.tc(fn ->
    ResourceGraph.bow_tie_decomposition(graph)
  end)

bt_ms = time_bt_micro / 1000
total_pages = node_count

pct = fn count ->
  "#{Float.round(count / total_pages * 100, 2)}%"
end

bowtie_rows = [
  %{
    "Component" => "SCC (Central Core)",
    "Role in Web" => "Mutually reachable giant core of Stanford.edu",
    "Page Count" => bowtie.scc_count,
    "% of Web Graph" => pct.(bowtie.scc_count)
  },
  %{
    "Component" => "OUT",
    "Role in Web" => "Reachable from Core, but no links back",
    "Page Count" => bowtie.out_count,
    "% of Web Graph" => pct.(bowtie.out_count)
  },
  %{
    "Component" => "IN",
    "Role in Web" => "Links into Core, but unreachable from it",
    "Page Count" => bowtie.in_count,
    "% of Web Graph" => pct.(bowtie.in_count)
  },
  %{
    "Component" => "TENDRILS",
    "Role in Web" => "Branches hanging off IN or leading into OUT",
    "Page Count" => bowtie.tendrils_count,
    "% of Web Graph" => pct.(bowtie.tendrils_count)
  },
  %{
    "Component" => "DISCONNECTED",
    "Role in Web" => "Isolated departmental pages & disconnected islands",
    "Page Count" => bowtie.disconnected_count,
    "% of Web Graph" => pct.(bowtie.disconnected_count)
  },
  %{
    "Component" => "TUBES",
    "Role in Web" => "Direct highway paths connecting IN to OUT bypassing Core",
    "Page Count" => bowtie.tubes_count,
    "% of Web Graph" => pct.(bowtie.tubes_count)
  }
]

Kino.Layout.grid(
  [
    Kino.Markdown.new("""
    ### 🎀 Full Bow-Tie Decomposition
    - **Total Algorithm Runtime**: **#{Float.round(bt_ms, 2)} ms**!
    - **Key Structural Finding**: Over **53.4%** of the Stanford web graph lives in the strongly connected core. **24.0%** of pages are terminal leaves (`OUT`), while **11.6%** are upstream entry points (`IN`).
    """),
    Kino.DataTable.new(bowtie_rows, name: "Bow-Tie Model Distribution")
  ],
  columns: 1
)

5. Interactive Webpage Inspector

Select any page ID (from 1 to 281,903) to inspect its exact position in the Stanford web graph hierarchy:

page_input = Kino.Input.number("Stanford Page ID", default: 89_073)
Kino.Layout.grid([page_input], columns: 1)

page_value = Kino.Input.read(page_input)
whole_number? = fn value -> is_integer(value) or (is_float(value) and value == trunc(value)) end

tag_name = fn
  0 -> {"DISCONNECTED", "Isolated or disconnected from main web components"}
  1 -> {"SCC (CORE)", "Part of the central strongly connected core"}
  2 -> {"IN", "Upstream page linking into the core"}
  3 -> {"OUT", "Downstream page reachable from the core"}
  4 -> {"TUBES", "Transit page routing directly from IN to OUT"}
  5 -> {"TENDRILS", "Peripheral branch hanging off IN or feeding into OUT"}
  _ -> {"UNKNOWN", "Invalid page"}
end

cond do
  not whole_number?.(page_value) ->
    Kino.Markdown.new("⚠️ Please enter a whole-number page ID.")

  page_value < 1 or page_value > node_count ->
    Kino.Markdown.new("⚠️ Please enter a valid page ID between `1` and `#{node_count}`.")

  true ->
    page_id = trunc(page_value)
    native_id = page_id - 1
    <<tag::8>> = binary_part(bowtie.tags, native_id, 1)
    {component_label, explanation} = tag_name.(tag)

    degrees = ResourceGraph.node_degrees(graph)
    out_deg = Enum.at(degrees, native_id, 0)

    Kino.Markdown.new("""
    ### 📄 Page `#{page_id}` Diagnostics
    - **Native Node ID**: `#{native_id}`
    - **Bow-Tie Classification**: `#{component_label}`
    - **Out-Degree (Hyperlinks Out)**: `#{out_deg}`
    - **Structural Context**: #{explanation}
    """)
end

6. PageRank & Web Authority Discovery

Stanford was the birthplace of Google and the PageRank algorithm (Page & Brin, 1998). Let's run PageRank natively on the full 281,903-page web graph to find the most authoritative pages:

{time_pr_micro, pageranks} =
  :timer.tc(fn ->
    ResourceGraph.pagerank(graph, raw: true)
  end)

pr_ms = time_pr_micro / 1000

top_pages =
  pageranks
  |> Enum.with_index()
  |> Enum.sort_by(&elem(&1, 0), :desc)
  |> Enum.take(10)
  |> Enum.with_index(1)
  |> Enum.map(fn {{score, native_id}, rank} ->
    <<tag::8>> = binary_part(bowtie.tags, native_id, 1)
    {comp, _} = tag_name.(tag)

    %{
      "Rank" => rank,
      "Page ID" => native_id + 1,
      "Native Node ID" => native_id,
      "PageRank Score" => Float.round(score, 6),
      "Bow-Tie Component" => comp
    }
  end)

Kino.Layout.grid(
  [
    Kino.Markdown.new("""
    ### 🏆 Top 10 Most Authoritative Pages (PageRank)
    - **Computation Time**: **#{Float.round(pr_ms, 2)} ms** across 281,903 nodes and 2.3M edges!
    - Notice that the highest-ranked pages naturally belong to the **SCC (Core)**!
    """),
    Kino.DataTable.new(top_pages, name: "Top Stanford Web Pages")
  ],
  columns: 1
)

7. Clean Native Memory

Always release native allocations when done:

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