pagerank 没写完

参考链接：社区划分-PageRank算法的解析与Python实现_搜索与推荐Wiki的博客-CSDN博客_pagerank算法python

        PageRank算法是一个迭代求解算法，可以处理网页排名（根据网页的重要性进行排序）、社会影响力分析、文本摘要 等问题。

        PageRank算法在1996年由Page和Brin提出

        PageRank适用于解决用有向图表示的图数据

---

PageRank算法是在图上执行一个随机游走模型，根据随机游走者 在有向图上 通过对 节点访问次数或访问概率 的高低 来判断有向图上各个节点的重要程度

首先给出算法的迭代公式，而后用一个实例对该迭代公式的各个部分的意义进行解释：

对于各个节点，其重要程度（其被访问概率）可以按以下公式迭代计算得出： 

（以节点X为例）

LaTeX：
PR(X)=(1-d)/N + d[ \, PR(T_{1})/C(T_{1}) \, + \, PR(T_{2})/C(T_{2}) + \cdots \, + PR(T_{n})/C(T_{n}) \, ] 

其中：

PR（X）表示节点的PR值，即节点X被访问到的概率，当迭代结束后，PR（X）则代表节点X的重要程度

d表示阻尼系数，指用户达到了当前节点后愿意沿图上的出边情况挑选任一节点继续向后游走的概率

表示在图上指向节点X的节点

表示节点的出度

---

        最初的PageRank算法是用于对网页的重要程度进行排名，那么我们就以网页排名作为该算法的一个实际例子对迭代公式的各部分进行解释：

        在我们访问网页的时候，网页A可能会链接到其他网页上，比如链接到网页B和网页C。

如果将这种网页间的链接关系体现在图结构数据上的话：那么，在图数据中，网页A、B、C均作为节点出现，且由于网页A可以链接到网页B和网页C，那么，在图上节点A应有两条出边，分别指向节点B和节点C。

        现在有如下的网页间的链接关系

        如图1示，有ABCD四个网页，网页间的链接关系有：A链接到BCD；B链接到AD；C链接到A；D链接到BC

        PageRank算法的核心思想就是：假设有一个随机游走者，在图上进行随机游走。

随机游走者经过多次游走后，对不同的节点有着不同的访问次数，显然，随机游走者访问次数多的节点有着更高的重要性。

算法就是在模拟随机游走者在图上的随机游走过程，所以每次算法对各个节点PR值的迭代更新都对应着随机游走者在图上的一次随机游走。

PS：随机游走者的"游走"体现为：如上图示若随机游走者当前所处位置为节点A，那么，随机游走者可以向BCD三个节点进行下一步的游走；随机游走者的"随机"体现在：随机游走者可以按照概率去随机选择下一个要游走到的节点【我不确定这段话应不应该加上去】

一、常规情况：

        直观来感受，若当前随机游走者在网页B上，由于网页B有两条出边分别链接到网页A和D，那么，它有1/2的概率跳转到网页A，有1/2的概率跳转到网页D。

由于网页B没有对网页C的跳转链接，所以图数据上BC两节点间没有边，所以跳转到网页C的概率为0

        因此，PageRank算法定义，对于一个网页，它可以跳转到k个其他网页上去（即，它在图上有k条出边），那么它跳转到这k个网页的概率都是1/k

        以图1为例，先初始化每个网页的被访问概率值PR=1，

        即：PR（A）=PR（B）=PR（C）=PR（D）=1

然后，对各个节点进行随机游走分析：

        如果随机游走者想访问到网页A，那么要分别从：网页B以1/2的概率链接到节点A；从网页C以1/1的概率链接到节点A；从网页D以0的概率链接到节点A。

然后分别代入访问网页BCD的访问概率值与对应各个网页链接到网页A的概率相乘，将上述三种情况发生的概率加和得到最终可以访问网页A的访问概率。

以上这些，对应节点PR值迭代公式的 ：

        每次迭代时，由于图结构不变，所以计算各节点的访问概率时，只有对应链接到该节点的对应节点PR值在变动，所以，为了加速计算，很自然的想到用矩阵来存储图的链接结构，我们称该矩阵为转移矩阵M，那么，对于本图结构，矩阵M为：

