PageRank算法及優化綜述報告

prprpr（指PageRank）

PageRank算法及優化綜述報告
前言
Simplified PageRank
PageRank
Weighted PageRank (WPR)
PageRank based on Visits of Links (VOL)
Weighted PageRank based on Visits of Links (WPR(VOL))
Enhanced Weighted PageRank based on Visits of Links (EWPR(VOL))
局部近似算法（基于\(Push\)操作的APXPR算法）
代碼實現
- Weighted PageRank based on Visits of Links
- 局部近似算法
總結
參考

PageRank算法及優化綜述報告

看完這些論文的感覺：Google提出了PageRank，之后十幾年一人改一點，就能一人寫一篇論文（霧）。
~~你一改我一改大家明天都能畢業~~
但WPR(VOL)和EWPR(VOL)真的毫無創新性，上一個算法提出后隔年就發出來了，感覺好水。

說是綜述報告，其實就是為了作業隨便寫的，隨便看看就好。

前言

關于PageRank的研究成果有很多，但與無權圖相比帶權圖的算法仍然較少。
因為個人目前水平和時間問題，只對PageRank及Weighted PageRank優化方向的幾個簡單算法進行介紹。

Simplified PageRank

L. Page, S. Brin等¹于1998年提出簡化的PageRank算法：

\[PR(u)=c\sum_{v\in B(u)}\frac{PR(v)}{N_v} \]

其中：\(u\)表示某個網頁，\(PR(u),PR(v)\)分別為\(u,v\)網頁的排序值（網頁的排名得分，即rank score），\(B(u)\)為連向\(u\)的網頁集合，\(N_v\)為\(v\)的出度，\(c=1.0\)為factor used for normalization（標準化參數？）。

所有網頁的排序值\(PR(x)\)可以通過迭代若干次計算。
但是，當一個網絡中存在兩個點及以上的環，且該環沒有出邊時，這個環會積累其它網頁的排序值而不會傳遞出去，使得所有連向該環的網頁的排序值變為\(0\)，不合實際。這個問題叫做rank sink。

PageRank

為解決rank sink，L. Page, S. Brin等¹根據隨機游走將簡化的PageRank改為：

\[PR(u)=(1-d)+d\sum_{v\in B(u)}\frac{PR(v)}{N_v} \]

其中：\(d\)為dampening factor（不跳出概率？），通常設為\(0.85\)。

相比Simplified PageRank，該算法考慮了用戶在瀏覽網頁時有概率跳出當前瀏覽的網頁，而任意再選擇其它網頁的情況，從而避免了rank sink。
作者測試了該算法，大概在\(O(\log n)\)次迭代后排序值會收斂。

Weighted PageRank (WPR)

PageRank算法的每次迭代，將每個網頁的排序值平均分給了它指向的網頁。但在實際中，同一網頁指向的不同鏈接的重要性可能不同，分到的排序值也應不同。
Wenpu Xing, Ali Ghorbani²在2004年發表Weighted PageRank Algorithm，提出了Weighted PageRank(WPR)算法：

\[PR(u)=(1-d)+d\sum_{v\in B(u)}PR(v)W_{(v,u)}^{in}W_{(v,u)}^{out} \]

\(W_{(v,u)}^{in}\)表示：考慮\(u\)的入度和\(v\)連向的所有點的入度，\(v\to u\)這條邊該分配\(v\)的多少權值：

\[W_{(v,u)}^{in}=\frac{I_u}{\sum_{p\in R(v)}I_p} \]

其中：\(I_u\)表示\(u\)的入度，\(R(v)\)表示\(v\)連向點的集合。

\(W_{(v,u)}^{out}\)表示：考慮\(u\)的出度和\(v\)連向的所有點的出度，\(v\to u\)這條邊該分配\(v\)的多少權值：

\[W_{(v,u)}^{out}=\frac{O_u}{\sum_{p\in R(v)}O_p} \]

其中：\(O_u\)表示\(u\)的出度，\(R(v)\)表示\(v\)連向點的集合。

作者認為，一個網頁越受歡迎，連向它的網頁和它連出的網頁越多。所以WPR根據\(v\)指向網頁集合\(R(v)\)中點的出度和入度，分配\(v\)的排序值。這樣\(v\)排序值會更多地分配到更受歡迎的網頁上，而不是均分。
作者實驗表明：將WPR用于搜索，得到的結果的相關性高于傳統PageRank算法。

