PageRank

一、直观理解：随机冲浪者会在哪些页停留更久

PageRank 最初为网页排序设计：重要页面被许多重要页面链接。可以想象一个上网者：

• 以概率 $1-d$ 沿着当前页的出链随机点击；
• 以概率 $d$ 传送到任意页面（阻尼/传送，避免陷阱与死胡同）。

长期停留频率就是 PageRank 分数。它是有向图上带重启的随机游走平稳分布。

公式常见写法：

$$\mathbf{r}=d\frac{\mathbf{1}}{n}+(1-d)P^\mathsf{T}\mathbf{r}$$

（传送概率写法因文献而异，注意 $d$ 定义。）更常见：

$$PR(i)=\frac{1-\alpha}{n}+\alpha\sum_{j\to i}\frac{PR(j)}{\mathrm{outdeg}(j)}$$

$\alpha$ 通常 0.85。

二、适用场景与优缺点

类型	说明
适用场景	有向引用/超链接/关注网络；节点重要性排序；反作弊的基线中心性。
核心优点	利用全局结构；对“被重要者指向”敏感；幂迭代易实现；有阻尼保证不可约非周期（在传送下）。
局限与缺点	无向图需改定义；权重与时间敏感性需扩展；操纵链接可作弊；分数解释是游走停留而非因果权威。

三、核心原理

1. 构造行随机矩阵 $P$：若 $j$ 出度 $k_j>0$，$P_{ji}=1/k_j$ 当 $j\to i$；
2. 悬挂节点（出度 0）整行改为 $1/n$；
3. Google 矩阵 $G=\alpha P+(1-\alpha)\mathbf{1}\mathbf{1}^\mathsf{T}/n$；
4. 求 $G^\mathsf{T} r=r$（主特征/幂迭代）。

与特征向量中心性关系：PageRank 是加了传送与出度归一的变体，更适合有向网页图。

四、关键决策

1. $\alpha$

0.85 常用；做敏感性 $\alpha\in[0.7,0.95]$。

2. 有无边权

可用加权出链比例。

3. 个性化 PageRank

传送向量非均匀，用于局部重要或推荐。

4. 验证

分数和为 1；小图手算；与入度排序对照。

五、MATLAB 示例

% 有向图 1->2,1->3,2->3,3->1,3->4,4->3
s = [1 1 2 3 3 4];
t = [2 3 3 1 4 3];
n = 4;
A = zeros(n);
for e = 1:numel(s)
    A(s(e), t(e)) = 1;
end

alpha = 0.85;
% 行随机
P = zeros(n);
outdeg = sum(A, 2);
for i = 1:n
    if outdeg(i)==0
        P(i,:) = 1/n;
    else
        P(i,:) = A(i,:) / outdeg(i);
    end
end
Gmat = alpha*P + (1-alpha)*ones(n)/n;

% 幂迭代
r = ones(n,1)/n;
for it = 1:100
    r_new = Gmat' * r;
    if norm(r_new - r,1) < 1e-12, break; end
    r = r_new;
end
r = r / sum(r);
disp(table((1:n)', r, "VariableNames", {'node','PageRank'}));

% MATLAB digraph 中心性（若支持）
Gd = digraph(s,t);
try
    pr = centrality(Gd, "pagerank", "FollowProbability", alpha);
    disp("centrality pagerank:"); disp(pr);
catch
    disp("使用手写 PageRank 结果即可");
end

figure;
p = plot(Gd, "Layout", "layered");
p.MarkerSize = 10 + 40*r/max(r);
title("节点大小 ∝ PageRank");

六、如何解释结果

1. 边方向含义（引用/关注/超链）；
2. $\alpha$ 与悬挂节点处理；
3. 排序表与 Top 节点解释；
4. 与入度中心性差异；
5. 敏感性；
6. 应用边界（排序≠真理）。

七、常见误区

1. 无向图直接当网页规则用

需明确对称化或改指标。

2. 忽略悬挂点

概率泄漏。

3. 把 PR 当访问量预测绝对数

它是相对结构分。

4. 不固定 $\alpha$ 却比较跨网络绝对值

跨图比较需谨慎。

八、小结

PageRank 的核心是：

有向网上带传送的随机游走平稳分布，给节点全局重要性打分。

实现时处理好出度归一、悬挂点与阻尼，并用幂迭代得到排序。解释上始终扣住“结构权威/停留概率”，而不是夸张的因果叙事。

补充说明（建模写作）

在数学建模论文中，除正文八段结构外，建议把下列材料放进附录或支撑材料，避免主文臃肿却又不失可复核性：

1. 原始数据或模拟数据的生成设定：样本量、变量含义、单位、随机种子；
2. 软件与函数清单：如 corr、coxphfit、centrality 及关键参数；
3. 对照结果：与更简单基线（均值差、入度排序、不调整分析）并排；
4. 失败诊断：不收敛、不连通、删失比例过高、重叠不足时的处理；
5. 可复现脚本：保证评阅人按相同步骤得到同号结论。

这些补充不改变方法本身，但能显著提高结果的可信度与答辩时的解释效率。