其中，M[i][j]表示链接到 i 节点的 j 节点其在图中可以链接到的所有节点的数目比（即，j 节点的出度值）

所以，第一次迭代可以计算为： 

 表示第 i 次迭代后的各个节点的访问概率；“   ” 表示数值的点乘；表示矩阵乘法

初始时，

那么经过一次迭代后，

Latex:
PR_{1}=M \otimes PR_{1}
=\begin{bmatrix} 0& 1/2& 1& 0\ 1/3& 0& 0& 0 \ 1/3& 0& 0& 1 \ 1/3& 1/2& 0& 0 \end{bmatrix} \otimes \begin{bmatrix}1\1\ 1\1\end{bmatrix}
=\begin{bmatrix}3/2\1/3\4/3\5/6\end{bmatrix}

按这种方式迭代10次，各节点的PR值变化如下：

迭代1000次，各点的PR值分别为：

PR(A)=1.494391 PR(B)=0.498127 PR(C)=1.245322 PR(D)=0.747192

对应代码如下：

#include 
using namespace std;

int main()
{
	double matrix[4][4]={0,0.5,1,0 , 0.33333,0,0,0 , 0.33333,0,0,1 , 0.33333,0.5,0,0  };
	double PR[4]={1,1,1,1};
	double PRtt[4]={0,0,0,0};
	/*for(int i=0;i<4;i++)
		for(int j=0;j<4;j++)
		{
			printf("%f ",matrix[i][j]);
		}*/
	for(int num=0;num<1000;num++)
	{
		for(int i=0;i<4;i++)
		{
			double tt=0;
			for(int j=0;j<4;j++)
			{
				tt += matrix[i][j]*PR[j];
			}
			PRtt[i]=tt;
		}
		PR[0]=PRtt[0];PR[1]=PRtt[1];PR[2]=PRtt[2];PR[3]=PRtt[3];			
		//printf("PR(A)=%f PR(B)=%f PR(C)=%f PR(D)=%f\n",PR[0],PR[1],PR[2],PR[3]);
	}
	printf("PR(A)=%f PR(B)=%f PR(C)=%f PR(D)=%f\n",PR[0],PR[1],PR[2],PR[3]);
	
	
	return 0;	
}

注意：

“每一轮迭代”的意思是，对节点ABCD的PR值都进行了一次更新。

        在上述的这种迭代方式中，对于第 i 轮的迭代：对每个节点的PR值进行更新的时候，都是用的上一轮（即 i-1 轮次）中各个节点的PR值进行计算的。

即：在第i轮迭代中，虽然对于节点B来说，新的PR值已经计算完了，但是，在计算CD节点的PR值时，仍旧采用的是B节点在i-1轮次的旧PR值。

那么，读者可能会有疑惑，如果实时更新，在同一轮中，用最新的节点PR值对接下来的其他节点进行更新会产生与上述方法有什么不同么

我们还是采用图1对应的图结构进行数值上的对比，只不过在这次的更新方式上，即使是在同一轮，PR（A）的值计算结束，接下来计算PR（B）的值时选择用刚得到的更新后的新的PR（A）的值。

对同一轮的其它节点的计算方法同理。

那么，代码如下：

#include 
using namespace std;

int main()
{
	double matrix[4][4]={0,0.5,1,0 , 0.33333,0,0,0 , 0.33333,0,0,1 , 0.33333,0.5,0,0 };
	double PR[4]={1,1,1,1};
	/*for(int i=0;i<4;i++)
		for(int j=0;j<4;j++)
		{
			printf("%f ",matrix[i][j]);
		}*/
	for(int num=0;num<10;num++)
	{
		for(int i=0;i<4;i++)
		{
			double tt=0;
			for(int j=0;j<4;j++)
			{
				tt += matrix[i][j]*PR[j];
			}
			PR[i]=tt;
		}			
		printf("PR(A)=%f PR(B)=%f PR(C)=%f PR(D)=%f\n",PR[0],PR[1],PR[2],PR[3]);
	}
	//printf("PR(A)=%f PR(B)=%f PR(C)=%f PR(D)=%f\n",PR[0],PR[1],PR[2],PR[3]);
	
	
	return 0;	
}

