1. P a g e R a n k PageRank PageRank算法背景

?? $PageRank$ 算法是現(xiàn)代數(shù)據(jù)科學中用于圖鏈接分析的經(jīng)典方法，最初由 $Larry$ $Page$ 和 $Sergey$ $Brin$ 在1996年提出。兩位斯坦福大學研究生認為互聯(lián)網(wǎng)上的鏈接結構能夠反映頁面的重要性，與當時基于關鍵詞的搜索方法形成對比。這一獨特觀點不僅贏得了學術界的認可，也為后來創(chuàng)建的 $Google$搜索引擎奠定了基礎。

?? $PageRank$的核心思想基于有向圖上的隨機游走模型，即一階馬爾可夫鏈。描述了隨機游走者如何沿著圖的邊隨機移動，最終收斂到一個平穩(wěn)分布。在這分布中，每個節(jié)點被訪問的概率即為其 $PageRank$ 值，代表節(jié)點的重要性。 $PageRank$是遞歸定義的，計算需要迭代方法，因為一個頁面的值部分取決于鏈接到它的其他頁面的值。盡管最初設計用于互聯(lián)網(wǎng)頁面，但 $PageRank$ 已廣泛應用于社會影響力、文本摘要等多個領域，展示了其在圖數(shù)據(jù)上的強大實用性。

2. P a g e R a n k PageRank PageRank算法基礎

2.1. P a g e R a n k PageRank PageRank問題描述

?? $PageRank$ 算法是互聯(lián)網(wǎng)早期用于評估網(wǎng)頁重要性的方法。其核心概念是將互聯(lián)網(wǎng)視為一個有向圖，其中每個網(wǎng)頁是一個節(jié)點，超鏈接是有向邊。通過建立一階馬爾可夫鏈的隨機游走模型，模擬虛擬網(wǎng)頁瀏覽者隨機跳轉，最終形成一個平穩(wěn)分布。每個網(wǎng)頁的 $PageRank$ 值代表其在這個分布中的概率，即重要性。

?? 舉例說明，如下圖所示，假設有三個網(wǎng)頁 $A$、$B$ 和 $C$，$A$ 鏈接到 $B$ 和 $C$，$B$ 只鏈接到 $C$，而 $C$ 只鏈接到 $A$。隨機游走模型中，從 $A$ 出發(fā)的瀏覽者有 50% 的概率跳轉到 $B$ 或 $C$；從 $B$ 出發(fā)的瀏覽者會 100% 跳轉到 $C$；從 $C$ 出發(fā)的瀏覽者會 100% 跳轉到 $A$。經(jīng)過多次迭代，$C$ 的 $PageRank$ 值可能比 $A$ 和 $B$ 高，因為它接收到了 $A$ 和 $B$ 的流量。

?? $PageRank$算法直觀上認為，一個網(wǎng)頁被指向的超鏈接越多，隨機跳轉到該網(wǎng)頁的概率越高，其$PageRank$值越高，表示網(wǎng)頁越重要。反之，指向該網(wǎng)頁的$PageRank$值越高，該網(wǎng)頁$PageRank$值也越高，表明其重要性增加。PageRank值依賴于網(wǎng)絡拓撲結構，一旦確定，$PageRank$值也確定。計算通過迭代，在互聯(lián)網(wǎng)有向圖上進行。初始假設一個分布，通過迭代計算所有網(wǎng)頁的$PageRank$值直至收斂。有向圖和隨機游走模型定義了$PageRank$的基本原理，而基本定義對應于理想情況，一般定義則考慮實際網(wǎng)絡中的復雜性。

2.2.有向圖模型

??有向圖($Directed$ $Graph$)是圖論的基本概念，由節(jié)點和有向邊組成。每條邊有起始節(jié)點和終止節(jié)點，表示方向性。在互聯(lián)網(wǎng)中，每個網(wǎng)頁可看作有向圖中的一個節(jié)點，超鏈接則表示有向邊。

??以三個網(wǎng)頁 A、B 和 C 為例，網(wǎng)頁 A 包含指向 B 和 C 的鏈接，B 包含指向 C 的鏈接，而 C 包含指向 A 的鏈接。這構成有向圖的邊集合，即 E={(A,B),(A,C),(B,C),(C,A)}。

??有向圖中的周期性結構可通過路徑的長度判斷，例如，從節(jié)點 A 出發(fā)返回 A 需要經(jīng)過長度為 3 的倍數(shù)的路徑。這樣的有向圖被稱為周期性圖。

2.3.隨機游走模型

??給定一個含有$n$個結點的有向圖，在有向圖上定義隨機游走（$Random$ $Walk$）模型，即一階馬爾可夫鏈，其中結點表示狀態(tài)，有向邊表示狀態(tài)之間的轉移，假設從一個結點到通過有向邊相連的所有結點的轉移概率相等。具體地，轉移矩陣是一個$n$階矩陣。
$$M=[m_{ij}{]}_{n\times n}$$

