浅析PageRank(公式篇2)
????? 上公式~~~PageRank最开始一个版本的公式：
??? ?
????? 最基本的概念这里不再赘述，对公示稍加解释：页面A的PR是由页面B、C、D一起贡献的，每个页面贡献给A的大小由各自链出数目决定，如果B有五个链出，PR(B)=10，那么就有2的值给A。q是阻尼因子，指代浏览者沿着当前链接继续阅读的可能性，每个页面都有一个最小值1-q，PR中q=0.85。
???? ?接下来，用实例说明：(为了使计算简单明了，实例中的页面无外部的链入和链出，实际PR算法的设计也是依据将互联网看做一个整体，只有内部成员间的连接，无外部链接)
????? 自己随意画了一个关系图，箭头代表A、B、C页面间的联系(为使矩阵运算简单可观，这里只列出三个页面)。
?????????????? 
????? 由图可以看出，它们之间的关联以及构造的矩阵如下(不懂怎么构造矩阵的去看公式篇1，不再解释~~)：
???????????? 
???????? 
???? ?(赤果果的word图，好难看啊~)然后我们沿着之前说过的思路，将矩阵进行转置和概率化，结果如下：
??????????????? 
???? ????? 
????? 对如图概率化后的矩阵求解特征值和相对应的特征向量，解得最大特征值所对应特征向量中的原素即为各页面的PR值。这里我们从数学思想与PR公式两个角度进行计算，以验证结果的有效性。
????? 1、数学实现
????? 通过公式Ax=kx(详细求解过程与思路1中都已经介绍，这里给出大体思路和结果)，其中k为特征值，x为特征向量。求解特征值时，根据(A-kE)x=0，E为与A同型的单位矩阵，即求|A-kE|=0，经计算可得 -k3+1/4k=0，因为数学中的前提是?k≠0，所以k=1/2，解得特征向量为p=(1,1,2)T，可以得所有的mp(?m≠0)均为特征值1/2的特征向量。
???? ?2、公式
????? 由公式PR(A)=(PR(B)/L(B)+PR(C)/L(C))*0.85+0.15，假设A、B、C的初始PR均为1，那么通过代入公式，进行第一次求值可得PR(A)=0.575，PR(B)=0.394375，PR(C)=0.7119844(注：在这里计算的时候取的精度为float，与以下代码中使用的相同，也就是精确到小数点后7位)。再将第一次得出的值代入公式进行第二次计算，可得PR(A)=0.31760937，PR(B)=0.284984，PR(C)=0.5561022，重复代入的步骤进行计算，这里不列出全值，但是通过观察结果可以看出，一直到第11次开始，A、B、C三者的PR值保持了一致，不再随计算的重复性变动，当然这里的精确度达到了小数点后的7位，如果对精确度的要求更低，运算的次数会大大减少，比如对精度的要求是小数点后2位，那么计算到第4次便达到了要求。最终的稳定结果是PR(A)=0.26086956，PR(B)=0.26086956，PR(C)=0.5217391。
?
????? 将公式计算的结果与数学方法所求的值相比可以看出，数学实现的结果中存在的关联关系PR(A)=PR(B)=1/2*PR(C)与通过公式计算的结果PR(A)=0.26086956，PR(B)=0.26086956，PR(C)=0.5217391有着高度的一致性,因此，这两种方法在思路上是统一的。
?
????? 由这个例子，我们可以再回过头来分析阻尼因子q的作用。Sample中出现了一个比较特殊的情况，C页面只有链入没有链出，也就是说迭代时A，B的值不断传入C，C却不为PR的传播做任何贡献，这必然会导致有限次计算后全网的PR趋于0。加入阻尼因子后，我们看到，计算的结果并未受这一情况的影响，网页间实际PR的计算依然与模型一致，这就是概念篇中提到过的消除值沉淀问题。
?
???? ?这里还有一个很重要的问题要说明：Brin与Page的设计中，证明无论如何取初值，计算结果都会收敛到一个固定的值，之前的计算中取得初值全为1，此时我们验证一下这个说法的正确性。令PR(A)=1，PR(B)=2，PR(C)=3，运算后在第12次、float精度下趋于稳定；令PR(A)=60，PR(B)=70，PR(C)=80，运算在第14次、float精度下趋于稳定；令PR(A)=100，PR(B)=500，PR(C)=1000，运算在第15次、float精度下趋于稳定…………从例子中可以看出，不论初值如何取，最终的计算结果都会趋于一个稳定值，当然这些稳定值也是相等的，区别则是当选取了一个合理的初始值，会使得计算的次数减少，这里只是一个三维矩阵的计算，差距可能不够明显，实际操作中面对几十亿的网页数量这种操作的时间差是不可忽视的。从这些计算值中，可以看出运算次数在随着初始值的增加而增加，个人猜测这或许也是Google将网页排名定为0~10的一个原因，如果将几十的初始值放入十亿单位的网页操作，计算量应该相当的惊人。
?
????? 本来想进行一下随着维度增加，运算时间变化的分析，但实现过程中发现这个运算时间的影响因素太多，比如电脑运算的即时性、录入矩阵的复杂度等，使得运算之变化幅度很大，维度之间差距也不够明显，尤其是矩阵内部链接复杂度对运算影响非常大，一个简单的四维矩阵可以比上文例举的三维矩阵算短一半时间，复杂的四维花费又变成了一倍，因此这里不列出数据进行对比，感兴趣的话可以自行研究~但是可以确定的是，这个时间量的增加并不是线性的，当维度增加n，行的遍历增加n，列的遍历也增加了n,额外增加的数据其实是n2个，三位矩阵的耗时为28毫秒(取大致的平均值),那么可以假设同等复杂度的维度是1亿的矩阵为28/9*1016毫秒，这还不考虑多耗费的用于创建临时变量以及数组的时间。同时我们可以估算出来，此时初始值有108个，400MB的数据是可以接受的，但矩阵里面的数据有108*108个元素，每个float型占4Byte，也就是需要4*108*108B，等同于40000TB……这需要多么庞大的存储空间啊……
?
???? ?讨论过了理论，我用java的方法模拟一下PR值的计算过程,具体的描述代码中都写出来了，使用的思路和上述Sample一样，只不过代码中是直接从选定的文件中读入初始PR值以及矩阵元素(文件中的书写顺序是：第一行为各个初始的PR值，接下来是矩阵，每行的元素之间通过,分隔，行与行之间无分隔符)，然后进行转置、概率化、公式重复求解（这份新代码修改了一个计算上的失误，也增加了随机生成一个矩阵的方法，节省了手工录入矩阵的时间。其中矩阵维度就是矩阵的大小，初始值为初始的PR值，复杂度指代连接中有百分之多少多少为1，当然，这里的复杂度只是取最简单情况，实际中计算复杂程度取决于更为详细的链接情况，比如全部都是50%的复杂度，全单向链接和存在双向链接的计算时间与收敛次数必然不会相同）
package cn.wx.PageRank;import java.awt.FlowLayout;import java.awt.event.ActionEvent;import java.awt.event.ActionListener;import java.io.BufferedReader;import java.io.File;import java.io.FileNotFoundException;import java.io.FileReader;import java.io.IOException;import javax.swing.JButton;import javax.swing.JFileChooser;import javax.swing.JFrame;import javax.swing.JLabel;import javax.swing.JScrollPane;import javax.swing.JTextArea;import javax.swing.JTextField;/** * 求取PageRank值的代码 * @author 艾儿 */public class newPageRank {static JTextField jtf;//显示文件路径的框static JTextArea jta;//显示计算结果的框static JFrame jf;//显示的窗体static JFrame jf1;//显示输入矩阵的窗体static float[] data;//存数输入数据的数组static int time=20;//指定的运行次数public static void main(String [] args){newPageRank mine = new newPageRank();mine.showUI();}/** * 展示计算结果的界面 */public void showUI(){//初始化界面以及按钮、输入框等jf = new JFrame();jf.setTitle("PR值计算~~");jf.setSize(500, 500);jf.setDefaultCloseOperation(3);jf.setResizable(false);jf.setLayout(null);jf.setLocationRelativeTo(null);JButton btn = new JButton("打开");btn.setActionCommand("Open");btn.setBounds(20, 20, 80, 30);JButton btn1 = new JButton("随机");btn1.setActionCommand("Input");btn1.setBounds(110, 20, 80, 30);jtf = new JTextField();jtf.setBounds(200, 20, 260, 30);jtf.setEditable(true);jtf.setActionCommand("Over");jta = new JTextArea();jta.setEditable(false);jta.setLineWrap(true);jta.setAutoscrolls(true);JScrollPane jsp = new JScrollPane(jta);//创建滚动条jsp.setBounds(20, 70, 460, 380);//添加监听器ActionListener al = new ActionListener(){public void actionPerformed(ActionEvent e) {if(e.getActionCommand().equals("Open")){//弹出选择框jta.setText("");//每次重新选择之前清空输入框JFileChooser fc = new JFileChooser();int value = fc.showOpenDialog(null);fc.setFileSelectionMode(JFileChooser.FILES_ONLY);if(value == JFileChooser.CANCEL_OPTION){return;}File file = fc.getSelectedFile();jtf.setText(file.getAbsolutePath());readFile(file);}if(e.getActionCommand().equals("Input")){init();//初始化窗体，获取值}if(e.getActionCommand().equals("Over")){jta.setText("");//输入路径结束，执行以下操作File file = new File(jtf.getText());readFile(file);}}};jf.add(btn);jf.add(btn1);jf.add(jtf);jf.add(jsp);btn.addActionListener(al);btn1.addActionListener(al);jtf.addActionListener(al);jf.setVisible(true);}/** * 读取相应路径文件的方法 * 定义文件中第一行是节点对应的初始化PR值，接下来是N*N的矩阵 * 同行数据之间均通过，分隔，不同行无需分隔符 * @param file：文件 */public static void readFile(File file){try {//创建读文件的流FileReader fr = new FileReader(file);BufferedReader br = new BufferedReader(fr);String PR = br.readLine();String[] sPR = PR.split(",");//将第一行PR值存入对应数组//将读取的PR值从String转为floatfloat[] initPR = new float[sPR.length];for(int i=0;i<sPR.length;i++){initPR[i] = Float.parseFloat(sPR[i]);}jta.append("各页面的初始PR值………………………………………………………………"+"\n");for(int i=0;i<initPR.length;i++){jta.append(initPR[i]+"\t");//打印出PR值}jta.append("\n");//读取并创建N*N矩阵，在这里使用float，精度为小数点后7位float[][] array = new float[initPR.length][initPR.length];int count = 0;//用计数器控制行的变化//当行数小于指定数N时进行读取while(count<initPR.length){String value = br.readLine();//读取一行的值String[] rowV = value.split(",");//对第count行第i列赋值for(int i=0;i<initPR.length;i++){array[count][i] = Float.parseFloat(rowV[i]);}count++;}jta.append("原始矩阵为………………………………………………………"+"\n");print(array);//打印出矩阵//读取完成后，调用计算的函数对矩阵进行计算long start = System.currentTimeMillis();calculate(initPR,array);long end = System.currentTimeMillis();jta.append("total time is:"+(end-start));} catch (FileNotFoundException e) {javax.swing.JOptionPane.showMessageDialog(jf,"文件未找到，请重试！");} catch (IOException e) {javax.swing.JOptionPane.showMessageDialog(jf,"文件读取有误，请重试！");}}/** * 打印矩阵的方法 * @param s */static void print(float[][] f){for(int i=0;i<f.length;i++){for(int j=0;j<f.length;j++){jta.append(f[i][j]+"\t");}jta.append("\n");}}/** * 计算矩阵特征值以及特征向量的方法 * @param initPR：存储初始的PR值的float数组 * @param array：存储初始矩阵的float二维数组 */static void calculate(float[] initPR,float[][] array){array = changeRC(array);//倒置矩阵jta.append("转置后的矩阵…………………………………………………………");jta.append("\n");print(array);array = randomization(array);//概率化矩阵jta.append("\n");jta.append("概率化后的矩阵………………………………………………………………");jta.append("\n");print(array);for(int i=1;i<=time;i++){initPR = formular(initPR,array);jta.append("\n");jta.append("经过"+i+"次计算，PR值为………………………………………………");jta.append("\n");for(int j=0;j<initPR.length;j++){jta.append("PR["+j+"]的值为："+initPR[j]);jta.append("\n");}}jta.repaint();}/** * 转置矩阵的方法 * @param array：需要转置的矩阵 * @return：将转置后的矩阵返回 */static float[][] changeRC(float[][] array){float temp = 0;//临时变量，用于交换for(int i=0;i<array.length;i++){for(int j=0;j<array.length;j++){//对矩阵的每一行、列遍历，如果下标i<j就倒换if(i<j){temp = array[i][j];array[i][j] = array[j][i];array[j][i] = temp;}}}return array;}/** * 概率化矩阵的方法 * @param array：需要概率化的矩阵 * @return：返回已经概率化的矩阵 */static float[][] randomization(float[][] array){int count = 0;//控制列变化的计数器int size = 0;//计量列中连接为1的元素数量的计数器while(count<array.length){size = 0;//每次计数之前要清零for(int i=0;i<array.length;i++){if(array[i][count]==1){size++;//先统计出数量为多少}}jta.append("the size of "+count+" is:"+size+" ");for(int i=0;i<array.length;i++){if(array[i][count]==1){array[i][count]=(float)1/size;}}count++;}return array;}/** * 通过公式计算PR值 * @param initPR：初始PR值 * @param array：经处理的矩阵 * @return：返回计算后的PR值 */static float[] formular(float[] initPR,float[][] array){for(int i=0;i<initPR.length;i++){initPR[i] = 0;//重算一个PR之前，将其清零int count =0;//计量每一行0元素个数for(int j=0;j<initPR.length;j++){if(i!=j && array[i][j]!=0){initPR[i] = (float) (initPR[i]+((initPR[j]*array[i][j])*0.85+0.15));}elsecount++;}if(count==initPR.length){initPR[i] = (float) 0.15;}}return initPR;} static void input(float[] data){float size = data[0];float complex = data[1];float[] initPR = new float[data.length-2];for(int i=0;i<initPR.length;i++){initPR[i] = data[i+2];}float[][] array = new float[(int) size][(int) size];//创建输入大小的矩阵//初始化矩阵元素为0for(int i=0;i<array.length;i++){for(int j=0;j<array.length;j++){array[i][j]=0;}}int num = (int) (complex/100*array.length*array.length);//需要被赋为1的元素个数//为矩阵按照复杂程度赋值while(num>0){int row = (int) (Math.random()*(array.length));int column = (int) (Math.random()*(array.length));//随机生成行列数if(row!=column && array[row][column]!=1){array[row][column]=1;num--;}}//打印随机生成的PR和矩阵jta.append("各页面的初始PR值………………………………………………………………"+"\n");for(int i=0;i<initPR.length;i++){jta.append(initPR[i]+"\t");//打印出PR值}jta.append("\n");jta.append("生成的矩阵…………………………………………………………………………"+"\n");print(array);//将计算好的初始PR数组和矩阵传入计算long start = System.currentTimeMillis();calculate(initPR,array);long end = System.currentTimeMillis();jta.append("total time is:"+(end-start));}/** * 初始化一个输入值的窗体 */static void init(){jf1 = new JFrame("生成随机矩阵");jf1.setSize(300, 160);jf1.setResizable(false);jf1.setDefaultCloseOperation(2);jf1.setLocationRelativeTo(null);jf1.setLayout(new FlowLayout());JLabel lb = new JLabel("矩阵维度：");final JTextField jtf = new JTextField(15);JLabel lb1 = new JLabel("初始PR值：");final JTextField jtf1 = new JTextField(15);JLabel lb2 = new JLabel(" 复杂度： ");final JTextField jtf2 = new JTextField(15);jtf2.setActionCommand("sure");JLabel lb3 = new JLabel("% ");JButton btn = new JButton("确认");btn.setActionCommand("sure");JButton btn1 = new JButton("取消");btn1.setActionCommand("cancle");ActionListener al = new ActionListener(){public void actionPerformed(ActionEvent e) {if(e.getActionCommand().equals("sure")){//点击确认后，存储输入值float size = Integer.parseInt(jtf.getText());//取值String[] s = jtf1.getText().split(",");float complex = Integer.parseInt(jtf2.getText());//初始化数组，将输入框中的值存入数组data = new float[s.length+2];//先存入矩阵维度，再放入复杂度，最后存入各个初始值data[0] = size;data[1] = complex;for(int i=0;i<s.length;i++){data[2+i] = Float.parseFloat(s[i]);}jf1.dispose();input(data);}if(e.getActionCommand().equals("cancle")){jf1.dispose();}}};jf1.add(lb);jf1.add(jtf);jf1.add(lb1);jf1.add(jtf1);jf1.add(lb2);jf1.add(jtf2);jf1.add(lb3);jf1.add(btn);jf1.add(btn1);jtf2.addActionListener(al);btn.addActionListener(al);btn1.addActionListener(al);jf1.setVisible(true);}}?
?
?
???? 关于公式再提一下，Google后来调整时使用了1-q/N,公式的其他部分未作任何变动，这里的N是互联网中全部的网页数量，网上的参考资料说这样做使得网页级别变为了被随机访问的期望值(不理解)……做一下比较，对于0.15/N这个公式，从逻辑上看也可以认为是加速了值收敛，通过代码计算验证发现，对于同样维度为10的矩阵，初始值全为1，复杂度为50%，原公式经过20次运算后，有9个PR值收敛到了小数点后2位，一个收敛到了小数点后1位，而改进后的公式，有8个PR值收敛到了小数点后3位，2个收敛到小数点后2位。可以看出，仅仅是10维矩阵就几乎存在一位的精度差，如果应用到上亿的网页运算中，计算时间一定会大大的缩减~但是这种情况下的计算比较复杂，而且两种计算的原理近似，这里不再额外讨论。
?
?
?
?
?
?