# 1. PageRank

$$PR(p_i) = \frac{1-d}{N} + d \sum_{p_j \in B(p_i)} \frac{PR(p_j)}{L(p_j)}$$

Fig. 1: PageRanks for a simple network (image from Wikipedia).

Fig. 2: Label nodes in Fig. 1.

# 2. 迭代方法

## 2.1 初始化节点PR值

Fig. 3: The graph with starting value of PageRank iteration for each node.

# Step 1: Initiate PageRank
N = G.number_of_nodes()                     # N = 11
node_and_pr = dict.fromkeys(G, 1.0 / N)


## 2.2 创建随机图（stochastic graph）

Fig. 4: The stochastic graph

stochastic_graph = nx.stochastic_graph(G, weight=weight)    # M = 1/L(pj)

print(stochastic_graph['D'])
{'A': {'Edge Id': u'5', 'weight': 0.5}, 'B': {'Edge Id': u'6', 'weight': 0.5}}


## 2.3 迭代计算

dangling_value = (1-d)/N

for _ in range(max_iter):       # for each iteration
node_and_prev_pr = node_and_pr
node_and_pr = dict.fromkeys(node_and_prev_pr.keys(), 0)

for node in node_and_pr:    # for each node
for out_node in stochastic_graph[node]:     # node --> out_node
node_and_pr[out_node] += d * node_and_prev_pr[node] * stochastic_graph[node][out_node][weight]  # PR(p_i) = d * PR(p_j)}/L(p_j)

node_and_pr[node] += dangling_value


Fig. 5: PageRank after one ieration

# check convergence, l1 norm
err = sum([abs(node_and_pr[node] - node_and_prev_pr[node]) for node in node_and_pr])
if err < N*tol:
return node_and_pr


Fig. 6: Stable PageRank values (66 iterations)

# 初始值
PA(D) = 0.09
PA(B) = 0.09

# 第一次迭代
PA(D)/2 --> P(A), P(B)  # 此时， PB(B)=0.045
PB(B) --> P(C)          # 按上面的算法，PB(B)=0.09，那能不能使用刚更新的PR值0.045，这样会不会快一些？


# 3. NetworkX的pagerank

nx.pagerank跟章节2差不多，区别在于：

# 2中的算法
node_and_pr[node] += (1.0 - d)/N

# nx.pagerank
danglesum = d * sum(node_and_prev_pr[node] for node in dangling_nodes)
node_and_pr[node] += danglesum/N + (1.0 - d)/N  # danglesum/N  + (1-d)/N


nx.pagerank将图中所有悬挂节点（dangling nodes，没有出链的节点，图1只有节点A）的PR累加，并normalized，再加上$(1.0 – d)/N$。