獲取案例鏈接、直播課件、數(shù)據(jù)集在本公眾號(hào)內(nèi)發(fā)送“機(jī)器學(xué)習(xí)”。
PageRank 是谷歌公司起家的算法，在數(shù)據(jù)科學(xué)領(lǐng)域具有重要的地位和作用。PageRank 算法最初提出來用于利用網(wǎng)頁之間的鏈接關(guān)系來對(duì)網(wǎng)頁進(jìn)行排序，從而優(yōu)化搜索引擎的效果。如今，我們可以將 PageRank 算法用作網(wǎng)絡(luò)中節(jié)點(diǎn)排序的一般算法。
在本案例中，我們使用一個(gè)全球機(jī)場之間航線的網(wǎng)絡(luò)數(shù)據(jù)集，借助 Python 中的復(fù)雜網(wǎng)絡(luò)分析庫 networkx 中實(shí)現(xiàn)的 PageRank 算法，完成對(duì)全球機(jī)場的排序。
1 數(shù)據(jù)集介紹
文件 ./input/out.opsahl-openflights.csv 中的有向網(wǎng)絡(luò)包含世界各機(jī)場之間的航班。有向邊表示從一個(gè)機(jī)場到另一個(gè)機(jī)場的飛行航線。這個(gè)數(shù)據(jù)集是從Openflights.org 數(shù)據(jù)中提取出來的，與 Tore Opsahl 在數(shù)據(jù)集列表中的網(wǎng)絡(luò)14c相對(duì)應(yīng)，來源網(wǎng)址為：toreopsahl.com。
利用 networkx 中的 read_edgelist 函數(shù)，將網(wǎng)絡(luò)加載到內(nèi)存中。注意，由于我們處理的是有向網(wǎng)絡(luò)，所以需要將 create_using 參數(shù)設(shè)置為 nx.DiGraph()。
import networkx as nx
flights_network = nx.read_edgelist('./input/out.opsahl-openflights.csv',create_using=nx.DiGraph())
print('航班數(shù)：' + str(len(flights_network.nodes)))
print('航線數(shù)：' + str(len(flights_network.edges)))
航班數(shù)：2939
航線數(shù)：30501
在這個(gè)航線網(wǎng)絡(luò)中，一共包含 2939 個(gè)機(jī)場，30501 條航線。下面我們使用 nx.draw 函數(shù)，將網(wǎng)絡(luò)進(jìn)行可視化。
import matplotlib.pyplot as plt
%matplotlib inline
fig, ax = plt.subplots(figsize=(24, 16))
pos_flights = nx.kamada_kawai_layout(flights_network) #網(wǎng)絡(luò)布局
ax.axis('off')
plt.box(False)
nx.draw(flights_network, node_size=30,node_color = 'green', edge_color = '#D8D8D8',width=.3, ax=ax)
2 找出最大連通子圖
從上圖中很容易看出，這個(gè)網(wǎng)絡(luò)不是一個(gè)連通圖。我們從航線網(wǎng)絡(luò)中提取出最大連通子圖進(jìn)行進(jìn)一步分析。對(duì)于有向網(wǎng)絡(luò)， networkx 中的 weakly_connected_component_subgraphs 函數(shù)可以返回網(wǎng)絡(luò)中的連通子圖列表。我們只提取最大連通子圖。
largest_component = max(nx.weakly_connected_component_subgraphs(flights_network), key=len)#找出最大連通子圖
print('航班數(shù)：' + str(len(largest_component.nodes)))
print('航線數(shù)：' + str(len(largest_component.edges)))
航班數(shù)：2905
航線數(shù)：30442
在最大連通子圖中，一共包含 2905 個(gè)機(jī)場和 30442 條航線。下面將最大連通子圖進(jìn)行可視化。
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算法是由谷歌創(chuàng)始人拉里·佩奇(Larry Page)和謝爾蓋·布林(Sergey Brin)所設(shè)計(jì)出來的谷歌搜索引擎上的頁面排序算法，最早作為論文發(fā)表于 1998 年。論文發(fā)表之后沒多久，佩奇和布林就以此論文為基礎(chǔ)創(chuàng)立了谷歌公司。
PageRank是一個(gè)迭代算法。在初始的時(shí)候，每個(gè)點(diǎn)的PageRank值都設(shè)置成，其中為圖中點(diǎn)的數(shù)量。在每一輪的迭代中，每個(gè)點(diǎn) 都沿著它的出邊往它每個(gè)鄰居點(diǎn)傳遞 的 的PageRank值。于是，經(jīng)過第 輪迭代之后，每個(gè)點(diǎn) 的PageRank值可以表示為
其中 為指向節(jié)點(diǎn)的節(jié)點(diǎn)集合，而 表示 指向的節(jié)點(diǎn)的集合。
阻尼系數(shù) 用來表示在PageRank迭代過程中一個(gè)點(diǎn)沿著出邊跳轉(zhuǎn)到下一個(gè)點(diǎn)的概率。 表示在瀏覽過程不沿著邊跳轉(zhuǎn)，而是在所有點(diǎn)中隨機(jī)挑選下一個(gè)點(diǎn)的概率。實(shí)際試驗(yàn)證明 被設(shè)置成 時(shí) PageRank 的計(jì)算結(jié)果最符合實(shí)際情況。
4 使用 PageRank 算法對(duì)機(jī)場進(jìn)行排序
在 networkx 中，使用 pagerank 函數(shù)即可計(jì)算網(wǎng)絡(luò)中節(jié)點(diǎn)的 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 將節(jié)點(diǎn)大小與 PageRank 值關(guān)聯(lián)并可視化
實(shí)現(xiàn)一個(gè)函數(shù) get_nodesize_pagerank ，將網(wǎng)絡(luò)中節(jié)點(diǎn)的 PageRank 值，映射為網(wǎng)絡(luò)中節(jié)點(diǎn)的大小。
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)
