?PaperWeekly 原創 ·?作者｜賁忠奇

單位｜混沌大學推薦算法工程師

研究方向｜推薦算法、反作弊

PageRank 是一種利用網頁之間的連接數量和質量來計算網頁重要性的技術。PageRank 算法基礎上衍生出來很多重要的鏈接分析算法，TextRank 是其重要的衍生之一，在 nlp 領域用于文章摘要和關鍵詞提取。

PageRank 也可以用于反作弊，網頁的連接數量和質量可以類比成某個黑產團伙中的成員之間的連接數量和連接的質量，可以用于黑產成員重要性分析。

背景

最早的搜索引擎采用的是分類目錄方法，即通過人工編輯審核進行網頁分類并整理出高質量的網站，并按照人工編輯認為的重要程度去排序。由于早期的網頁比較少，那時 Yahoo 和國內的 hao123 就是使用這種方法，在那一歷史時期是可以行的。后來網頁越來越多，人工分類已經不可能了。

搜索引擎采用文本檢索的方式，即計算用戶查詢關鍵詞與網頁內容的相關程度來返回搜索結果，被搜索詞語在網頁中的出現次數來決定排序——出現次數越多的網頁排在越前面。但是總有一些垃圾網站，來回地倒騰某些關鍵詞使自己的搜索排名靠前，使得李鬼取代李逵，顯然這種方式是不合理的。

1996 年初，谷歌公司的創始人， 當時還是美國斯坦福大學（Stanford University）研究生的佩奇（Larry Page）和布林（Sergey Brin）開始了對網頁排序存在的問題進行研究。

PageRank 于 1997 年用于構建早期的搜索系統原型時提出的鏈接分析算法，用來衡量一個網站的好壞，使得更加重要或者等級越高的網站排名更加靠前，提升搜索結果的相關性和質量。?PageRank 的得分簡稱 PR 值，Google 把 PR 值分為 0 到 10 級，10 級為滿分，PR 值越高說明網站越重要。

算法介紹

在 PageRank 提出之前，已經有研究者利用網頁的入鏈數來表示網頁的重要程度。PageRank 除了考慮入鏈的數量還考慮網頁的質量，兩者結合起來表示網頁的重要性。PageRank 有兩個基本假設：

數量假設：如果一個頁面收到其他網頁指向它的入鏈數越多，說明這個頁面越重要。

質量假設：指向一個頁面的入鏈質量不同，質量高的頁面通過鏈接向其他頁面傳遞更多的權重。

PageRank 計算公式如下：

?: 網頁??的 PageRank 值；?表示網頁?鏈入合集中的某個網頁；?: 網頁?鏈入的集合；?: 表示鏈入網頁?的 PageRank 值；?:表示網頁??鏈出的數量。

計算過程主要分為以下兩個階段：

初始階段：網頁通過鏈接關系構建起 Web 圖，每個鏈接的頁面具有相同的 PageRank 值。可以將網頁的 PageRank 值都初始化為 1/N，N 是網頁的數量，認為每個網頁的權重一樣，剛開始都是可以隨機訪問到的。

更新 PageRank 得分：在一輪更新頁面 PageRank 得分的計算中，每個頁面將其當前的 PageRank 值平均分配到本頁面包含的出鏈上，這樣每個鏈接即獲得了相應的權值；而每個頁面將所有指向本頁面的入鏈所傳入的權值求和，即可得到新的 PageRank 得分。當每個頁面都獲得了更新后的 PageRank 值，就完成了一輪 PageRank 計算。?

具體實例

如果只是上面的介紹，雖然寫的很明白，但是對于初學者來說還是理解很費勁的，至少我第一次看到這些概念其實還是不太懂。所以打算舉個例子，通過例子來形象的說明一下這個問題。將 網頁 作如下抽象：

將每個網頁抽象成一個節點

如果一個頁面 A 有鏈接直接鏈向 B，則存在一條有向邊從 A 到 B

因此，整個 Web 被抽象為一張有向圖。

▲ 網頁抽象圖

3.1 PageRank初始化

PageRank 值簡稱 PR 值，意義是一個網頁被訪問的概率，初始時用戶訪問每個頁面的概率均等，假設一共有 N 個網頁，每個網頁的初始 PR 值 = 1 / N。

