pagerank演算法應用

1. 基於社區發現演算法和圖分析Neo4j解讀《權力的游戲》下篇

其中的分析和可視化是用Gephi做的，Gephi是非常流行的圖分析工具。但作者覺得使用Neo4j來實現更有趣。

節點中心度
節點中心度給出網路中節點的重要性的相對度量。有許多不同的方式來度量中心度，每種方式都代表不同類型的「重要性」。

度中心性(Degree Centrality)
度中心性是最簡單度量，即為某個節點在網路中的聯結數。在《權力的游戲》的圖中，某個角色的度中心性是指該角色接觸的其他角色數。作者使用Cypher計算度中心性：
MATCH (c:Character)-[:INTERACTS]- RETURN c.name AS character, count(*) AS degree ORDER BY degree DESC

character
degree

Tyrion
36

Jon
26

Sansa
26

Robb
25

Jaime
24

Tywin
22

Cersei
20

Arya
19

Joffrey
18

Robert
18

從上面可以發現，在《權力的游戲》網路中提利昂·蘭尼斯特（Tyrion）和最多的角色有接觸。鑒於他的心計，我們覺得這是有道理的。

加權度中心性（Weighted Degree Centrality）
作者存儲一對角色接觸的次數作為 INTERACTS 關系的 weight 屬性。對該角色的 INTERACTS 關系的所有 weight 相加得到加權度中心性。作者使用Cypher計算所有角色的這個度量：
MATCH (c:Character)-[r:INTERACTS]- RETURN c.name AS character, sum(r.weight) AS weightedDegree ORDER BY weightedDegree DESC

character
weightedDegree

Tyrion
551

Jon
442

Sansa
383

Jaime
372

Bran
344

Robb
342

Samwell
282

Arya
269

Joffrey
255

Daenerys
232

介數中心性（Betweenness Centrality）
介數中心性：在網路中，一個節點的介數中心性是指其它兩個節點的所有最短路徑都經過這個節點，則這些所有最短路徑數即為此節點的介數中心性。介數中心性是一種重要的度量，因為它可以鑒別出網路中的「信息中間人」或者網路聚類後的聯結點。

圖6中紅色節點是具有高的介數中心性，網路聚類的聯結點。
為了計算介數中心性，作者使用Neo4j 3.x或者apoc庫。安裝apoc後能用Cypher調用其170+的程序：
MATCH (c:Character) WITH collect(c) AS charactersCALL apoc.algo.betweenness(['INTERACTS'], characters, 'BOTH') YIELD node, scoreSET node.betweenness = scoreRETURN node.name AS name, score ORDER BY score DESC

name
score

Jon
1279.7533534055322

Robert
1165.6025171231624

Tyrion
1101.3849724234349

Daenerys
874.8372110508583

Robb
706.5572832464792

Sansa
705.1985623519137

Stannis
571.5247305125714

Jaime
556.1852522889822

Arya
443.01358430043337

Tywin
364.7212195528086

緊度中心性（Closeness centrality）
緊度中心性是指到網路中所有其他角色的平均距離的倒數。在圖中，具有高緊度中心性的節點在聚類社區之間被高度聯結，但在社區之外不一定是高度聯結的。

圖7 ：網路中具有高緊度中心性的節點被其它節點高度聯結
MATCH (c:Character) WITH collect(c) AS charactersCALL apoc.algo.closeness(['INTERACTS'], characters, 'BOTH') YIELD node, scoreRETURN node.name AS name, score ORDER BY score DESC

name
score

Tyrion
0.004830917874396135

Sansa
0.004807692307692308

Robert
0.0047169811320754715

Robb
0.004608294930875576

Arya
0.0045871559633027525

Jaime
0.004524886877828055

Stannis
0.004524886877828055

Jon
0.004524886877828055

Tywin
0.004424778761061947

Eddard
0.004347826086956522

使用python-igraph
Neo4j與其它工具（比如，R和Python數據科學工具）完美結合。我們繼續使用apoc運行 PageRank和社區發現（community detection）演算法。這里接著使用python-igraph計算分析。Python-igraph移植自R的igraph圖形分析庫。 使用 pip install python-igraph 安裝它。

