图神经网络

---

---

一、PageRank简介

PageRank是Google最早的搜索引擎算法。其基本逻辑是给每个网页重要度打分，高分靠前。

1.1互联网的图表示

• Web Pages表示为Nodes，Hyperlinks表示为Edges
• 把互联网当作一个整体的系统，网页之间存在关联，而不是孤立的个体
• 网页可以表示成导航连接式网页
• 无标度网络（Scale-Free）呈现幂律分布

1.2PageRank算法概述

• PageRank使用连接信息计算节点的重要度
• 理解PageRank的5个角度：迭代求解线性方程组、迭代左乘M矩阵、矩阵的特征向量、随机游走、马尔可夫链
• 迭代求解线性方程组：重要节点引出的稀少链接，权重更高
• 迭代左乘M矩阵：将重要度写成矩阵的形式，左乘重要度矩阵
• 通过不断地迭代左乘M矩阵，矩阵会稳定收敛，即得到M矩阵的主特征向量
• 随机游走：随机游走每个网页，计数求和之后再归一化成每个网页的概率，即PageRank值
• 马尔可夫链：每个节点表示一种状态，节点之间的连接表示状态的转移，根据状态转移矩阵，可以计算下一个时刻的状态转移概率

1.3求解PageRank

• 推荐方式：迭代左乘M矩阵（幂迭代）

二、代码实战

2.1引入库

import networkx as nx
import numpy as np 
import random
import pandas as pd# 数据可视化
import matplotlib.pyplot as plt
import matplotlib as mpl
%matplotlib inline
plt.rcParams['font.sans-serif']=['SimHei']  # 用来正常显示中文标签  
plt.rcParams['axes.unicode_minus']=False  # 用来正常显示负号

2.2加载数据，并构建图

# 西游记人物数据集
df = pd.read_csv('data/journey_to_the_west/triples.csv')
Copy to clipboardErrorCopied
edges = [edge for edge in zip(df['head'], df['tail'])]G = nx.DiGraph()
G.add_edges_from(edges)
Copy to clipboardErrorCopied
# 可视化
plt.figure(figsize=(14,14))
pos = nx.spring_layout(G, iterations=3, seed=5)
nx.draw(G, pos, with_labels=True)
plt.show()

2.3计算每个节点PageRank重要度

pagerank = nx.pagerank(G,                     # NetworkX graph 有向图，如果是无向图则自动转为双向有向图alpha=0.85,            # Damping Factorpersonalization=None,  # 是否开启Personalized PageRank，随机传送至指定节点集合的概率更高或更低max_iter=100,          # 最大迭代次数tol=1e-06,             # 判定收敛的误差nstart=None,           # 每个节点初始PageRank值      dangling=None,         # Dead End死胡同节点
)
Copy to clipboardErrorCopied
# 按PageRank值从高到低排序
pagerank_sorted_values = sorted(pagerank.items(),key=lambda x : x[1], reverse=True)
Copy to clipboardErrorCopied
pagerank_sorted_values[:5]

2.4用节点尺寸可视化PageRank值

# 节点尺寸
node_sizes = (np.array(list(pagerank.values())) * 8000).astype(int)
Copy to clipboardErrorCopied
# 节点颜色
M = G.number_of_edges()
edge_colors = range(2, M + 2)
Copy to clipboardErrorCopied
plt.figure(figsize=(15,14))# 绘制节点
nodes = nx.draw_networkx_nodes(G, pos, node_size=node_sizes, node_color=node_sizes)# 绘制连接
edges = nx.draw_networkx_edges(G,pos,node_size=node_sizes,   # 节点尺寸arrowstyle="->",        # 箭头样式arrowsize=20,           # 箭头尺寸edge_color=edge_colors, # 连接颜色edge_cmap=plt.cm.plasma,# 连接配色方案，可选：plt.cm.Blueswidth=4                 # 连接线宽
)# 设置每个连接的透明度
edge_alphas = [(5 + i) / (M + 4) for i in range(M)]
for i in range(M):edges[i].set_alpha(edge_alphas[i])# # 图例
# pc = mpl.collections.PatchCollection(edges, cmap=cmap)
# pc.set_array(edge_colors)
# plt.colorbar(pc)ax = plt.gca()
ax.set_axis_off()
plt.show()

---