python - 如何实现一次迭代的pagerank?
问题描述
我正在尝试为单次迭代实现 pagerank 算法。 根据我在这里的 colab,公式定义为:
=∑→+(1−)1
我试图实现为:
r1 = (beta * (r0/degi)) + ( (1 - beta) * 1/node_count)
但是,在与 networkX 实现进行交叉检查时,我得到了不同的值。nx 源代码有点难以理解,因为它用于具有悬空值的多次迭代。
我的代码(在 colab 上更好地查看)
def one_iter_pagerank(G, beta, r0, node_id):
# TODO: Implement this function that takes a nx.Graph, beta, r0 and node id.
# The return value r1 is one interation PageRank value for the input node.
# Please round r1 to 2 decimal places.
degi = G.degree[node_id]
node_count = G.number_of_nodes() # correct?
r1 = (beta * (r0/degi)) + ( (1 - beta) * 1/node_count)
print('r1:', r1)
# crosscheck
# alpha == beta? (without= 0.128, with=)
r2 = nx.pagerank(G, max_iter=1, tol=0.1)[node_id]
r3 = nx.pagerank(G, max_iter=1, tol=0.1, alpha=beta)[node_id]
print('r2:', r2, '\nr3:', r3)
beta = 0.8
r0 = 1 / G.number_of_nodes() # assign base value?
node_id = 0
print('r0:', r0)
r1 = one_iter_pagerank(G, beta, r0, node_id)
它返回多个值:
r0: 0.029411764705882353 # base value?
r1: 0.007352941176470587 # my calculation
r2: 0.13427287581699343 # nx calc with no alpha
r3: 0.12810457516339868 # nx calc with alpha
那么我的实现在哪里出错/与 nx 结果如此不同?
colab 基于斯坦福 CS224W 课程 CS224W: Machine Learning with Graphs here
解决方案
要计算 PageRank 的一次迭代,您需要 的相邻节点的出度(或仅是度数,因为在这种情况下图是非循环的)node_id
。您计算的值是node_id
自身的度数。以下对我有用。
def one_iter_pagerank(G, beta, r0, node_id):
# TODO: Implement this function that takes a nx.Graph, beta, r0 and node id.
# The return value r1 is one interation PageRank value for the input node.
# Please round r1 to 2 decimal places.
r1 = 0
neighbors = [n for n in G[node_id]]
degrees = [d for _,d in G.degree(neighbors)]
for d in degrees:
r1 += beta*(r0/d)
r1 = round(r1 + (1-beta)/G.number_of_nodes(), 2)
return r1
推荐阅读
- php - 如何从字段中覆盖浏览器数据并在 woocommerce 结帐页面中设置默认值?
- python - 两个数字 & 从第一个数字到第二个数字打印列表
- r - 通过在 R 中使用 dplyr 计算来融化数据框和分组
- php - 使用 ClearDB 在 Heroku 上部署 PHP Web App
- python - AttributeError:“工作表”对象在 openpyxl(python)中没有属性“get_highest_row”
- r - 将 tweenr 和 gganimate 与条形图一起使用
- javascript - WordPress TwentyFifteen SubMenu 使用与主菜单项关联的按钮时显示的子菜单项
- ionic4 - 如何在 Ionic 4 中为旧版 Android 发布 apk?
- git - 如何在“git push”之前删除敏感信息
- linux - 如何让 systemd 变量在重启后仍然存在?