PageRank求解（networkx & gephi）

networkx基本操作

import networkx as nx
G = nx.Graph() # 创建空图

G.add_node(1, time='5pm') # 添加节点，并赋节点属性
G.add_edge(1, 2, weight=4.7 ) # 添加边，并赋边属性

# 图显示需要借助matplotlib
import matplotlib.pyplot as plt

nx.draw(G) #绘制网络G
plt.show() # 在窗口中显示这幅图像
nx.write_gexf(G,'your_file_name.gexf') # 将图存为gexf文件，进而使用Gephi可视化

G._node # 节点及其属性的字典
G._adj # 节点及其邻居节点的字典
list(G.nodes()) # 节点列表

# 查找某一节点的邻居节点

Geophi基本操作

• 官网下载，安装后可能会提醒cannot find Java 1.8 or higher；解决方法，在Gephi安装目录/etc/gephi.conf中取消jdkhome=“/path/to/jdk的注释，将将其更改为C:/Program Files/Java/jdk-9.0.1（你的jdk安装目录，如未安装需首先安装jdk）。

• 打开‘.gexf’文件，初始状态为一个密集的正方形快，点击左下角的‘布局’进行更改，我选择了‘ForceAtlas2’，感觉布局时间比其他一些的要长很多；

  

• 点击右下角的‘统计’选项，选择‘pagerank’执行pagerank算法，具体计算结果可见上方的‘数据资料’部分。

利用Sigma.js插件把图形导出到HTML

• 在该网站https://gephi.org/plugins/#/下载插件，sigmaexporter-0.9.0.nbm；

• 从Gephi的菜单栏选择“工具 >插件>添加插件>安装“，安装完成后重启软件；

  

• 文件输出格式此时可选“Sigma.js template...”；

  

• 选择导出项目所在的目录，其他信息可默认或自行更改，包括图形的标题、图例、描述、悬停和许多其他细节，选择完成后，点击“确定”；

  

• 导出后得到一个叫network的文件夹，利用该文件夹实现html交互可视化。

  

networkx的pagerank

• PR值：PR(u)=/sum_{v/in Bu} /frac{PR(v)}{L(v)}，u为待更新节点，Bu为u的入度节点集合，L(v)为节点v的出度。

• 等级泄露（Rank Leak）：如果一个节点只有入度，没有出度，吸收了其他节点的PR值而不释放，最终会导致其他节点的 PR 值为 0。

• 等级沉没（Rank Sink）：如果一个节点只有出度，没有入度，最终导致这个节点的 PR 值为 0。

• 为解决上述两个问题，拉里·佩奇提出改进的PageRank的随机浏览模型，该模型基于这样一个场景：在浏览网页时，用户并不总是依据链接跳转的方式，还有可能是用户就是要直接输入网址访问其他页面，虽然这个概率比较小。具体，定义阻尼因子d，表示用户通过链接跳转进入新的网页，一般设置为0.85，PR(u)=/frac{1-d}{N}+d /sum_{v/in Bu} /frac{PR(v)}{L(v)}。

  networkx.pagerank(G, alpha=0.85, personalization=None, max_iter=100, tol=1e-06, nstart=None, weight='weight', dangling=None)

• 在networkx.pagerank中，PR值得计算为：PR=alpha*(A*PR+dangling分配)+(1-alpha)*平均分配

• G：NetworkX图，对于无向图，默认会转化为双向有向图进行计算；

• alpha：即阻尼因子；

• personalization：自定义节点的PR值分配，默认为均匀分配；

• max_iter：最大迭代次数；

• tol：迭代阈值，若两次迭代差值低于该值，则跳出迭代；

• nstart：自定义网络各节点PageRank初始值，自定义的初始化PR值会在函数中自动归一化，见以下部分源码；

  if nstart is None:  
      x = dict.fromkeys(W, 1.0 / N)  #和为1
  else:
      # 归一化nstart vector
      s = float(sum(nstart.values()))
      x = dict((k, v / s) for k, v in nstart.items())
  

• weight：默认为“weight”，边权重值；没有时默认为1。

• dangling：对于dangling节点（出度为0的节点），自定义其PR值得分配，默认为均匀分配。多数情况下，personalization和dangling是相同的。

• Returns – 字典，每个节点及其对应的PR值。

# 计算每个节点的 PR 值，并作为节点的 pagerank 属性
pagerank = nx.pagerank(G)
# 将 pagerank 数值作为节点的属性
nx.set_node_attributes(G, name = 'pagerank', values=pagerank)

比较

• 可以看到，networkx和gephi计算得到的PR值是相近的。

参考

【白话机器学习】算法理论+实战之PageRank算法

networkx pagerank