PageRank based on Visits of Links (VOL)

Gyanendra Kumar等³在2011年發表Page Ranking Based on Number of Visits of Web Pages，提出了Page Ranking based on Visits of Links(VOL)算法：

\[PR(u)=(1-d)+d\sum_{v\in B(u)}\frac{L_uPR(v)}{TL(v)} \]

其中\(L_u\)表示通過鏈接\(v\to u\)訪問\(u\)的次數，\(TL(v)\)表示\(\sum_{u\in R(v)}L_u\)，即通過\(v\)上的鏈接訪問其它網頁的總次數。

該算法考慮了用戶的瀏覽傾向，根據用戶的實際瀏覽行為（鏈接的訪問數）決定哪個網頁更受歡迎，將更多的排序值分配到用戶瀏覽最多（更受歡迎）的網頁上。
VOL與之前算法相比具有如下特點：

具有動態性，更符合網頁搜索的特性。
結果不是僅與網絡結構相關，還與用戶行為有關，更具目標導向性；而之前算法中，網頁的排序值與用戶實際訪問該網頁的情況無關。
用戶可以在搜索的同時提高該算法的準確性。
一大問題是，需要動態統計每個網頁上用戶的瀏覽行為。

綜上，VOL比傳統PageRank的搜索結果更相關，但也帶來了具體實現的問題。

Weighted PageRank based on Visits of Links (WPR(VOL))

Neelam Tyagi, Simple Sharma⁴在2012年發表Weighted Page Rank Algorithm Based on Number of Visits of Links of Web Page，提出了Weighted PageRank based on Visits of Links(WPR(VOL))算法：

\[WPR_{VOL}(u)=(1-d)+d\sum_{v\in B(u)}\frac{L_uWPR_{VOL}(v)W_{(v,u)}^{in}}{TL(v)} \]

其中：\(WPR_{VOL}(u)\)是WPR(VOL)算法計算出的\(u\)的重要性\(PR(u)\)，\(W_{(v,u)}^{in}\)是WPR中，考慮\(u\)的入度和\(v\)連向的所有點的入度，\(v\to u\)這條邊該分配\(v\)的多少權值：

\[W_{(v,u)}^{in}=\frac{I_u}{\sum_{p\in R(v)}I_p} \]

因為VOL算法中考慮了出度影響的受歡迎程度（即\(\frac{L_u}{TL(v)}\)），作者沒有使用\(W_{(v,u)}^{out}=\frac{O_u}{\sum_{p\in R(v)}O_p}\)。
該算法將WPR（網頁的受歡迎程度）與VOL（用戶的實際瀏覽行為/鏈接的訪問數）結合，按照另一種比例分配排序值。
WPR(VOL)的特點、問題與VOL基本相同，但搜索結果相關性更強。

但是作者在所給例子的計算過程中，\(R(u)\)與\(B(u)\)搞混了，結果都是錯的，這也能發論文嗎。（下面EWPR(VOL)中這里沒有錯）

Enhanced Weighted PageRank based on Visits of Links (EWPR(VOL))

Sonal Tuteja⁵在2013年發表Enhancement in Weighted PageRank Algorithm Using VOL，對WPR(VOL)算法進行了優化：

\[EWPR_{VOL}(u)=(1-d)+d\sum_{v\in B(u)}WPR_{VOL}(v)W_{(v,u)}^{in}W_{(v,u)}^{out} \]

改進的原因是，作者認為WPR(VOL)算法中沒有考慮\(W_{(v,u)}^{out}\)（事實上考慮過這點），需要加上，于是就乘了個\(W_{(v,u)}^{out}\)然后發了篇新論文。
但是，公式中的\(WPR_{VOL}\)是指WPR(VOL)還是EWPR(VOL)中的網頁排序值？

如果是前者，那代入后完整公式應為：

\[EWPR_{VOL}(u)=(1-d)+d\sum_{v\in B(u)}\frac{L_uEWPR_{VOL}(v)\big(W_{(v,u)}^{in}\big)^2W_{(v,u)}^{out}}{TL(v)} \]

為什么\(W_{(v,u)}^{in}\)就要算兩次？作者沒有說明\(W^{in},W^{out}\)為什么不同。

