nx_pagerank.nx source
↩ module page · 57 lines · 2839 B
1// nx_pagerank.nx -- LIB: sovereign PageRank over a web-graph edge list. The authority signal weak indie indexes
2// (Mojeek/Brave) lack -- Common Crawl's WAT links are a 13.4B-edge graph; this is what turns "a bigger index" into
3// "a BETTER index" (link-authority ranking + anti-slop). Power iteration, damping 0.85, integer fixed-point (ranks are
4// parts-per-PR_SCALE, conserved to ~PR_SCALE), dangling-node redistribution (standard formulation). Fuses as an
5// authority prior into nx_rank_fused. BUILT + gated NOW on synthetic graphs with known ranks; RUNS at NAS scale over
6// the real CC web graph later (build-now / run-on-NAS, per the foundational roadmap). No float (nx is integer).
7// license_tier: ORIGINAL
8import "nx_syscalls.nx"
9
10const PR_SCALE: i64 = 1000000000 // ranks are ppb, sum ~= PR_SCALE
11const PR_D_NUM: i64 = 85 // damping 0.85 = 85/100
12const PR_D_DEN: i64 = 100
13
14// compute PageRank into rank[N] (caller-allocated). edges = parallel efrom/eto (M directed edges j->i). iters = power
15// iterations (small graphs converge in ~30-60; use 100 for margin). Returns 0 ok, -1 bad args.
16func pr_compute(N: i64, M: i64, efrom: *i64, eto: *i64, rank: *i64, iters: i64) -> i64 {
17 if N <= 0 { return 0 - 1 }
18 let outdeg: *i64 = sys_mmap(8 * N)
19 var i: i64 = 0
20 while i < N { outdeg[i] = 0; i = i + 1 }
21 var e: i64 = 0
22 while e < M { let f: i64 = efrom[e]; outdeg[f] = outdeg[f] + 1; e = e + 1 }
23 i = 0
24 while i < N { rank[i] = PR_SCALE / N; i = i + 1 }
25 let nr: *i64 = sys_mmap(8 * N)
26 var it: i64 = 0
27 while it < iters {
28 // dangling mass (nodes with no out-links) is redistributed to all nodes, damped
29 var dang: i64 = 0
30 i = 0
31 while i < N { if outdeg[i] == 0 { dang = dang + rank[i] } i = i + 1 }
32 let teleport: i64 = ((PR_D_DEN - PR_D_NUM) * (PR_SCALE / N)) / PR_D_DEN // (1-d)*SCALE/N
33 let dshare: i64 = (PR_D_NUM * (dang / N)) / PR_D_DEN // d*dang/N to every node
34 let base: i64 = teleport + dshare
35 i = 0
36 while i < N { nr[i] = base; i = i + 1 }
37 e = 0
38 while e < M {
39 let j: i64 = efrom[e]; let t: i64 = eto[e]
40 if outdeg[j] > 0 { nr[t] = nr[t] + (PR_D_NUM * (rank[j] / outdeg[j])) / PR_D_DEN }
41 e = e + 1
42 }
43 i = 0
44 while i < N { rank[i] = nr[i]; i = i + 1 }
45 it = it + 1
46 }
47 return 0
48}
49
50// index of the max-rank node (the highest-authority page).
51func pr_argmax(rank: *i64, N: i64) -> i64 {
52 var mi: i64 = 0; var i: i64 = 1
53 while i < N { if rank[i] > rank[mi] { mi = i } i = i + 1 }
54 return mi
55}
56// sum of all ranks (should stay ~PR_SCALE -- conservation check).
57func pr_sum(rank: *i64, N: i64) -> i64 { var s: i64 = 0; var i: i64 = 0; while i < N { s = s + rank[i]; i = i + 1 } return s }