PageRank和Personalized PageRank（个性化PageRank，PPR）是图节点重要性评估的两种核心算法，前者用于全局重要性排序，后者用于局部关联性计算。

Personalized PageRank可视化

damping值越大，种子节点周围节点重要性越大

PageRank

PageRank 算法根据图中各节点的关系数量以及相应源节点的重要性来衡量每个节点的重要性。其基本假设是：一个页面的重要性仅取决于链接到它的其他页面的重要性。

原理

• 随机游走模型：模拟用户随机点击链接的行为，以阻尼系数 d （通常0.85）控制继续浏览的概率，剩余概率 1−d 随机跳转至任意网页。

• 公式表示：
  
  其中：

• 假定有T₁到Tₙ等页面指向节点A。

• d为阻尼系数，通常设为0.85，取值范围为0（含）到1（不含）。

• C(A)表示页面A的出链数。

PageRank算法注意事项

• 如果一组页面之间只有内部链接，没有指向外部的链接，这组页面会形成“蜘蛛陷阱”（spider trap）。
• 当页面网络形成无限循环时，会出现“排名沉降”（rank sink）问题。
• 如果某些页面没有任何出链，会形成“死胡同”（dead-end）。

阻尼因子配置参数的取值范围在 0（含）至 1（不含）之间。如果其值过高，可能会出现“陷坑”和“蜘蛛网”等问题，并且数值可能会出现波动，导致算法无法收敛。如果值过低，那么所有的分数都会趋向于 1，这样结果将无法充分反映图的结构。调整阻尼系数（damping factor）可以缓解上述问题。阻尼系数可以理解为网页浏览者随机跳转到其他页面的概率，从而避免陷入陷阱或死循环。

Personalized PageRank（PPR）

PPR是传统PageRank的扩展，用于衡量图中节点间的关联性。其核心思想是从指定源节点（如用户或商品）出发，通过随机游走模拟重要性传播，最终收敛到稳定概率分布。

数学上，PPR的迭代公式为：

应用场景

• 推荐系统：基于用户历史行为推荐商品（如用户-商品二部图中的PPR计算）；
• 社交网络好友推荐：发现与目标用户兴趣相似的节点。

igraph库实现

• igraph_i_personalized_pagerank_arpack
  • 基于 ARPACK 库，将 PageRank 问题转化为特征向量（主特征值为1的特征向量）问题，通过迭代求解。
  • 算法本质是幂迭代（power iteration），每一步通过自定义的算子进行向量变换。
  • 适合稀疏大图，但收敛速度依赖于谱间隙，且对数值稳定性有一定要求。
• igraph_i_personalized_pagerank_prpack
  • 基于 PRPACK 库，采用代数方法，将 PageRank 问题转化为线性方程组求解。
  • 通常使用高效的稀疏线性求解器（如Gaussian-Elimination高斯消元法），收敛速度快，对各种图结构更健壮。
  • 支持更多高级特性，如阻尼因子为0时的特殊处理。

arpack与prpack对比：

特性	ARPACK 版本	PRPACK 版本
算法类型	特征向量迭代（幂法）	稀疏线性方程组求解
依赖库	ARPACK	PRPACK
代码复杂度	高（需手动实现迭代算子和流程）	低（直接调用 PRPACK 接口）
收敛速度与健壮性	依赖谱间隙，部分图收敛慢	通常更快更健壮
推荐程度	兼容性考虑，或需自定义算子时	推荐用于大多数 PageRank 计算场景

HippoRAG2使用igraph库来实现：

pagerank_scores = self.graph.personalized_pagerank(
            vertices=range(len(self.node_name_to_vertex_idx)),
            damping=damping, # 阻尼因子0.5
            directed=False,
            weights='weight',
            reset=reset_prob, # reset_prob为综合排名rerank后的节点分数
            implementation='prpack' # 使用prpack实现
        )

igraph_i_personalized_pagerank_arpack实现代码

1. 初始化：仅源节点PR值为1，其余为0；
2. 迭代传播：从源节点出发，沿边分配权重，直至收敛；
3. 结果解释：节点PR值越高，与源节点的关联性越强。