從Neo4j構建一個igraph實例
為了在《權力的游戲》的數據的圖分析中使用igraph，首先需要從Neo4j拉取數據，用Python建立igraph實例。作者使用 Neo4j 的Python驅動庫py2neo。我們能直接傳入Py2neo查詢結果對象到igraph的 TupleList 構造器，創建igraph實例：
from py2neo import Graphfrom igraph import Graph as IGraph graph = Graph query = ''' MATCH (c1:Character)-[r:INTERACTS]->(c2:Character) RETURN c1.name, c2.name, r.weight AS weight '''ig = IGraph.TupleList(graph.run(query), weights=True)

現在有了igraph對象，可以運行igraph實現的各種圖演算法來。

PageRank
作者使用igraph運行的第一個演算法是PageRank。PageRank演算法源自Google的網頁排名。它是一種特徵向量中心性(eigenvector centrality)演算法。
在igraph實例中運行PageRank演算法，然後把結果寫回Neo4j，在角色節點創建一個pagerank屬性存儲igraph計算的值：
pg = ig.pagerank pgvs = for p in zip(ig.vs, pg): print(p) pgvs.append({"name": p[0]["name"], "pg": p[1]}) pgvs write_clusters_query = ''' UNWIND {nodes} AS n MATCH (c:Character) WHERE c.name = n.name SET c.pagerank = n.pg '''graph.run(write_clusters_query, nodes=pgvs)

現在可以在Neo4j的圖中查詢最高PageRank值的節點：
MATCH (n:Character) RETURN n.name AS name, n.pagerank AS pagerank ORDER BY pagerank DESC LIMIT 10

name
pagerank

Tyrion
0.042884981999963316

Jon
0.03582869669163558

Robb
0.03017114665594764

Sansa
0.030009716660108578

Daenerys
0.02881425425830273

Jaime
0.028727587587471206

Tywin
0.02570016262642541

Robert
0.022292016521362864

Cersei
0.022287327589773507

Arya
0.022050209663844467

社區發現（Community detection）

圖8
社區發現演算法用來找出圖中的社區聚類。作者使用igraph實現的隨機遊走演算法（ walktrap）來找到在社區中頻繁有接觸的角色社區，在社區之外角色不怎麼接觸。
在igraph中運行隨機遊走的社區發現演算法，然後把社區發現的結果導入Neo4j，其中每個角色所屬的社區用一個整數來表示：
clusters = IGraph.community_walktrap(ig, weights="weight").as_clustering nodes = [{"name": node["name"]} for node in ig.vs]for node in nodes: idx = ig.vs.find(name=node["name"]).index node["community"] = clusters.membership[idx] write_clusters_query = ''' UNWIND {nodes} AS n MATCH (c:Character) WHERE c.name = n.name SET c.community = toInt(n.community) '''graph.run(write_clusters_query, nodes=nodes)

我們能在Neo4j中查詢有多少個社區以及每個社區的成員數：
MATCH (c:Character) WITH c.community AS cluster, collect(c.name) AS members RETURN cluster, members ORDER BY cluster ASC

cluster
members

0
[Aemon, Alliser, Craster, Eddison, Gilly, Janos, Jon, Mance, Rattleshirt, Samwell, Val, Ygritte, Grenn, Karl, Bowen, Dalla, Orell, Qhorin, Styr]

1
[Aerys, Amory, Balon, Brienne, Bronn, Cersei, Gregor, Jaime, Joffrey, Jon Arryn, Kevan, Loras, Lysa, Meryn, Myrcella, Oberyn, Podrick, Renly, Robert, Robert Arryn, Sansa, Shae, Tommen, Tyrion, Tywin, Varys, Walton, Petyr, Elia, Ilyn, Pycelle, Qyburn, Margaery, Olenna, Marillion, Ellaria, Mace, Chataya, Doran]

2
[Arya, Beric, Eddard, Gendry, Sandor, Anguy, Thoros]

3
[Brynden, Catelyn, Edmure, Hoster, Lothar, Rickard, Robb, Roose, Walder, Jeyne, Roslin, Ramsay]

4
[Bran, Hodor, Jojen, Luwin, Meera, Rickon, Nan, Theon]

5
[Belwas, Daario, Daenerys, Irri, Jorah, Missandei, Rhaegar, Viserys, Barristan, Illyrio, Drogo, Aegon, Kraznys, Rakharo, Worm]

6
[Davos, Melisandre, Shireen, Stannis, Cressen, Salladhor]

7
[Lancel]