??第$i$行第$j$列的元素$m_{ij}$取值規(guī)則如下：如果結點$j$有有$k$個有向邊連出，并且結點$i$是其連出的一個結點則$m_{ij}=\frac{1}{k}$，否則$m_{ij}=0$.
注意轉移矩陣$M$具有如下約束條件:
$$m_{ij}\ge 0$$
$$\sum _{i=1}^n{m}_{ij}=1$$
??即每個元素非負，每列元素之和為1即矩陣$M$為隨機矩陣（$stochastic$ $matrix$）。
??在有向圖上的隨機游走形成馬爾可夫鏈。也就是說，隨機游走者每經(jīng)過一個單位時間轉移一個狀態(tài)。如果當前時刻在第 $i$ 個結點（狀態(tài)），那么下一個時刻在第 $j$ 個結點（狀態(tài)）的概率是 $P_{ij}$。這一概率只依賴于當前的狀態(tài)，與過去無關，具有馬爾可夫性。

3. P a g e R a n k PageRank PageRank算法定義

3.1. P a g e R a n k PageRank PageRank算法基本定義

??給定一個包含 $n$ 個結點的強連通且非周期性的有向圖，在其基礎上定義隨機游走模型。假設轉移矩陣為 $M$，在時刻 $0,1,2,\dots ,t,\dots$，訪問各個結點的概率分布為 ${\mathbf{p}}_0,{\mathbf{p}}_1,{\mathbf{p}}_2,\dots ,{\mathbf{p}}_t,\dots$。其中，${\mathbf{v}}_0$ 是初始概率分布。

$${\mathbf{p}}_0={\mathbf{v}}_0,{\mathbf{p}}_{t+1}={\mathbf{p}}_t?M$$

??則極限為:
$$\underset{t\to \infty }{\lim }{M}^t{R}_0=R$$
??存在極限向量$R$表示馬爾可夫鏈的平穩(wěn)分布，滿足:
$$MR=R$$
??平穩(wěn)分布$R$稱為這個有向圖的 $PageRank$。 $R$的各個分量稱為各個結點的$PageRank$值。
R = [ P R ( v 1 ) P R ( v 2 ) ? P R ( v n ) ] \left.R=\left[\begin{array}{c}PR\left(v_1\right)\\PR\left(v_2\right)\\\vdots\\PR\left(v_n\right)\end{array}\right.\right] R= ?PR(v1?)PR(v2?)?PR(vn?)? ?

??其中
$$PR\left(v_i\right)=\sum _{v_j\in M\left(v_i\right)}\frac{PR\left(v_j\right)}{L\left(v_j\right)},i=1,2,?,n$$

??這里 $M(v_i)$ 表示指向結點 $v_i$的結點集合，$L(v_j)$ 表示結點 $v_j$ 連出的有向邊的個數(shù)。

3.2. P a g e R a n k PageRank PageRank算法一般定義

??為了考慮到用戶不僅會通過點擊鏈接來瀏覽網(wǎng)頁，還可能隨機選擇一個網(wǎng)頁。因此需要在基本定義的基礎上導入平滑項阻尼因子。阻尼因子 $d$ 取值由經(jīng)驗決定，例如 $d=0.85$。當 $d$ 接近1時，隨機游走主要依照轉移矩陣 $M$ 進行；當 $d$ 接近0時，隨機游走主要以等概率隨機訪問各個結點。
$$\begin{array}{rl}R& =(dM+\frac{1?d}{n}\mathbf{E})R\\ & =dMR+\frac{1?d}{n}1\end{array}$$

??相當于:
P R ( v i ) = d ( ∑ v j ∈ M ( v i ) P R ( v j ) L ( v j ) ) + 1 ? d n , i = 1 , 2 , ? ? , n PR\left(v_i\right)=d\left(\sum_{v_j\in M\left(v_i\right)}\frac{PR\left(v_j\right)}{L\left(v_j\right)}\right)+\frac{1-d}n,\quad i=1,2,\cdots,n PR(vi?)=d ?vj?∈M(vi?)∑?L(vj?)PR(vj?)? ?+n1?d?,i=1,2,?,n

4. P a g e R a n k PageRank PageRank算法計算

4.1.冪迭代法

??首先給每個頁面賦予隨機的PR值，然后通過 $P_{n+1}=A?P_n$ 不斷地迭代$PR$值。當滿足下面的不等式后迭代結束，獲得所有頁面的$PR$值：

$$|P_{n+1}?P_n|<?$$

??其中，$?$是預先定義的小正數(shù)。

4.2.特征值法

??特征值法是一種用于求解線性代數(shù)問題的方法，其中之一就是求解矩陣的特征值和特征向量。在上述描述中，特征值法用于分析 $Markov$ 鏈的收斂行為。

??具體來說，對于一個方陣 $A$，其特征值（$eigenvalues$）$\lambda$ 和對應的特征向量（$eigenvectors$）$\mathbf{v}$滿足以下方程：

$$A?\mathbf{v}=\lambda ?\mathbf{v}$$

??這個方程可以重寫為 $(A?\lambda ?I)?\mathbf{v}=0$，其中 $I$ 是單位矩陣。