按这种方式迭代10次，各节点的PR值变化如下：

迭代1000次，各点的PR值分别为：

PR(A)=1.655606 PR(B)=0.551863 PR(C)=1.379663 PR(D)=0.827795

这样一对比，虽然最终对于这四个节点计算得来的PR值不同，但是迭代后得出的网页节点排名是相同的：A>C>D>B。

同时，对于收敛速度来看，仅对该图1对应的例子来说，是第一种方法收敛速度更快。

        但，直觉上，我还是会觉得采用第二种方式来更新各个节点的PR值更好一些，所以接下来的演示会采用第二种方式。

二、非常规情况：终止点问题   

对于图1，网页间是联通的，有一个很明显的连接                                                      

我们设置一个阻尼系数d，意思为随机游走者到达当前节点后，按照当前节点的链接愿意继续向后访问被链接到的其他节点的概率。

以书签记录估算得，d=0.85

所以，对于第一次迭代：

A节点被随机游走者访问的概率是

PR（A）= d * [ PR(B)* 1/2  + PR(C)* 1/1  ] = 0.85*[1* 1/2 + 1* 1/1 ] = 1.275

B节点被随机游走者访问的概率是

PR（B）= d * [ PB(A)* 1/3 + PB(D)* 1/2 ] = 0.85*[ 1.275* 1/3 + 1* 1/2 ] = 0.786

C节点被随机游走者访问的概率是

PR（C）= d * [ PR(A)* 1/3 + PR(D)* 1/2 ] = 0.85*[ 1.275* 1/3 + 1* 1/2 ] = 0.786

D节点被随机游走者访问的概率是

PR（D）= d * [ PR(A)* 1/3 +PR(B) *1/2 ] = 0.85*[ 1.275* 1/3 + 0.786* 1/2 ] = 0.695

对于第二次迭代：

A节点被随机游走者访问的概率是

PR（A）= d * [ PR(B)* 1/2  + PR(C)* 1/1  ] = 0.85*[0.786* 1/2 + 0.786* 1/1 ] = 1.002

B节点被随机游走者访问的概率是

PR（B）= d * [ PB(A)* 1/3 + PB(D)* 1/2 ] = 0.85*[ 1.002* 1/3 + 0.695* 1/2 ] = 0.579

C节点被随机游走者访问的概率是

PR（C）= d * [ PR(A)* 1/3 + PR(D)* 1/2 ] = 0.85*[ 1.002* 1/3 + 0.695* 1/2 ] = 0.618

D节点被随机游走者访问的概率是

PR（D）= d * [ PR(A)* 1/3 +PR(B) *1/2 ] = 0.85*[ 1.002* 1/3 + 0.579* 1/2 ] = 0.530

一直这样的迭代，直到达到迭代次数后停止迭代；或者两次迭代间，各个节点的访问概率值的和小于阈值，那么就可以停止迭代

从上面的两次迭代我们可以看出，每次迭代时，由于图结构不变，所以计算各节点的访问概率时，只有对应链接到该节点的对应节点PR值在变动，所以，为了加速计算，很自然的想到用矩阵来存储图的链接结构，我们称该矩阵为转移矩阵M，那么，对于本图结构，矩阵M为：

其中，M[i][j]表示链接到 i 节点的 j 节点其在图中可以链接到的所有节点的数目比（即，j 节点的出度值）

所以，第一次迭代即为：

 表示第 i 次迭代后的各个节点的访问概率；“   ” 表示数值的点乘；表示矩阵乘法

初始时，

    ，

那么经过一次迭代后，

我们会发现，这次迭代是各个节点的PR取值与之前的例子取值不同，之前的例子是，节点的PR取值经计算更改后，以后其他节点使用该节点时，便会采用该节点的新PR值，而在这种方式的计算下，节点的取值在一次所有节点（ABCD）均计算结束之前，各个节点均选择上一轮的旧值进行计算