角色「大合影」
《權力的游戲》的權力圖。節點的大小正比於介數中心性，顏色表示社區（由隨機遊走演算法獲得），邊的厚度正比於兩節點接觸的次數。現在已經計算好這些圖的分析數據，讓我們對其進行可視化，讓數據看起來更有意義。
Neo4j自帶瀏覽器可以對Cypher查詢的結果進行很好的可視化，但如果我們想把可視化好的圖嵌入到其它應用中，可以使用Javascript可視化庫Vis.js。從Neo4j拉取數據，用Vis.js的neovis.js構建可視化圖。Neovis.js提供簡單的API配置，例如：
var config = { container_id: "viz", server_url: "localhost", labels: { "Character": "name" }, label_size: { "Character": "betweenness" }, relationships: { "INTERACTS": }, relationship_thickness: { "INTERACTS": "weight" }, cluster_labels: { "Character": "community" } }; var viz = new NeoVis(config); viz.render;

其中：
節點帶有標簽Character，屬性name；

節點的大小正比於betweenness屬性；

可視化中包括INTERACTS關系；

關系的厚度正比於weight屬性；

節點的顏色是根據網路中社區community屬性決定；

從本地伺服器localhost拉取Neo4j的數據；

在一個id為viz的DOM元素中展示可視化。

2. 數據挖掘演算法 PageRank

數據挖掘演算法：PageRank
1. 引言
PageRank是Sergey Brin與Larry Page於1998年在WWW7會議上提出來的，用來解決鏈接分析中網頁排名的問題。在衡量一個網頁的排名，直覺告訴我們：
1、當一個網頁被更多網頁所鏈接時，其排名會越靠前；
2、排名高的網頁應具有更大的表決權，即當一個網頁被排名高的網頁所鏈接時，其重要性也應對應提高。
對於這兩個直覺，PageRank演算法所建立的模型非常簡單：一個網頁的排名等於所有鏈接到該網頁的網頁的加權排名之和：

PRi表示第i個網頁的PageRank值，用以衡量每一個網頁的排名；若排名越高，則其PageRank值越大。
網頁之間的鏈接關系可以表示成一個有向圖代表了網頁j鏈接到了網頁i；Oj為網頁j的出度，也可看作網頁j的外鏈數（ the number of out-links）。
假定P=(PR1,PR2,?,PRn)T為n維PageRank值向量，A為有向圖G所對應的轉移矩陣，

n個等式(1)可改寫為矩陣相乘：

但是，為了獲得某個網頁的排名，而需要知道其他網頁的排名，這不就等同於「是先有雞還是先有蛋」的問題了么？幸運的是，PageRank採用power iteration方法破解了這個問題怪圈。欲知詳情，請看下節分解。
2. 求解
為了對上述及以下求解過程有個直觀的了解，我們先來看一個例子，網頁鏈接關系圖如下圖所示：

那麼，矩陣A即為

所謂power iteration，是指先給定一個P的初始值P0，然後通過多輪迭代求解:

最後收斂於||Pk?Pk?1||<ξ，即差別小於某個閾值。
我們發現式子(2)為一個特徵方程（characteristic equation），並且解P是當特徵值（eigenvalue）為1時的特徵向量（eigenvector）。為了滿足(2)是有解的，則矩陣A應滿足如下三個性質：
1、stochastic matrix，則行至少存在一個非零值，即必須存在一個外鏈接（沒有外鏈接的網頁被稱為dangling pages）；
2、不可約（irrecible），即矩陣A所對應的有向圖G必須是強連通的，對於任意兩個節點u,v∈V，存在一個從u到v的路徑；
3、非周期性（aperiodic），即每個節點存在自迴路。
顯然，一般情況下矩陣A這三個性質均不滿足。為了滿足性質stochastic matrix，可以把全為0的行替換為e/n，其中e為單位向量；同時為了滿足性質不可約、非周期，需要做平滑處理：

其中，d為 damping factor，常置為0與1之間的一個常數；E為單位陣。那麼，式子(1)被改寫為

3. pagerrank演算法有何應用