如果是后者，那EWPR(VOL)與WPR算法不一樣嗎？

下面有作者給出的例子，例子與介紹VOL算法中的例子相同，包含visit of links。但是，給出的計算過程中沒有出現形如\(\frac{L_u}{TL(v)}\)的對visits的考慮。所以上面問題答案是后者，那例子中的EWPR(VOL)就是WPR（迷惑起來了）。
然后作者給出了WPR與EWPR(VOL)在\(d\)取不同值時的不同結果，這個不同結果是如何得出來的？所以個人認為是作者的例子計算過程寫錯了，公式也有問題。
公式應為：

\[EWPR_{VOL}(u)=(1-d)+d\sum_{v\in B(u)}\frac{L_uEWPR_{VOL}(v)W_{(v,u)}^{in}W_{(v,u)}^{out}}{TL(v)} \]

可能是我水平低吧，我認為這篇論文/這算法和CtrlCV沒區別，還有問題，這期刊隨便發嗎。

局部近似算法（基于\(Push\)操作的APXPR算法）

彭茂、張媛⁶在2016年發表《帶權網絡的個性化PageRank計算_彭茂》，提出了基于\(Push\)操作的PageRank計算方法，其時間復雜度優于傳統迭代算法。

記\(s\)為PageRank中各點排序值構成的向量，\(p(s)\)為計算后的\(s\)向量，\(W\)為狀態轉移矩陣，\(\alpha=1-d\)為跳出概率。則可知\(p(s)\)為如下方程的唯一解：

\[p(s)=\alpha s+(1-\alpha)p(s)W \]

傳統迭代算法可表示為：

\[p^{k}=\alpha s+(1-\alpha)p^{k-1}W \]

算法的誤差限通常定義為：\(||p^k-p^{k-1}||\leq\varepsilon\)，時間復雜度為\(O\left(\frac{m\log\varepsilon}{\log(1-\alpha)}\right)\)。

作者給出了帶權圖的一個近似PageRank計算方法，復雜度上界為\(O\left(\frac{\Delta}{\varepsilon\alpha}\right)\)，其中\(\Delta\)為圖頂點的最大出度。算法如下。

若\(r\)為非負向量，且對任意頂點\(v\)有\(r(v)\leq\varepsilon\cdot outdgree(v)\)，則稱向量\(p(s-r)\)為PageRank向量\(p(s)\)的\(\varepsilon-\)近似。
該算法持續更新一個向量對\((p,r)\)，使其始終滿足：

\[p(I-(1-\alpha)W)=\alpha(s-r) \]

即

\[r=s-p\left(\frac{1}{\alpha}I-\frac{1-\alpha}{\alpha}W\right) \]

算法初始時\(p=0,r=s\)，\(p,r\)通過如下\(Push\)操作更新（\(p',r'\)為\(Push\)操作后所得向量）：

對某個點\(u\)：