繼續沿用先前的圖，初始 PR 值向量?

3.2 PageRank計算

在計算之前，我們來講一下鄰接矩陣和概率轉移矩陣。

?

上面左圖是鄰接矩陣，以列為源，行為目標節點，那么從 A 到 B，C，D 都能連通，那么矩陣對應的位置都為1，即 [0,1,1,1]。因為是有向圖，所以 B 不能到 A，B 可以到 C、D，因此第二列是 [0 0 1 1]，以此類推構建鄰接矩陣。

那么 A 節點有多大的概率跳到 B 節點呢？因為 A 節點有三個出度，所以分給 B，C，D 各三分之一。B 節點有兩個出度，給 C、D 各二分之一，以此類推構建概率轉移矩陣，如上面右圖。

概率轉移矩陣*初始 PR 值向量得到迭代一次后的 PR 值。通過構造概率轉移矩陣，能把出度的值分出來；矩陣的乘法正好滿足了把出度上面的值給了入度節點的，并且求了加和，滿足了 PageRank 的數量和質量需求。

以此類推，PR 值向量，不斷左乘概率轉移矩陣 M，更新 PR 值，直到 P 收斂，即?。

3.3 終止點問題

上面網絡結構圖是一個馬爾科夫過程的實例，要滿足收斂性，需要具備一個條件：

圖是強連通的，即從任意網頁可以到達其他任意網頁。

實際中互聯網上網頁可能不滿足強連通性，有的網頁不指向任何網頁。如果按照上面矩陣相乘的計算，會導致前面累計的轉移概率被清零，這樣下去，最終的得到的概率分布向量所有元素幾乎都為 0。假設我們把上面圖中 C 到 D 的鏈接改成 D 到 C，C 變成了一個終止點，得到下面這個圖：

▲ C終止點

概率轉移矩陣變成了

?

由于第三列全部為 0，這樣在每次矩陣相乘的過程，這個分量都是 0，會被轉移到所有節點，最終 PR 值向量的值都為 [0,0,0,0]。

3.4 陷阱問題

另外一個問題就是陷阱問題，即有些網頁不存在指向其他網頁的鏈接，但存在指向自己的鏈接。比如下面這個圖：

▲ 自指性不指向其他

當從其他網頁鏈接到 C 網頁后，就像跳進了陷阱，陷入了漩渦，再也不能從 C 中出來，將最終導致概率分布值全部轉移到 C 上來，這使得其他網頁的概率分布值為 0，結果變為 [0,0,1,0]，從而整個網頁排名就失去了意義。如果按照上面圖對應的轉移矩陣為：

3.5 改進的PageRank公式

一個上網者，隨機瀏覽頁面有兩個選擇：

從當前頁面跳轉

在瀏覽器中直接輸入新地址

上網者通過點擊鏈接開啟新頁面的概率為 d（d 也稱阻尼系數，通常取 0.85）。此時，我們的 PageRank 模型變為：在每一個頁面，用戶都有 d 的概率通過點擊鏈接進入下一個頁面；此外，還有 1-d 的概率隨機跳轉，此時跳轉到其他頁面的概率為 1/M（M 表示網頁的總結點）。改進后的 PageRank 公式為：

：網頁??的 PageRank 值；?表示 網頁??鏈入合集中的某個網頁；?: 網頁?鏈入的集合；?：表示鏈入網頁 j 的 PageRank 值；：表示網頁? 鏈出的數量；m 表示圖中節點的個數；d：阻尼系數，任意時刻，用戶鏈接到某個網頁其他網頁對他的貢獻的系數；（1-d=0.15）：表示網頁鏈接，隨機跳到新網頁的概率，取值范圍：，Google 設為 0.85。

PR 值計算過程變為：

由于存在一定的概率跳出循環，因此可以避免陷阱問題。

3.6 PageRank優缺點

優點：是一個與查詢無關的靜態算法，所有網頁的 PageRank 值通過離線計算獲得；有效減少在線查詢時的計算量，極大降低了查詢響應時間。

缺點：

人們的查詢具有主題特征，PageRank 是主題無關的；因為下一時刻 PageRank 值與前一時刻的 PageRank 值無直接關系，即算法是主題無關的，只取決于入度的權重。假設有一個搜索引擎，其相似度計算函數不考慮內容相似因素，完全采用 PageRank 來進行排序，那么這個搜索引擎的表現是什么樣子的呢？這個搜索引擎對于任意不同的查詢請求，返回的結果都是相同的，即返回 PageRank 值最高的頁面。

