PageRank算法

/*
 * PageRank算法的计算方式
 *
 *  1.计算Google矩阵
 *       G  =  a*s+((1-a)/n)*p   p为单位矩阵
 *  2.q =G p   如果能找到这样的一个q和p,但是p与q是非常接近的,就说明找到了Google矩阵的特征向量,该特征向量就是所求的每一个网页的pagerank值
 *
 * */
public class PageRankB {
    public static void main(String[] args) {
        /*
         *  定义一个最大误差
         * */
        double MAX = 0.000000000000001;
        /* 定义一个权值 */
        double RIGHT = 0.5;
        int[][] links = { { 0, 1, 1 }, { 0, 0, 1 }, { 1, 0, 0 } };
        int len = links.length;
        // 各点的总链出数量
        int[] linkOut = new int[len];
        for (int k = 0; k < len; k++) {
            for (int l = 0; l < len; l++) {
                linkOut[k] += links[k][l];
            }
        }
        /*
         *
         * 用来存储PR值的结果
         *
         * */
        double[] pr = new double[len];
        double[] init = new double[len];
        for (int i = 0; i < len; i++) {
            init[i] = 0.0;
        }
        /*
         * 先做一次PageRank
         *
         * */
        pr = doPageRank(init, linkOut, links, RIGHT);
        // 把得到的值反复运算,只到得到要得到的精度为止
        while (!checkPrecision(pr, init, MAX)) {
            System.arraycopy(pr, 0, init, 0, len);
            pr = doPageRank(pr, linkOut, links, RIGHT);
       
        }
        for (int i = 0; i < len; i++) {
            System.out.println("PageRank(" + (char) (i + 65) + ") 为: " + pr[i]);
        }
    }
   
   
    /*
     * 检查两个特征向量的相似度,必须小于给定最大值
     *
     * */
    public static boolean checkPrecision(double[] checked, double[] ref,
            double precision) {
        /*
         *
         * 如果两个数组的长度不一样,则没比较,所以返回false
         *
         * */
        if (checked.length != ref.length) {
            System.out.println("lenth is not the same!");
            return false;
        }
        /*
         *
         *先把结果设为true
         * 
         * */
        boolean result = true;
        int len = ref.length;
        for (int i = 0; i < len; i++) {
            if (Math.abs(checked[i] - ref[i]) > precision) {
                result = false;
                break;
            }
        }
        return result;
    }
   
   
    public static double[] doPageRank(double[] init, int[] linkOut, int[][] links, double right) {
        if(init.length != linkOut.length) {
            return null;
        }
        int len = init.length;
        double[] pr = new double[len];
        double temp = 0;
        int i = 0, j = 0;
        for(i = 0; i<len; i++) {
            j  = 0;
            temp = 0;
            for(j = 0; j <len; j++) {
                if((i != j) && (linkOut[j] != 0) && (links[j][i] != 0)) {
                    temp += init[j]/linkOut[j];
                }            
            }
            pr[i] = right + (1 - right)* temp;
        }
        return pr;
    }
}

相关推荐