．017 基於中心性和PageRank的網頁綜合評分方法 （1．西南交通大學信息科學與技術學院，四川成都610031；2．成都市公安局科技處，四川成都610017；3．西南財經大學經濟信息工程學院，四川成都610074） 摘要：為准確、高效地對網頁進行評分，提出了一種基於中心性（結點度、居間度和緊密度）和PageRank演算法 的網頁評分方法CentralRank．它採用PageRank演算法計算網頁分數，藉助中心性度量的方法計算頁面在Web社會 網路中的重要性．為了驗證CentralRank的性能優勢，設計了一個網頁抓取器，可利用該抓取器自動、准確地下載 網頁信息．該網頁抓取器集成了網路信息採集、頁面內容分析和頁面消重3項技術．基於大量真實數據的實驗結 果表明：CentralRank在保證網頁評分時間性能的前提下，比單純基於中心性的網頁評分演算法和PageRank演算法更 准確、有效，預測准確性分別提高約14．2％和7．5％． 關鍵詞：社會網路分析；Web社會網路；中心性；PageRank演算法；網頁評分 中圖分類號：TP311．13 文獻標志碼：A Hybrid Page Scoring Algorithm Based PageRankqtAO Shaojiel，PENG Jin92，H Tianruil，LI Iton91，12 Taiyon93，WANG Cha01 （1．School InformationScience Technology，SouthwestJiaotong University，Cheng 610031，China； 2．Department Technology，ChengMunicipal Public Security Bureau，Cheng 610017，China； 3．School EconomicInformation Engineering，soutllwtem University Economics，Cheng610074， China） Abst豫ct：In order scor

4. 對pagerank演算法的整理

1、首先先大致介紹下pagerank，pagerank是Google排名演算法法則的一部分，是用來標記網頁的等級的一種方法，也是用來衡量一個網頁好壞的唯一標准。pagerank他採用PR值來劃分網頁的受歡迎度，PR值越高，則表名受歡迎度越高，PR最高為10，最低為0，一般PR達到4，則表名網站已經不錯了。PR為4的網站比PR為3的網站不是單純的好一點來形容，他是一種里氏震級的形式來形容的，就好比地震的等級，是指數刻度增長的，因此可以想像PR為10的網站是一種什麼程度。因為這個演算法是Google提出的，因此Google將自己的網站PR值設置為10，所以想要自己的網站PR達到10，是非常難的，如果你的網站可以達到Google的水平。

2、介紹完了pagerank是一個什麼東西後，我們就來介紹一下pagerank如何計算的。

2.1、用個例子來說明下PageRank演算法

在網頁A中有B、C、D三個鏈接，在網頁B中有A、C兩個個鏈接，在網頁C中有D鏈接，網頁D中有A、B兩個鏈接。（可以看出這個圖是強鏈接的，任何一個節點都可以到達另一個節點）。

我們假設每一個鏈接訪問的概率是相同的，為了計算方便我們將每一個網頁的PageRank設置為1。

先給出計算公式

PR(pj) 表示網頁 pj 的 PageRank 得分，L(pj) 表示網頁 pj 的出鏈接數量，1/L(pj) 就表示從網頁 pj 跳轉到 pi 的概率。

所以我們來計算第一次迭代後的PR值：

PR(A)=PR(B)/2+PR(D)/2

PR(B)=PR(A)/3+PR(D)/2

PR(C)=PR(A)/3+PR(B)/2

PR(D)=PR(A)/3+PR(C)/1

PR(A)+PR(B)+PR(C)+PR(D)=1

PR(A)=0.265, PR(B)=0.235, PR(C)=0.206, PR(D)=0.294

通過上面的公式在不斷的進行迭代，可以得到一個收斂值，大概是在（0.265，0.235，2.206，0.294）附近。

2.2看完公式之後，我們來考慮倆種特殊的情況

2.2.1終止問題

上面過程要滿足收斂性，需要具備一個條件：圖是強連通的，即從任意網頁可以到達其他任意網頁。

互聯網中存在網頁不滿足強連通的特性，因為有一些網頁不指向任何網頁，按照上面公式迭代計算下去，導致前面累計得到的轉移概率被清零，最終得到的概率分布向量所有元素幾乎都為0。

假設把上面圖中C到D的鏈接丟掉，C變成了一個終止點，得到下面這個圖：

轉移矩陣M為：

不斷迭代，最終得到所有元素都為0。

2.2.2 、陷阱問題

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

這種情況下，PageRank演算法不斷迭代會導致概率分布值全部轉移到c網頁上，這使得其他網頁的概率分布值為0，從而整個網頁排名就失去了意義。如果按照上面圖則對應的轉移矩陣M為：

不斷迭代，最終得倒如下結果：

為了解決終止點問題和陷阱問題 ，下面需要對演算法進行改進。假設選取下一個跳轉頁面時，既不選 當前頁面 ，也不選 當前網頁上的其他鏈接 ，而是以一定概率跳轉到其他不相關網頁，那麼上面兩個問題就能得到很好的解決，這就是 完整 PageRank 演算法思想 。

N表示的時網頁鏈接的個數，α表示不進行隨機跳轉的概率。