舊的頁面等級會比新頁面高。因為即使是非常好的新頁面也不會有很多上游鏈接，除非它是某個站點的子站點。

3.7 簡單實現代碼

下面是上圖計算內容的簡單代碼，用 python3 寫的。雖然沒有 PageRank 的源碼那么完善，但是有助于學習 PageRank 算法的理解。

#?-*-?coding:?utf-8?-*- from?numpy?import?*def?pro_transfer(a):??#?構建概率轉移矩陣b?=?transpose(a)??#?b為a的轉置矩陣c?=?zeros((a.shape),?dtype=float)for?i?in?range(a.shape[0]):for?j?in?range(a.shape[1]):c[i][j]?=?a[i][j]?/?(b[j].sum())print(c)print("===================================")return?cdef?init_pr(M):??#?PageRank值初始化pr?=?zeros((M.shape[0],?1),?dtype=float)??#?構造一個存放pr值得矩陣for?i?in?range(M.shape[0]):pr[i]?=?float(1)?/?M.shape[0]?print(pr)print("======================================")return?prdef?page_rank(m,?v):??#?計算pageRank值while?((v?==?dot(m,?v)).all()?==?False):#判斷pr矩陣是否收斂,(v?==?dot(m,?v)).all()判斷前后的pr矩陣是否相等，若相等則停止循環v?=?dot(m,?v)return?vdef?page_rank_d(d,?m,?v):??#?計算pageRank值,增加阻尼系數while?((v?==?d?*?dot(m,?v)?+?(1?-?d)?/?m.shape[0]).all()?==?False):#?判斷pr矩陣是否收斂,(v?==?d?*?dot(m,?v)?+?(1?-?d)?/?m.shape[0]).all()判斷前后的pr矩陣是否相等，若相等則停止循環v?=?d?*?dot(m,?v)?+?(1?-?d)?/?m.shape[0]return?vif?__name__?==?"__main__":a_matrix?=?array([[0,?0,?0,?1],[1,?0,?0,?1],[1,?1,?0,?0],[1,?1,?1,?0]],?dtype=float)??#?構建鄰接矩陣M?=?pro_transfer(a_matrix)??#?構建概率轉移矩陣pr?=?init_pr(M)d?=?0.85??#?阻尼系數print(page_rank(M,?pr))??#?計算pr值,無阻尼系數print("==================================")print(page_rank_d(d,?M,?pr))#?計算pr值,有阻尼系數

反欺詐方向應用

在反欺詐方向的應用有不少，可以發現一些網頁抱團，相互鏈接，沒有實質性的內容，以及將高權重的網頁出售給作弊的網站，來提高自己的排名。可以通過降低他們的 PageRank 值來減少他們對網頁權重的影響。

下面我舉一個不是網頁方面反作弊的例子，以金融反欺詐中發現惡意貸款或者不明資金轉賬的團伙成員關系的場景為例子，兩個假設如下：

數量假設：如果很多人轉賬給一個人員，說明這個人員更加重要。

質量假設：假設有個用戶叫張三，轉賬給張三的人的質量不同。質量低的人員向張三轉賬傳遞的權重小，質量高的人員向張三轉賬傳遞的權重大；越多質量高的人員向張三轉賬，說明張三越重要。

4.1 實踐過程

可以套用改進的 PageRank 公式，那么原始公式中變成以下含義：

?:??人員的 PageRank 值；：人員的總數；?表示??鏈入合集中的某個成員；?:??鏈入人員的集合；?：表示鏈入人員??的 PageRank 值；?：表示? 鏈出人員的數量；d：阻尼系數，任意時刻，用戶鏈接到張三后，其他人對張三貢獻的概率系數；（1-d=0.15）：表示用戶鏈接，隨機跳到新人員的概率，取值范圍：，Google 設為 0.85。

初始化階段：人員通過鏈接關系構建有向圖，有鏈接關系的初始化 PageRank 值為1，沒有鏈接關系的初始化為 0，從而構造了鄰接矩陣；之后使用鄰接矩陣構建概率轉移矩陣；

