图相关的算法

pagerank

google搜索引擎使用的网页排序算法，初始逻辑非常简单，将网页的相互引用关系建模为一张图，节点为网页页面，边为引用关系，随机选择一个节点随机游走，得到每个节点被访问的收敛概率，该值即pagerank值。该过程可以使用代数方法简化。

实现

rustworkx的实现方案（src/link_analysis.rs）：

/**
- graph - 要计算PageRank的有向图对象
- alpha - 阻尼因子，控制随机跳转概率，通常设为0.85
- weight_fn - 可选函数，用于自定义边权重计算
- nstart - 可选的初始PageRank值字典(key:节点索引，value:初始值)
- personalization - 个性化向量，可以给特定节点分配更高的权重
- tol - 收敛阈值，当两次迭代间的变化小于 tol * 节点数 时停止
- max_iter - 最大迭代次数限制
- dangling - 处理没有出边的节点(悬挂节点)的权重分配
**/
#[pyo3(
    text_signature = "(graph, /, alpha=0.85, weight_fn=None, nstart=None, personalization=None, tol=1.0e-6, max_iter=100, dangling=None)"
)]
pub fn pagerank(
    py: Python,
    graph: &PyDiGraph,
    alpha: f64,
    weight_fn: Option<PyObject>,
    nstart: Option<HashMap<usize, f64>>,
    personalization: Option<HashMap<usize, f64>>,
    tol: f64,
    max_iter: usize,
    dangling: Option<HashMap<usize, f64>>,
) -> PyResult<CentralityMapping> {
...
}

其原始过程：

1. 初始化 （第101-111行）：

   • 获取图的节点数和大小
   • 处理空图的特殊情况

2. 权重处理 （第113-127行）：

   • 从图中提取边的权重
   • 计算每个节点的出边权重总和

3. 构建 Google 矩阵 （第129-134行）：

   • 创建稀疏矩阵表示 Markov 链过程

4. 初始化 PageRank 向量 （第136-151行）：

   • 设置初始 PageRank 值
   • 处理自定义起始值

5. 个性化处理 （第153-172行）：

   • 处理个性化向量
   • 计算阻尼系数

6. 处理悬挂节点 （第174-189行）：

   • 识别没有出边的节点
   • 为悬挂节点分配权重

7. 幂迭代法计算 PageRank （第191-208行）：

   • 迭代计算 PageRank 值直到收敛或达到最大迭代次数
   • 检查收敛条件

8. 结果处理 （第210-226行）：

   • 检查是否收敛
   • 将结果转换为返回格式