Google PageRank算法计算网页的价值PR值原创

分类: 首页- >Java技术 | 阅读: 546 | 评论: 1 | 2016-12-06 09:51:35 
摘要:PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种由[1] 根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。

导读:PageRank通过网络浩瀚的超链接关系来确定一个页面的等级。Google把从A页面到B页面的链接解释为A页面给B页面投票,Google根据投票来源(甚至来源的来源,即链接到A页面的页面)和投票目标的等级来决定新的等级。简单的说,一个高等级的页面可以使其他低等级页面的等级提升。

现假设有A,B,C,D,E五个网页,其中
1)  A网页有链接指向B,C,D,E
2)  B网页有链接指向A,D
3)  C网页有链接指向A,D
4)  D网页有链接指向C
5)  E网页有链接指向A,C
A 请写出这个网页链接结构的Google矩阵,目测你认为哪个页面的重要性(PR值)最高?
B 手动或编程计算这5个页面的PR值,可以使用任何你熟悉的编程语言;
C 指出当页面较多的时候,计算PR的主要困难在什么地方,Map-Reduce是怎么解决这个难题的?

一、Google矩阵
将上述问题进行数学建模,如下:

二、网页价值计算(计算PageRank值)
PageRank算法的数学原理如下:

得到初始矩阵后,我们就可以得到PR值,当只有a概率的用户会点击网页链接,剩下(1-a)概率的用户会跳到无关的页面上去,而访问的页面恰好是这5个页面中A的概率只有(1-a)/5(a是阻尼系数,Google取a等于0.85),所以真正的Google矩阵 :

于是得到q(n)=G*q(n-1),特征向量q的初始值为值为1的5*1矩阵,直到q(n)=q(n-1),q(n)就是PR的值。

将上述的思想抽象成一个数学函数:

当f(n+1)约等于f(n),此时的PageRank值即为f(n)。

三、编程实现

public class PageRank {
    /**
     * 矩阵g乘以矩阵p

     * @param g
     * @param p
     * @return 矩阵g乘以矩阵p的结果矩阵
     */
    private static double[] multiMatrix(double[][] g, double[] p){
        double[] multiResult = new double[p.length];
        for(int i=0; i<g.length; i++){
            double rowResult = 0.0f;
            for(int j=0; j<g.length; j++){
                rowResult+=g[i][j]*p[j];
            }
            multiResult[i] = rowResult;
        }
        return multiResult;
    }
    /**
     * 根据初始矩阵计算真正的Google矩阵
     * @param 初始矩阵
     * @param weight
     * @param oneMatrix
     * @return 真正的Google矩阵
     */
    private static void getGoogleMatrix(double[][] transitionMatrix, double weight){

        //transitionMatrix*weight
        for(int i=0; i<transitionMatrix.length; i++){
            for(int j=0; j<transitionMatrix.length; j++){
                transitionMatrix[i][j] *= weight;
                transitionMatrix[i][j] += (1-weight)/transitionMatrix.length;
            }
        }
    }
    /**
     * 如果pageRankN=pageRankN_1,返回true;否则,返回false

     * @param pageRankN
     * @param pageRankN_1
     * @return
     */
    private static boolean compareMatrix(double[] pageRankN, double[] pageRankN_1){
        for(int i=0; i<pageRankN.length; i++){
            if(pageRankN[i]-pageRankN_1[i]>0.0000001){
                return false;
            }
        }
        return true;
    }
    /**
     *
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        double[][] transitionMatrix={
                {0,    1/2f,   1/2f,   0,   1/2f},
                {1/4f,    0,      0,   0,      0},
                {1/4f,    0,      0,  1f,      0},
                {1/4f, 1/2f,   1/2f,   0,   1/2f},
                {1/4f,    0,      0,   0,      0}
        };//初始矩阵
        double[] p={1,1,1,1,1};
        double weight = 0.85f; //a的值


        //真正的Google矩阵
        getGoogleMatrix(transitionMatrix, weight);

        //输出看一下
//        for(int i=0; i<transitionMatrix.length; i++){
//            for(int j=0; j<transitionMatrix.length; j++){
//              System.out.print(transitionMatrix[i][j]);
//              System.out.print("  ");
//            }
//            System.out.println();
//        }

        //q(n)=G*q(n-1),如果q(n)=q(n-1),q(n)是PageRank
        double[] pageRank = multiMatrix(transitionMatrix, p);
        while(!compareMatrix(pageRank, p)){
            p = pageRank;
            pageRank = multiMatrix(transitionMatrix, p);
        }

        for(int i=0; i<pageRank.length; i++){
            System.out.println(pageRank[i]);
        }
    }


}

计算结果:
1.1724915755493341
0.3991544277616714
1.6075535417744635
1.4216460271528633
0.3991544277616714

四、PageRank算法优缺点
优点:
        是一个与查询无关的静态算法,所有网页的PageRank值通过离线计算获得;有效减少在线查询时的计算量,极大降低了查询响应时间。
缺点:
       1)人们的查询具有主题特征,PageRank忽略了主题相关性,导致结果的相关性和主题性降低
       2)旧的页面等级会比新页面高。因为即使是非常好的新页面也不会有很多上游链接,除非它是某个站点的子站点。

PageRank值每年只发布几次,有时就得使用过时信息,因此,PageRank并不是一个非常精确的度量。GOOGLE自己也似乎在使用更精确的值来进行排名。

 声明:www.mbaike.net 博客文章版权属于作者,受法律保护。未经作者同意不得转载。
标签 PageRank PR
相关搜索

共有 1 条网友评论

1 楼:钓鱼人之家 发表于2016-12-06 13:33:48
钓鱼人之家(http: www.chinadyer.com)
管理回复:可以!

发布评论:

昵称: 邮箱: 验证码:
文明上网,理性发言!
© 移动互联百科(www.mbaike.net) | WAP站点 | 站长QQ:459104018 | 备案号:蜀ICP备14008230号-2