社区首页 >专栏 >直播案例 | 使用PageRank对全球机场进行排序

直播案例 | 使用PageRank对全球机场进行排序

原创

数据酷客

修改于 2020-05-18 06:24:29

2.7K00

代码可运行

文章被收录于专栏：数据科学人工智能数据科学人工智能

运行总次数：0

代码可运行

查看本案例完整的数据、代码和报告请登录数据酷客（http://cookdata.cn）案例板块。

PageRank 是谷歌公司起家的算法，在数据科学领域具有重要的地位和作用。PageRank 算法最初提出来用于利用网页之间的链接关系来对网页进行排序，从而优化搜索引擎的效果。如今，我们可以将 PageRank 算法用作网络中节点排序的一般算法。

在本案例中，我们使用一个全球机场之间航线的网络数据集，借助 Python 中的复杂网络分析库 networkx 中实现的 PageRank 算法，完成对全球机场的排序。

1 数据集介绍

文件 ./input/out.opsahl-openflights.csv 中的有向网络包含世界各机场之间的航班。有向边表示从一个机场到另一个机场的飞行航线。这个数据集是从Openflights.org 数据中提取出来的，与 Tore Opsahl 在数据集列表中的网络14c相对应，来源网址为：toreopsahl.com。

利用 networkx 中的 read_edgelist 函数，将网络加载到内存中。注意，由于我们处理的是有向网络，所以需要将 create_using 参数设置为 nx.DiGraph()。

import networkx as nx
flights_network = nx.read_edgelist("./input/out.opsahl-openflights.csv",create_using=nx.DiGraph())

print("航班数：" + str(len(flights_network.nodes)))
print("航线数：" + str(len(flights_network.edges)))

航班数：2939 航线数：30501

在这个航线网络中，一共包含 2939 个机场，30501 条航线。下面我们使用 nx.draw 函数，将网络进行可视化。

import matplotlib.pyplot as plt
%matplotlib inline
fig, ax = plt.subplots(figsize=(24, 16)) 
pos_flights = nx.kamada_kawai_layout(flights_network) #网络布局
ax.axis("off")
plt.box(False)
nx.draw(flights_network, node_size=30,node_color = "green", edge_color = "#D8D8D8",width=.3, ax=ax)

2 找出最大连通子图

从上图中很容易看出，这个网络不是一个连通图。我们从航线网络中提取出最大连通子图进行进一步分析。对于有向网络， networkx 中的 weakly_connected_component_subgraphs 函数可以返回网络中的连通子图列表。我们只提取最大连通子图。

largest_component = max(nx.weakly_connected_component_subgraphs(flights_network), key=len)#找出最大连通子图

print("航班数：" + str(len(largest_component.nodes)))
print("航线数：" + str(len(largest_component.edges)))

航班数：2905 航线数：30442

在最大连通子图中，一共包含 2905 个机场和 30442 条航线。下面将最大连通子图进行可视化。

fig, ax = plt.subplots(figsize=(24, 16)) 
pos_flights2 = nx.kamada_kawai_layout(largest_component)
ax.axis("off")
plt.box(False)
nx.draw(largest_component, node_size=30,node_color = "green", edge_color = "#D8D8D8",width=.3,pos = pos_flights2, ax=ax)

3 PageRank 算法简介

PageRank算法是由谷歌创始人拉里·佩奇(Larry Page)和谢尔盖·布林(Sergey Brin)所设计出来的谷歌搜索引擎上的页面排序算法，最早作为论文发表于 1998 年。论文发表之后没多久，佩奇和布林就以此论文为基础创立了谷歌公司。、

阻尼系数 β 用来表示在PageRank迭代过程中一个点沿着出边跳转到下一个点的概率。 (1 - β) 表示在浏览过程不沿着边跳转，而是在所有点中随机挑选下一个点的概率。实际试验证明 β 被设置成 0.85 时 PageRank 的计算结果最符合实际情况。

4 使用 PageRank 算法对机场进行排序

在 networkx 中，使用 pagerank 函数即可计算网络中节点的 PageRank 值。

pr_dict = nx.pagerank(largest_component)

import pandas as pd
pr_df = pd.DataFrame.from_dict(pr_dict,orient="index")
pr_df.columns = ["pr_value"]
pr_df.sort_values(by = "pr_value").head(20)
pr_df.head(20)

5 将节点大小与 PageRank 值关联并可视化

实现一个函数 get_nodesize_pagerank ，将网络中节点的 PageRank 值，映射为网络中节点的大小。

def get_nodesize_pagerank(pagerank, min_size, max_size):
    nodesize_list = []
    pr_max = max(pagerank.values())
    for node, pr in pagerank.items():
        nodesize = (max_size - min_size)*pr/pr_max + min_size
        nodesize_list.append(nodesize)
    return nodesize_list

fig, ax = plt.subplots(figsize=(24, 16)) 
pos_flights2 = nx.kamada_kawai_layout(largest_component)
ax.axis("off")
plt.box(False)
nx.draw(largest_component, node_size=get_nodesize_pagerank(pr_dict,1,100),node_color = "green", edge_color = "#D8D8D8",width=.3,pos = pos_flights2, ax=ax)