\(p'(u)=p(u)+\alpha\cdot\beta\cdot r(u)\)

\(r'(u)=r(u)-\beta\cdot r(u)+(1-\alpha)w_{u,u}\cdot\beta\cdot r(u)\)

\(r'(v)=r(v)+(1-\alpha)w_{u,v}\cdot\beta\cdot r(u)\)（對所有滿足\((u,v)\in E\)的\(v\)）
未更新的\(p'=p,r'=r\)。
若\(W=D^{-1}A=(w_{ij})_{n\times n}\)為轉移矩陣，則\(w_{u,u}=0\)；\(\beta\)為預設值，默認為\(\frac12\)。

可知\(p=p(s-r)\Rightarrow p'=p(s-r')\)。
因為\(Push\)過程可以看做，\(r\)中的某些概率轉移到了\(p\)中，所以對所有滿足\(r(u)\geq\varepsilon\cdot outdgree(u)\)的點執行\(Push\)操作，可得到如下計算\(\varepsilon-\)近似PageRank向量方法：

ApxPR(s, α, ε)
    Let p=0 and r=s
    while r(u)>ε*outdgree(u) for some vertex u
        Pick any vertex u where r(u)>ε*outdgree(u)
        Apply Push(u)
    return p and r

作者證明了該APXPR算法時間復雜度為\(O\left(\frac{\Delta}{\varepsilon\alpha}\right)\)，其中\(\Delta\)為圖頂點的最大出度，遠優于迭代算法的\(O\left(\frac{m\log\varepsilon}{\log(1-\alpha)}\right)\)。

該算法也支持動態帶權網絡修改，更新網絡一條邊的復雜度為\(O\left(\frac{\Delta}{\varepsilon\alpha^2}\right)\)，且實際計算時間會小很多。而傳統冪迭代法只能重新計算。動態網絡的計算這里不再展開。

此外，作者介紹了蒙特卡洛策略計算PageRank向量的方法，也支持在線更新網絡。對于一個\(n\)個頂點、\(m\)條邊的圖，保持\(m\)條邊持續更新的復雜度為\(O\left(\frac{nRf}{\alpha^2}\right)\)。

作者通過實驗得出：

靜態圖中\(Push\)算法與蒙特卡洛算法均優于冪迭代法；圖的稠密度較高時蒙特卡洛算法優于\(Push\)算法。
動態圖中，在圖的更新量較少時，\(Push\)算法優于蒙特卡洛方法。

代碼實現

對WPR(VOL)算法與ApxPR算法的簡單實現（節點數較小時）。
在節點數、邊數不大時，算法實現很簡單，但當節點數很大，即現實中網頁數非常多時，可能需要改進實現方法。

Weighted PageRank based on Visits of Links

每次迭代復雜度為\(O(n+m)\)。

/*
Sample Input:
3 4
1 3 2
3 1 2
1 2 1
2 3 2
Output:
WPR[1]=0.6319057
WPR[2]=0.2096800
WPR[3]=0.5669479
*/
#include <bits/stdc++.h>
#define pc putchar
#define gc() getchar()
#define pb emplace_back
typedef long long LL;
const int N=1e3+5;
const double d=0.85;

inline int read()
{
	int now=0,f=1; char c=gc();
	for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
	for(;isdigit(c);now=now*10+c-48,c=gc());
	return now*f;
}

struct Edge
{
	int v,w;
};
struct Graph
{
	std::vector<int> e[N];
};
struct PageRank
{
	Graph R,B;
	int n,L[N][N],TL[N],I[N],O[N];
	double WPR[N],W_in[N][N],W_out[N][N];
	
	void AddEdge(int w,int v,int u)
	{
		R.e[u].pb(v), B.e[v].pb(u);
		++I[v], ++O[u], L[u][v]+=w, TL[u]+=w;
	}
	void Output()
	{
		for(int i=1; i<=n; ++i) printf("WPR[%d]=%.7f\n",i,WPR[i]);
	}
	void WPRVOL()
	{
		for(int u=1; u<=n; ++u)
		{
			double sum=0;
			for(auto v:B.e[u]) sum+=L[v][u]*WPR[v]*W_in[v][u]/TL[v];
			WPR[u]=1-d+d*sum;
		}
	}
	void Calc()
	{
//Init WPR
		for(int i=1; i<=n; ++i) WPR[i]=1;
//Calc W_in W_out
		for(int u=1; u<=n; ++u)
		{
			if(!R.e[u].size()) continue;
			int sumI=0,sumO=0;
			for(auto v:R/*B*/.e[u]) sumI+=I[v], sumO+=O[v];//這里WPR(VOL)論文中使用的B(u) 
			for(auto v:R.e[u]) W_in[u][v]=1.0*I[v]/sumI, W_out[u][v]=1.0*O[v]/sumO;
		}
//Calc values iteratively
		for(int T=300,t=1; t<=T; ++t)//應該有一個校驗誤差是否滿足的函數，不寫了 
		{
			WPRVOL();
//			printf("\nIteration %d:\n",t), Output();
		}
		Output();
	}
	void Init()
	{
		n=read();
		for(int m=read(); m--; AddEdge(read(),read(),read()));
		Calc();
	}
}PR;

int main()
{
	PR.Init();

	return 0;
}

局部近似算法

/*
Sample Input:
3 4
1 3 2
3 1 2
1 2 1
2 3 2
Output:
PR[1]=1.2303706
PR[2]=0.4986050
PR[3]=1.2710243
*/
#include <bits/stdc++.h>
#define pc putchar
#define gc() getchar()
#define pb emplace_back
typedef long long LL;
const int N=1e3+5;
const double d=0.85;
const double alpha=1-d, beta=0.5, epsilon=1e-8;

inline int read()
{
	int now=0,f=1; char c=gc();
	for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
	for(;isdigit(c);now=now*10+c-48,c=gc());
	return now*f;
}

struct Edge
{
	int v,w;
};
struct Graph
{
	std::vector<int> e[N];
};
struct PageRank
{
	Graph R,B;
	int n,I[N],O[N],A[N][N];
	double p[N],r[N],w[N][N];
	
	void AddEdge(int w,int v,int u)
	{
		R.e[u].pb(v), B.e[v].pb(u);
		++I[v], ++O[u], A[u][v]+=w;
	}
	void Output()
	{
		for(int i=1; i<=n; ++i) printf("PR[%d]=%.7f\n",i,p[i]);
	}
	int Exist(double e)
	{
		for(int u=1; u<=n; ++u)
			if(r[u]>e*O[u]) return u;
		return 0;
	}
	void Push(int u,double a,double b)
	{
		p[u]=p[u]+a*b*r[u];
		for(auto v:R.e[u]) r[v]=r[v]+(1-a)*w[u][v]*b*r[u];
		r[u]=r[u]-b*r[u]+(1-a)*0*b*r[u];
	}
	void ApxPR(double a,double e,double b)
	{
//Init
		for(int i=1; i<=n; ++i) p[i]=0, r[i]=1;
//APXPR
		int u;
		while(u=Exist(e),u) Push(u,a,b);
	}
	void Init()
	{
		n=read();
		for(int m=read(); m--; AddEdge(read(),read(),read()));
//Calc wij
		for(int i=1; i<=n; ++i)
		{
			int D=0;
			for(int j=1; j<=n; ++j) D+=A[i][j];
			for(int j=1; j<=n; ++j) w[i][j]=1.0*A[i][j]/D;
		}
//ApxPR 
		ApxPR(alpha,epsilon,beta);
		Output();
	}
}PR;

int main()
{
	PR.Init();

	return 0;
}

總結

PageRank最初的幾個算法雖然容易理解，但在當時確實很具有創新性，比如PageRank、Weighted PageRank和PageRank based on Visits of Links。
但是之后的提出的兩個算法 WPR(VOL)和EWPR(VOL)，只是簡單地將前面的算法進行結合，沒太有創新性，且內容都有很大的錯誤，合理懷疑只是在水論文。
除了冪迭代法，還有很多其它算法，也比迭代法更復雜、有創意。

參考

[1] 15036 The PageRank Citation Ranking

[2] 710 weightedPageRank

[3] 92 Page Ranking Based on Number of Visits of Web Pages

[4] 79 Weighted Page Rank Algorithm Based on Number of Visits of Links of Web Page

[5] 18 Enhancement in Weighted PageRank Algorithm Using VOL

[6] 帶權網絡的個性化PageRank計算

posted @ 2021-05-01 16:44 SovietPower 閱讀(3052) 評論(0) 收藏舉報

刷新頁面返回頂部

SovietPower

因你而起的一泓喜悲權當年輕留個紀念

PageRank算法及優化綜述報告

PageRank算法及優化綜述報告

前言

Simplified PageRank

PageRank

Weighted PageRank (WPR)

PageRank based on Visits of Links (VOL)

Weighted PageRank based on Visits of Links (WPR(VOL))

Enhanced Weighted PageRank based on Visits of Links (EWPR(VOL))

局部近似算法（基于\(Push\)操作的APXPR算法）

代碼實現

Weighted PageRank based on Visits of Links

局部近似算法

總結

參考

公告

SovietPower

因你而起的一泓喜悲 權當年輕 留個紀念

PageRank算法及優化 綜述報告

PageRank算法及優化 綜述報告

前言

Simplified PageRank

PageRank

Weighted PageRank (WPR)

PageRank based on Visits of Links (VOL)

Weighted PageRank based on Visits of Links (WPR(VOL))

Enhanced Weighted PageRank based on Visits of Links (EWPR(VOL))

局部近似算法（基于\(Push\)操作的APXPR算法）

代碼實現

Weighted PageRank based on Visits of Links

局部近似算法

總結

參考

公告

因你而起的一泓喜悲權當年輕留個紀念

PageRank算法及優化綜述報告

PageRank算法及優化綜述報告