PageRank算法及根據(jù)航線對(duì)機(jī)場(chǎng)進(jìn)行排序的示例分析

本篇文章給大家分享的是有關(guān)PageRank算法及根據(jù)航線對(duì)機(jī)場(chǎng)進(jìn)行排序的示例分析，小編覺得挺實(shí)用的，因此分享給大家學(xué)習(xí)，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。

1. PageRank算法

PageRank算法，即網(wǎng)頁排名算法，由Google創(chuàng)始人Larry Page在斯坦福上學(xué)的時(shí)候提出來的。該算法用于對(duì)網(wǎng)頁進(jìn)行排名，排名高的網(wǎng)頁表示該網(wǎng)頁被訪問的概率高。該算法的主要思想有兩點(diǎn)：

a. 如果多個(gè)網(wǎng)頁指向某個(gè)網(wǎng)頁A，則網(wǎng)頁A的排名較高。

b. 如果排名高A的網(wǎng)頁指向某個(gè)網(wǎng)頁B，則網(wǎng)頁B的排名也較高，即網(wǎng)頁B的排名受指向其的網(wǎng)頁的排名的影響。

https://blog.csdn.net/u013007900/article/details/88961913

https://blog.csdn.net/ten_sory/article/details/80927738

2.根據(jù)航線對(duì)機(jī)場(chǎng)進(jìn)行排序示例

input_1.txt內(nèi)容：

XIY SHA
XIY CAN
XIY PEK
SHA PEK
CAN YIH
PEK YIH
SHA YIH
YIH XIY

# -*- coding: utf-8 -*-
"""
Created on Tue Aug 11 21:28:17 2020

@author: pengchua
"""

# 輸入為一個(gè)*.txt文件，例如
# A B
# B C
# B A
# ...表示前者指向后者
 
import numpy as np
 
 
if __name__ == '__main__':
 
    # 讀入有向圖，存儲(chǔ)邊
    f = open('input_1.txt', 'r')
    edges = [line.strip('\n').split(' ') for line in f]
    print(edges)
 
    # 根據(jù)邊獲取節(jié)點(diǎn)的集合
    nodes = []
    for edge in edges:
        if edge[0] not in nodes:
            nodes.append(edge[0])
        if edge[1] not in nodes:
            nodes.append(edge[1])
    print(nodes)
 
    N = len(nodes)
 
    # 將節(jié)點(diǎn)符號(hào)（字母），映射成阿拉伯?dāng)?shù)字，便于后面生成A矩陣/S矩陣
    i = 0
    node_to_num = {}
    for node in nodes:
        node_to_num[node] = i
        i += 1
    for edge in edges:
        edge[0] = node_to_num[edge[0]]
        edge[1] = node_to_num[edge[1]]
    print(edges)
 
    # 生成初步的S矩陣
    S = np.zeros([N, N])
    for edge in edges:
        S[edge[1], edge[0]] = 1
    print(S)
 
    # 計(jì)算比例：即一個(gè)網(wǎng)頁對(duì)其他網(wǎng)頁的PageRank值的貢獻(xiàn)，即進(jìn)行列的歸一化處理
    for j in range(N):
        sum_of_col = sum(S[:,j])
        for i in range(N):
            S[i, j] /= sum_of_col
    print(S)
 
    # 計(jì)算矩陣A
    alpha = 0.85
    A = alpha*S + (1-alpha) / N * np.ones([N, N])
    print(A)
 
    # 生成初始的PageRank值，記錄在P_n中，P_n和P_n1均用于迭代
    P_n = np.ones(N) / N
    P_n1 = np.zeros(N)
 
    e = 100000  # 誤差初始化
    k = 0   # 記錄迭代次數(shù)
    print('loop...')
 
    while e > 0.00000001:   # 開始迭代
        P_n1 = np.dot(A, P_n)   # 迭代公式
        e = P_n1-P_n
        e = max(map(abs, e))    # 計(jì)算誤差
        P_n = P_n1
        k += 1
        print('iteration %s:'%str(k), P_n1)
 
    print('final result:', P_n)

final result: [0.29633859 0.1139626  0.1139626  0.1623967  0.31333951]

networkx在2002年5月產(chǎn)生，是一個(gè)用Python語言開發(fā)的圖論與復(fù)雜網(wǎng)絡(luò)建模工具，內(nèi)置了常用的圖與復(fù)雜網(wǎng)絡(luò)分析算法，可以方便的進(jìn)行復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)分析、仿真建模等工作。

利用networkx可以以標(biāo)準(zhǔn)化和非標(biāo)準(zhǔn)化的數(shù)據(jù)格式存儲(chǔ)網(wǎng)絡(luò)、生成多種隨機(jī)網(wǎng)絡(luò)和經(jīng)典網(wǎng)絡(luò)、分析網(wǎng)絡(luò)結(jié)構(gòu)、建立網(wǎng)絡(luò)模型、設(shè)計(jì)新的網(wǎng)絡(luò)算法、進(jìn)行網(wǎng)絡(luò)繪制等。

##基于networkx 進(jìn)行pageRank計(jì)算

# -*- coding: utf-8 -*-
"""
Created on Tue Aug 11 21:38:58 2020

@author: pengchua
"""

import networkx as nx
import matplotlib.pyplot as plt
 
 
if __name__ == '__main__':
 
    # 讀入有向圖，存儲(chǔ)邊
    f = open('input_1.txt', 'r')
    edges = [line.strip('\n').split(' ') for line in f]
 
    G = nx.DiGraph()
    for edge in edges:
        G.add_edge(edge[0], edge[1])
        
    #顯示圖表
    nx.draw(G, with_labels=True)
    plt.show()
    
    #計(jì)算pr值 
    pr=nx.pagerank(G)
#   page_rank_value=pr[node]
    for node, pageRankValue in pr.items():
        print("%s,%.4f" %(node,pageRankValue))

以上就是PageRank算法及根據(jù)航線對(duì)機(jī)場(chǎng)進(jìn)行排序的示例分析，小編相信有部分知識(shí)點(diǎn)可能是我們?nèi)粘９ぷ鲿?huì)見到或用到的。希望你能通過這篇文章學(xué)到更多知識(shí)。更多詳情敬請(qǐng)關(guān)注億速云行業(yè)資訊頻道。