在一輪更新人員 PageRank 值的時候，都是將其 PageRank 值鏈出，指向出鏈上的每個人員即可獲得相應的權值，每個人員指向自己的入鏈所傳入的權值和就是其新的 PageRank 得分。

當所有人的 PageRank 都更新后，就完成了一輪迭代。在每一輪迭代中，人員當前的 PageRank 值會不斷得到更新。通過若干輪的計算，每人會獲得最終的 PeopleRank 值。（本質是計算鄰接矩陣的特征值）?

4.2 應用實例

還是借助上文中的圖繼續說明如何應用于反作弊，假設 A, B, C, D 是一個團伙，可以計算出團伙中成員的重要程度，也就是他們的 pageRank 值。可以看出 D-->B-->C-->A 的重要程度依次減弱。

▲ 整個實例

問：一個思考小問題，影響團伙成員的關系不僅僅有轉賬人數、轉賬人的質量，還應該有轉賬的總金額，如何去設計一個更加完善的 PageRank 呢？

答：轉賬的總金額全局歸一化后，可以設計為邊的權重，來表達數額的重要性。TextRank 就是一種帶權重的 PageRank 衍生出來的。

TextRank

文章提取有兩種方式，抽取式和生成式。抽取式提取文中關鍵信息，可以是詞也可以是句子。生成式使用自然語言理解生成技術，形成自我總結的詞句，不是文章中的原文，算法相對復雜，可控性差一些。TextRank 是基于 PageRank，用于提取文本的關鍵詞和摘要，屬于抽取式的方式。

在 TextRank 的論文中，PageRank 表述為：使用?表示有向圖， 由節點?集合和??邊集合組成。??是??的子集。對于一個給定的點?,???為 指 向 該 點 的 點 集 合 ,??為點??指向的點集合。點??的得分定義如下:

?是阻尼系數，一般設置為 0.85。

問：為什么這里的PageRank介紹公式和上文的介紹公式不同？

答：因為這是兩個論文，上面的是 PageRank 論文中寫的，這個是 TextRank 論文中表述的 PageRank 的公式。我是忠于他們的原文，這樣便于更好的銜接 TextRank 算法的介紹，雖然兩者符號上有差異，但是表述的內容是一致的。

自然語言文本構建包括從文本中提取的單元（節點）之間有多個或部分鏈接。因此，將兩個節點和??之間的連接強度用權重??表示，并添加到連接兩個節點的相應邊上。因此類比 PageRank 引入了一個新的公式如下:

基于圖的排名算法在自然語言文本應用中包括以下主要步驟：

確定定義的文本單元，將其添加到圖形的節點中。

確定連接這些文本單元的關系，邊可以是有向或無向的，加權或未加權的。

迭代基于圖的排名算法，直到收斂為止。

根據最終得分對節點排序，使用附加到每個節點的值進行排名/選擇決策。

5.1 基于TextRank的關鍵詞提取

關鍵詞抽取的任務就是從一段給定的文本中自動抽取出一個或多個重要的詞語。TextRank 算法是利用詞匯之間的共線關系對后續關鍵詞進行排序，具體步驟如下：

將給定文本按照整句進行分割，即 ；

對于每個句子 ，對其進行分詞和詞性標注，然后剔除停用詞，只保留指定詞性的詞，如名詞、動詞、形容詞等，即 ，其中 保留后的候選關鍵詞；

構建詞圖 ，其中 V 為節點集合，由以上步驟生成的詞組成，然后采用共現關系構造任意兩個節點之間的邊：兩個節點之間存在邊僅當它們對應的詞在長度為 K 的窗口中共現，K 表示窗口大小，即最多共現 K 個單詞，一般 K 取 2；其實這里也可以改成 word2vec 來表示兩個詞，之后采用相似度衡量公式，例如余弦相識度來衡量兩個詞的相似性，根據實際效果來選擇相似度的方式。

根據上面的公式，迭代計算各節點的權重，直至收斂；

對節點的權重進行倒序排序，從中得到最重要的 t 個單詞，作為 top-t 關鍵詞；

對于得到的 top-t 關鍵詞，在原始文本中進行標記，若它們之間形成了相鄰詞組，則作為關鍵詞組提取出來。

▲ 論文中關鍵詞抽取圖和效果