// pagerank_operator_unweighted 是 igraph PageRank 算法（未加权版本）中用于 ARPACK 求解器的算子函数。它实现了 PageRank 迭代中的一次“向量乘法”，即根据当前概率分布 from 计算下一步概率分布 to
static igraph_error_t pagerank_operator_unweighted(igraph_real_t *to, const igraph_real_t *from, int n, void *extra) {

    pagerank_data_t *data = extra;
    igraph_adjlist_t *adjlist = data->adjlist;
    igraph_vector_t *outdegree = data->outdegree;
    igraph_vector_t *tmp = data->tmp;
    igraph_vector_t *reset = data->reset;
    igraph_vector_int_t *neis;
    igraph_integer_t i, j, nlen;
    igraph_real_t sumfrom = 0.0;
    igraph_real_t fact = 1 - data->damping;

    /* 遍历每个顶点 i：
        如果 i 有出边（outdegree[i] != 0），则该顶点的概率 from[i] 有 fact = 1-damping 的概率会跳转（teleport），其余概率用于正常游走。
        如果 i 没有出边（出度为 0），则所有概率都用于跳转。
        sumfrom 累加所有顶点的跳转概率（即本轮所有需要“随机跳转”的概率总和）。
        tmp[i] 预先存储 from[i] / outdegree[i]，用于后续分配概率到邻居。
    */
    for (i = 0; i < n; i++) {
        sumfrom += VECTOR(*outdegree)[i] != 0 ? from[i] * fact : from[i];
        VECTOR(*tmp)[i] = from[i] / VECTOR(*outdegree)[i];
    }

    /* 对每个顶点 i：
        获取其所有邻居 neis。
        对每个邻居 nei，累加 tmp[nei]（即邻居分配给 i 的概率）。
        最后乘以 damping（即“正常游走”概率），得到 to[i] 的“游走”部分。 
    */
    for (i = 0; i < n; i++) {
        neis = igraph_adjlist_get(adjlist, i);
        nlen = igraph_vector_int_size(neis);
        to[i] = 0.0;
        for (j = 0; j < nlen; j++) {
            igraph_integer_t nei = VECTOR(*neis)[j];
            to[i] += VECTOR(*tmp)[nei];
        }
        to[i] *= data->damping;
    }

    /* 如果有 reset 向量（个性化 PageRank），则跳转概率按 reset 分布分配到每个顶点。
        否则（普通 PageRank），跳转概率均匀分配到所有顶点。*/
    if (reset) {
        /* Running personalized PageRank */
        for (i = 0; i < n; i++) {
            to[i] += sumfrom * VECTOR(*reset)[i];
        }
    } else {
        /* Traditional PageRank with uniform reset vector */
        sumfrom /= n;
        for (i = 0; i < n; i++) {
            to[i] += sumfrom;
        }
    }

    return IGRAPH_SUCCESS;
}

neo4j（Graph Data Science库）实现

neo4j需要使用插件Graph Data Science（GDS）库来实现，语法如下：

MATCH (siteA:Page {name: 'Site A'})
CALL gds.pageRank.stream('myGraph', {
  maxIterations: 20,
  dampingFactor: 0.85,
  sourceNodes: [siteA]
})
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC, name ASC

GDS算法实现：http://delab.csd.auth.gr/~dimitris/courses/ir_spring06/page_rank_computing/01531136.pdf

• 该算法将整个图分区，每个分区并行处理自己负责的节点。
• 每一轮迭代中，节点将自己的PageRank值通过出边平均分配给目标节点。
• 如果目标节点在本分区，直接累加；如果在其他分区，则需要同步（通信）。
• 最后用阻尼系数统一更新所有节点的PageRank值。
• 经过多轮迭代后，PageRank值会逐渐收敛。

PageRank与Personalized PageRank对比

维度	PageRank	Personalized PageRank
目标	全局重要性排序	局部关联性评估
初始向量	均匀分布	集中于源节点（其余为0）
随机跳转	均匀跳转至任意节点	以高概率返回源节点
计算复杂度	需全局迭代，适合离线计算	支持单源局部计算，适合在线推荐系统
典型应用	网页排名、学术论文影响力分析	商品推荐、社交网络关系挖掘

总结：

PageRank通过全局链接结构衡量节点重要性，而Personalized PageRank通过局部随机游走实现个性化关联分析。两者在搜索引擎、推荐系统等领域形成互补，体现了从“全局权威”到“个体偏好”的算法演进逻辑。