??對于 $Markov$ 鏈的情況，我們考慮轉移矩陣 $A$。特征值法告訴我們，當 $A$ 的特征值中存在一個值為 1 時，對應的特征向量可以用來表示 Markov 鏈的收斂狀態(tài)。這個特征向量的所有分量均為正，而且是唯一的。

??在 $PageRank$ 算法中，我們通過不斷迭代

$$P_{n+1}=A?P_n$$

??來逼近這個特征向量，直到收斂。這就是特征值法在 $PageRank$ 算法中的應用。

4.3.代數(shù)法

??相似的，當上面提到的$Markov$鏈收斂時，必有：
$$\begin{array}{c}P=AP\\ ?P=(\alpha S+\frac{(1?\alpha )}{N}e{e}^T)P\\ \text{方量都為}1\text{的列向量,}P\text{的所有分量之和為}1\\ ?P=\alpha SP+\frac{(1?\alpha )}{N}e\\ ?(e{e}^T?\alpha S)P=\frac{(1?\alpha )}{N}e\\ ?P=(e{e}^T?\alpha S{)}^{?1}\frac{(1?\alpha )}{N}e\end{array}$$

5. P a g e R a n k PageRank PageRank算法計算實例

??利用$PageRank$算法計算下圖每一個結點對應的$PR$：

??迭代過程與最后結果如下所示:文章來源地址http://www.zghlxwxcb.cn/news/detail-817033.html

6.算法工作源代碼

6.1.繪制圖網(wǎng)絡代碼

#繪制有向圖
import networkx as nx
import matplotlib.pyplot as plt
G = nx.DiGraph()
nodes = ["A", "B", "C", "D", "E"]
G.add_nodes_from(nodes)
edges = [("A", "B"), ("A", "C"), ("A", "D"), ("B", "D"), ("C", "E"), ("D", "E"), ("B", "E"), ("E", "A")]
G.add_edges_from(edges)
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_size=700, node_color='skyblue', font_size=10, font_color='black',
        font_weight='bold', arrowsize=20, connectionstyle='arc3,rad=0.1')
#plt.savefig("Graph.png")#隨機的圖像
plt.show()

6.2. P a g e R a n k PageRank PageRank算法Python代碼實現(xiàn)

from pygraph.classes.digraph import digraph
import networkx as nx
import matplotlib.pyplot as plt
class PRIterator:
    """計算一張圖中的PR值"""

    def __init__(self, dg):
        self.damping_factor = 0.85  # 阻尼系數(shù),即α
        self.max_iterations = 100  # 最大迭代次數(shù)
        self.min_delta = 0.00001  # 確定迭代是否結束的參數(shù),即?
        self.graph = dg

    def page_rank(self):
        #  先將圖中沒有出鏈的節(jié)點改為對所有節(jié)點都有出鏈
        for node in self.graph.nodes():
            if len(self.graph.neighbors(node)) == 0:
                for node2 in self.graph.nodes():
                    dg.add_edge((node, node2))

        nodes = self.graph.nodes()
        graph_size = len(nodes)

        if graph_size == 0:
            return {}
        page_rank = dict.fromkeys(nodes, 1.0 / graph_size)  # 給每個節(jié)點賦予初始的PR值
        damping_value = (1.0 - self.damping_factor) / graph_size  # 公式中的(1?α)/N部分

        flag = False
        for i in range(self.max_iterations):
            change = 0
            for node in nodes:
                rank = 0
                for incident_page in self.graph.incidents(node):  # 遍歷所有“入射”的頁面
                    rank += self.damping_factor * (page_rank[incident_page] / len(self.graph.neighbors(incident_page)))
                rank += damping_value
                change += abs(page_rank[node] - rank)  # 絕對值
                page_rank[node] = rank

            print("This is NO.%s iteration" % (i + 1))
            print(page_rank)

            if change < self.min_delta:
                flag = True
                break
        if flag:
            print("finished in %s iterations!" % (i + 1))
        else:
            print("finished out of 100 iterations!")
        return page_rank
    

#%%
if __name__ == '__main__':
    dg = digraph()

    dg.add_nodes(["A", "B", "C", "D", "E"])

    dg.add_edge(("A", "B"))
    dg.add_edge(("A", "C"))
    dg.add_edge(("A", "D"))
    dg.add_edge(("B", "D"))
    dg.add_edge(("C", "E"))
    dg.add_edge(("D", "E"))
    dg.add_edge(("B", "E"))
    dg.add_edge(("E", "A"))

    pr = PRIterator(dg)
    page_ranks = pr.page_rank()

    print("The final page rank is\n", page_ranks)

7.參考資料

[1].https://zhuanlan.zhihu.com/p/137561088
[2].https://zhuanlan.zhihu.com/p/133233438
[3].https://www.mlpod.com/36.html
[4].https://www.cnblogs.com/rubinorth/p/5799848.html
[5].https://zhuanlan.zhihu.com/p/197877312
[6].https://blog.csdn.net/qq_36159768/article/details/108791236

到了這里，關于數(shù)學建模--PageRank算法的Python實現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！