5.2 基于TextRank的文章摘要提取

從文章中提取關鍵句，將每個句子作為一個節點，兩個句子節點對應的邊是無向有權的，他們的相似性衡量公式如下：

?和?: 兩個句子；: 句子中的詞。

公式中：分子部分同時出現在兩個句子中的同一個詞的數量；分母是對句子中詞的個數求對數后求和，這樣的目的是為了遏制較長的句子在相似度計算上的優勢。

這個相似度衡量公式感覺像是 Jaccard 相似度衡量公式的改版，相似度也可以將句子改成 word2vec 之后采用余弦相似度或者其他相似度公式衡量兩個句子的相似性，具體看實際效果。

其他步驟和關鍵詞提取步驟類似，不同點在于根據相似度計算公式遍歷計算任意兩個節點之間的相似度，設置閾值去掉兩個節點之間相似度較低的邊連接，構建出節點連接圖，然后迭代計算每個節點的 TextRank 值，排序后選出 TextRank 值最高的幾個節點對應的句子作為關鍵句。

5.3 PageRank和TextRank異同點

TextRank 從 PageRank 衍生出來的，思想有共通之處都是通過圖模型構造節點和邊，節點的值表示重要程度。

區別在于，PageRank 的網絡構建是根據網頁之間的鏈接關系，而 TextRank 的網絡構建是根據詞句的共線關系；PageRank 構造的網絡中的邊是有向無權邊，而 TextRank 構造的網絡中的邊是無向有權邊。

一點感想

有時候我們對算法不夠了解，有時候只是知道算法在他原始的應用場景或者同類的應用場景；如果我們能在對算法有全面了解的基礎上，拓寬思路和擴展思維方式，有種破界創新的勇氣，這樣有利于各種算法和產業更好的相結合，促進算法落地和擴展在業務中的應用范圍。

參考文獻

[1]http://ilpubs.stanford.edu:8090/422/1/1999-66.pdf

[2]https://web.eecs.umich.edu/~mihalcea/papers/mihalcea.emnlp04.pdf

[3]https://blog.csdn.net/hguisu/article/details/7996185

[4]http://ilpubs.stanford.edu:8090/457/1/2000-37.pdf

[5]https://blog.csdn.net/weixin_43378396/article/details/90322422

[6]https://blog.csdn.net/qq_40276310/article/details/81215665?utm_medium=distribute.pc_aggpage_search_result.none-task-blog-2~all~first_rank_v2~rank_v25-1-81215665.nonecase&utm_term=textrank算法

更多閱讀

#投 稿?通 道#

?讓你的論文被更多人看到?

如何才能讓更多的優質內容以更短路徑到達讀者群體，縮短讀者尋找優質內容的成本呢？答案就是：你不認識的人。

總有一些你不認識的人，知道你想知道的東西。PaperWeekly 或許可以成為一座橋梁，促使不同背景、不同方向的學者和學術靈感相互碰撞，迸發出更多的可能性。?

PaperWeekly 鼓勵高校實驗室或個人，在我們的平臺上分享各類優質內容，可以是最新論文解讀，也可以是學習心得或技術干貨。我們的目的只有一個，讓知識真正流動起來。

?????來稿標準：

? 稿件確系個人原創作品，來稿需注明作者個人信息（姓名+學校/工作單位+學歷/職位+研究方向）?

? 如果文章并非首發，請在投稿時提醒并附上所有已發布鏈接?

? PaperWeekly 默認每篇文章都是首發，均會添加“原創”標志

?????投稿郵箱：

? 投稿郵箱：hr@paperweekly.site?

? 所有文章配圖，請單獨在附件中發送?

? 請留下即時聯系方式（微信或手機），以便我們在編輯發布時和作者溝通

????

現在，在「知乎」也能找到我們了

進入知乎首頁搜索「PaperWeekly」

點擊「關注」訂閱我們的專欄吧

關于PaperWeekly

PaperWeekly 是一個推薦、解讀、討論、報道人工智能前沿論文成果的學術平臺。如果你研究或從事 AI 領域，歡迎在公眾號后臺點擊「交流群」，小助手將把你帶入 PaperWeekly 的交流群里。

總結

以上是生活随笔為你收集整理的从PageRank到反欺诈与TextRank的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。