利用上面公式繼續迭代下去，直到收斂，得到最終rank值。

PageRank 的計算是采樣迭代法實現的：一開始所有網頁結點的初始 PageRank 值都可以設置為某個相同的數，例如 1，然後我們通過上面這個公式，得到每個結點新的 PageRank 值。每當一張網頁的 PageRank 發生了改變，它也會影響它的出鏈接所指向的網頁，因此我們可以再次使用這個公式，循環地修正每個網頁結點的值。由於這是一個馬爾科夫過程，所以我們能從理論上證明，所有網頁的 PageRank 最終會達到一個穩定的數值。整個證明過程很復雜，這里我們只需要知道這個迭代計算的過程就行了。

3、基於本文主題叫做數學建模之美，也是一篇讀後感，所以我們還是寫一下感受吧。

這個演算法的優美之處，就在於巧妙地將網頁內容的好壞，根據鏈接數的形式，用PR值進行了排名，它不僅激發網頁越做越好，也促進了各個網頁之間的聯系。

同時在結構方面，他將一個復雜的問題，進行了簡單的類比，用圖結構的形式代替鏈接的形式，用戶訪問的順序，也就是節點的走向。所以數學之美就在於他是非常的簡單，用簡單的原理，向我們展示了一個復雜的問題。

5. pagerank演算法可以用來干什麼

目前很多重要的鏈接分析演算法都是在PageRank演算法基礎上衍生出來的。PageRank是Google用於用來標識網頁的等級/重要性的一種方法,是Google用來衡量一個網

6. pagerank演算法是什麼

PageRank演算法是谷歌曾經獨步天下的「倚天劍」，該演算法由Larry Page和Sergey Brin在斯坦福大學讀研時發明的。PageRank，網頁排名，又稱為網頁級別，Google左側排名，是一種由網頁之間相互的超鏈接計算的技術，作為網頁排名的要素之一。

Google用它來體現網頁的相關性和重要性，在搜索引擎優化操作中是經常被用來評估網頁優化的成效因素之一。

PageRank的思想

PageRank認為，一個節點對系統施加影響的結果，就是與它相連的節點也具有一定的影響力。PageRank的想法看起來很簡單，實際上給我們留了一個難題：各個節點的PR值計算是存在依賴的，得先計算出PR(node1)才能計算PR(node0)。

也就是說需要首先把所有未被引用的節點的PR值算出來(一般默認是1.0)；然後把以它們為源頭、只和源頭相連、距離為1的節點的PR值算出來；接著計算距離為2、只和已經具有PR值節點相連的，所有節點的PR值；直到所有的節點都有PR值為止。這個計算方法復雜度比較高，不實用。

7. PageRank演算法實現好友推薦(演算法原理)

對於社交系統與電商網站，推薦系統佔有很重要的位置，當數據量越來越大的時候，用戶無法確定該選擇什麼商品，因此在電商系統中需要按照興趣或者相似度給用戶推薦相應的商品。相應的，在一個大型社交網路平台中，對於一些用戶，我們希望推薦一些知名度較高，活躍度較高或者感興趣的用戶，比如一些明星，歌手，演員等等。在社交網路中，PageRank演算法有著廣泛的應用，因此，本篇文章主要介紹其原理。

對於大部分社交系統來說，如果只是簡單的獲取好友的信息遠遠不夠，我們可以通過獲取好友的好友的信息來擴展用戶的朋友圈，使得信息量更加豐富，本項目中使用PageRank演算法來完成二級鄰居，然後按照Rank排序，選擇Top5用戶實現用戶的好友的好友的推薦。

PageRank演算法由Google的創始人拉里·佩奇和謝爾·布林於1998年發明.這項技術設計之初是為了體現網頁的相關性和重要性,在搜索引擎優化操作中經常被用來評估網頁優化的成效因素之一.

從技術上看,搜索引擎需要解決以下三個問題:

本質就是一個爬蟲問題,通過爬蟲獲取整個互聯網的數據

關鍵在於快速找到.

它的實現方式有: 倒排索引，簽名文件，後綴樹等。我們最熟悉的是 倒排索引 。(並不熟悉,以後有機會再看)

排序是Google的搜索引擎能夠興起的一個決定性因素。

對網頁排序有很多種方式，我們來看三種：

就是原封不懂地把索引到的鏈接直接返回給用戶，缺點就不說了，想找自己感興趣的內容估計要費不少功夫。

