建模与符号
设节点数为 N,边集为 edges,每条边 (u,v) 表示从 u→v。
构造列随机转移矩阵 S∈RN×N,令第 j 列表示“从节点 j”在一步内跳到各节点的概率分布:
Sij=Pr(j→i)请手写实现经典 PageRank 算法(列随机、幂迭代形式),用于极小的有向图(节点 ≤6 个)。
1.固定超参数
阻尼系数 d 0.85
随机跳转 (1−d)/N
收敛判据 当两次迭代 L1 差 <1e−8 或迭代次数达 1000 即停止
初始 PageRank 向量为均匀分布 (1/N,...,1/N) 。
2.输出格式
一行:长度为 N 的 JSON 数组,依节点编号顺序给出最终 PageRank 。
3.确定性说明
幂迭代在固定阻尼系数下会收敛到唯一的平稳分布;无需额外平局处理。
一行 JSON :
{
"edges”:[[u1,v1],[u2,v2],…],//有向边,节点编号从0开始"
"N”:4 / 节点总数(2≤N≤6)
}
若某节点没有任何出边(悬挂节点),请在构造转移矩阵时对出边(悬挂节点)做均匀分布处理。
使用 round(x,6) 保留小数位即可
示例:
[0.486486,0.256757,0.256757]
为了确保通过测试用例,仅使用 NumPy 实现
输入
{"edges":[[0,1],[1,0]],"N";2}
输出
[0.5,0.5]