上网者跑到D网页后，再也不能从D中出来，将最终导致概率分布值全部转移到D上来，这使得其他网页的概率分布值为0，从而整个网页排名就失去了意义。如果按照上面图对应的转移矩阵为：
A B C D
A 0 0.5 0 0
B 0.33 0 0 0
C 0.33 0.5 0 0
D 0,33 0 1 1
不断的迭代下去，的结果一定会是[0,0,0,1]的
解决终止点问题和陷阱问题
其实会出现这两个问题，是因为最开始构建模型的时候我们忽略了一个东西：上网者可以随时跳出他浏览的网页（浏览器上输入网址就行了），而不需要担心，要是浏览的网页没有链接那不就是不能出去了吗？（结果只需要输入网址就可以跳出去），那浏览的网页连接了自己浏览这不就一直在浏览这个了吗？（结果是浏览者发现这是陷阱都在重复浏览一个网页的时候，他可以轻松跳过去，只需要输入网址即可），当然正常情况他也是可以输入网址跳转任何他想去的网页，这个时候我们需要引入一个概念：阻尼系数（简单来说就是点击网页的概率-实际上就是用户感到无聊，停止点击，随机跳到新URL的概率），这里我们取α = 0.8，当然也有很多的觉得0.85是好的，这个概念已经给出，数值看我们自己~（觉得能让你的结果符合预期就ok啦..）。 从而我们得到了更加完善的公式：
由于这些是数学上的计算，有了公式是比较容易推出结果来的，所以就不在举例啦~~
如何通过代码具体的实现?
可以把每个网页所构成的复杂的关系模型化成数据结构的逻辑结构图(有向图)，每个网页就是一个结点，当一个网页(网页A)链接着另一个网页(网页B)的时候可以抽象的看出A->B,即通过出度和入度来描述链接和被链接数，当你通过创建有向图的时候其实就相当于模拟了网页之间的关系(当然浩瀚的互联网中网页数不胜数,我这里只是通过一个小的环境模拟这个算法的实现),通过PageRank算法加之迭代，使其每个网页的pr(衡量网页质量的参数)值都趋于稳定的时候,由pr值大小排序出来的网页的先后顺序可以相对准确的衡量网页质量。
我先是通过c语言模型化PageRank的算法 算出每个结点(网页)的pr值。
需要构建有向图来模型化网页（c语言的结点是手动输入的，因为为了测试方便嘛~）
#include <stdio.h> #include <stdlib.h> #include <math.h> #define OK 1 #define ERROR -1 #define FALSE 0 #define TRUE 1 #define MAXVER 20 //定义最大顶点数 #define MAXQSIZE 100 //#define OVERFLOW -2 typedef char verType; //顶点类型 typedef int Status; typedef int Boolean; typedef struct { verType verx[MAXVER]; int arcs[MAXVER][MAXVER]; //邻接矩阵 int vernum, arcnum; //定义最大顶点数 和 弧 }MGraph; Boolean visited[MAXVER]; //顶点开始都没有被访问过 int locate(MGraph G, verType ch); //查找顶点在数组中的下标 Status CreateDG(MGraph *G,int v); //创建有向图 void Create_Transfer_matrix(MGraph G, double ***F); //创建转移矩阵 double** Mat_mul(double **M1, int num); //矩阵相乘 int GetNum(MGraph G, int h, int l); //得到每一行非0项的个数 double *Iteration(double *M1, double **M2, double *M, int num); //迭代法 int main(void) { double **F = NULL; MGraph G; CreateDG(&G, 0); Create_Transfer_matrix(G, &F); Mat_mul(F, G.vernum); return 0; } double *Iteration(double *M1, double **M2, double *M, int num) {//迭代法 double *M3, temp = 0; int i, j; M3 = malloc(num * sizeof(double)); printf("\n"); for(i = 0; i < num; i++) { printf("@ = %0.10lf\n", M[i]); } for (i = 0; i < num; i++) { for (j = 0; j < num; j++) { temp = M1[j] * M2[i][j] + temp; } M3[i] = temp + M[i]; temp = 0; } putchar(10); for (i = 0; i < num; i++) { printf("%.10lf\n", M3[i]); } putchar(10); return M3; } double** Mat_mul(double **M1, int num) { int i,j; double *M2, *M3, temp = 0, *M; M3 = malloc(num *sizeof(double)); M2 = malloc(num * sizeof(double)); for (i = 0; i < num; i++) //初始化概率分布矩阵 { M2[i] = (1.0 / num * 1.0); } for (i = 0; i < num; i++) { for (j = 0; j < num; j++) { temp = M1[i][j] * M2[j] + temp; } M3[i] = temp + M2[i] * 0.2; temp = 0; } for (i = 0; i < num; i++) { printf("%.10lf\n", M3[i]); } for (j = 0; j < num; j++) { M2[j] = M2[j] * 0.2; } M = Iteration(M3, M1, M2, num); //调用函数实现转移矩阵和概率向量的相乘 while (fabs(M[0] - M3[0]) > 0.0000000001) //设置迭代结束条件 { M3 = M; M = Iteration(M3, M1, M2, num); } for (i = 0; i < num; i++) { M[i] = M[i] * 0.8 + 0.2 / num; } for (i = 0; i < num; i++) printf(" - %.10lf\n", M3[i] - 0.0000000001); return M1; } void Create_Transfer_matrix(MGraph G, double ***F) {//创建转移矩阵 int i, j; (*F) = malloc(G.vernum * sizeof(double *)); for (i = 0; i < G.vernum; i++) { (*F)[i] = malloc(G.vernum * sizeof(double)); } for (i = 0; i < G.vernum; i++) { for (j = 0; j < G.vernum; j++) { if (GetNum(G, G.vernum, i) == 0) (*F)[j][i] = 0; else (*F)[j][i] = 0.8 * (G.arcs[j][i] / (GetNum(G, G.vernum, i) * 1.0)); } } putchar(10); printf("\n转移矩阵为:\n"); for (i = 0; i < G.vernum; i++) { for (j = 0; j < G.vernum; j++) { printf("%.10lf ", (*F)[i][j]); } printf("\n"); } printf("\n"); } int locate(MGraph G, verType ch) { int i; for (i = 0; i < G.vernum && ch != G.verx[i]; i++); return i; } Status CreateDG(MGraph *G,int v) { int i, j, k; verType ch1, ch2; printf("请输入有向图的顶点数和弧数,格式如(0 0): "); scanf("%d %d", &G->vernum, &G->arcnum); fflush(stdin); //除缓存 printf("请输入顶点符号:\n"); for (i = 0; i < G->vernum; i++) { scanf("%c", &G->verx[i]); fflush(stdin); } for (i = 0; i < G->vernum; i++) { for (j = 0; j < G->vernum; j++) { G->arcs[i][j] = 0; //赋初值 } } printf("请输入有连接的点: 格式(A B)\n"); for (i = 0; i < G->arcnum; i++) { printf("请输入第%d对值\n", i + 1); scanf("%c %c", &ch1, &ch2); //输入顶点符号 fflush(stdin); k = locate(*G, ch1); //获得顶点下标 j = locate(*G, ch2); G->arcs[j][k] = 1; //为邻接矩阵赋值 } return OK; } int GetNum(MGraph G, int h, int l) //得到每一列非0的个数 { int i, Num = 0; for (i = 0; i < h; i++) { if (G.arcs[i][l] > 0) { Num++; } } return Num; }