這種方式是一種只從關鍵詞出現的次數和位置進行排序的方法。該方法以一個關鍵詞與網頁的相關度大小作為排序標准，而關鍵詞在網頁的相關度大小作為排序標准，而關鍵詞在網頁中的相關度則由它在網頁中出現的頻次和位置兩方面加權計算得出。

缺點也很明顯，容易出現刷分的情況，整篇文章中大量地刷關鍵詞就能提高排名。

真正找到計算網頁自身質量的完美的數學模型是Google的創始人拉里佩奇和謝爾蓋布林。 下一節講一下原理。

我們模擬一個悠閑的上網者，上網者首先隨機選擇一個網頁打開，然後在這個網頁上呆了幾分鍾後，跳轉到該網頁所指向的鏈接，這樣無所事事、漫無目的地在網頁上跳來跳去，PageRank就是估計這個悠閑的上網者分布在各個網頁上的概率，這個概率就代表這個網頁的重要性.

PageRank主要基於兩個重要的假設：

如果一篇文章被越來越多的人引用，那麼這篇文章可能就是一篇經典之作，如果這篇文章引用了其他的論文，那麼一定程度上這篇被引用的文章也是一篇很好的文章。應用到社交網路中，如果一個好友被更多的人關注，那麼說明該好友有很高的知名度和活躍度，那麼，我們可以將該好友推薦給用戶。

基於這兩個假設,我們可以總結出PageRank演算法的核心:

如下圖,可以更好的表達PageRank演算法的思想:

由上圖可知,每個頁面將自己的一部分rank傳遞給某個頁面，我們可以通過計算傳遞給某個頁面的所有rank值的和來計算出它的rank值，當然，不可能是通過一次計算完成，我們剛開始可以給每個頁面賦予一個初始rank值，比如 1/N(N為頁面總數) ，通過迭代計算得到該頁面的rank值。

迭代計算停止的條件為:

使用有向圖表示:

這個例子中只有四個網頁，如果當前在A網頁，那麼悠閑的上網者將會各以1/3的概率跳轉到B、C、D，這里的3表示A有3條出鏈，如果一個網頁有k條出鏈，那麼跳轉任意一個出鏈上的概率是1/k，同理D到B、C的概率各為1/2，而B到C的概率為0。

我們在做計算的時候會將該圖表示成一個二維的矩陣，我們做一個轉換，就會變成下圖的矩陣形式。 M(i,j) 表示j節點指向i節點的概率 ，一般來說每列和為1。

生成的 轉移矩陣 非常簡單, 矩陣的每一列代表該頂點所代表的頁面除以對應頁面的出鏈數得到的 。

有了轉移矩陣，我們可以來定義行向量 V ， V 的第i個分量記錄 對應的Rank值，因此一次Rank的更新可以表示為：

在演算法的第一輪計算中，我們假設上網者在每一個網頁的概率都是相等的，即1/n，於是初試的概率分布就是一個所有值都為1/n的n維列向量 ，用 去右乘轉移矩陣M，就得到了第一步之後上網者的概率分布向量 ,得到一個nX1的矩陣 ， 這個 一輪迭代計算出來的PageRank值 。下面是 的計算過程：

得到了 後，再用 去右乘M得到 ，一直下去，即 , 最終V會收斂 .

不斷的迭代，最終得到結果.

但是在迭代計算中，我們需要考慮如下兩大阻力： Dead End 和 Spider Trap ：

Dead End就是指一個頁面只有入鏈但是沒有出鏈，這時轉移矩陣M的一列為零，導致最後結果為零。這時web不是強連通的，即存在某一類節點不指向別人，如下圖的D。這個時候我們的演算法就會出問題了，它不滿足收斂性了。

為什麼不滿足收斂性了？

Spider Trap指頁面的所有出鏈都指向自己，這樣會使迭代結果中只有自己的頁面的Rank值很高。其他頁面的Rank值為零。

要克服上面兩個問題，我們需要將迭代計算公式做如下轉變。我們可以加入一個 隨機跳轉 機制.

即假設每個頁面有很小概率擁有一個指向其他頁面的鏈接。

表現出來就是：其他頁面本來傳遞給一個頁面的Rank值需要做一個折扣，作為補償，可能需要一個頁面指向該頁面並且傳遞Rank值給該頁面，該跳轉的概率為β，因此表達式變為：

其中,N為頁面總數; e 為一個N維且各個分量都是1的向量;β通過經驗得知一般設為0.15.

此時的計算結果過程為:

有機會再寫,先空著