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