简单模拟PageRan算法——让链接投票（网页排名）

1、维基百科：http://zh.wikipedia.org/wiki/PageRank

2、http://blog.csdn.net/aladdina/article/details/4141120

3、源码

package pagerank;import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.File;import java.io.FileReader;import java.io.FileWriter;import java.util.HashMap;import java.util.Hashtable;import java.util.Map;/** * 简单模拟PageRank算法 * 在文件中的格式说明： * A B C D A * B C D A E * C B A D * D A B C D * E B A C D * 如上的格式表明：总共有5个链接（第一列的元素），每一行表示第一个链接链接到后面的其他链接, * 第一个链接是father，后面的是son，以空格" "为分隔符 * 比如第一行：链接A有链接到B C D A,但是链接到本身A是不计算如A的PR值的 * @author kute * @date 2013年10月14日 */public class PageRank {public static void main(String[] args) throws Exception {//存放每行中所有的链接String[] linesarr;//存放每个father链接的索引，就是第几个链接:key-链接  value-索引Map<String, Integer> docIDandNum=new HashMap<String, Integer>();// 链接总数int total = 0;int father, son;// 某个链接的出度int outdegree = 0;//读取链接文件File linkfile = new File("C:/link.txt");BufferedReader linkinput = new BufferedReader(new FileReader(linkfile));String line = linkinput.readLine();while (line != null) {++total;linesarr = line.split(" ");if (linesarr.length > 0) {outdegree = linesarr.length - 1;//如果链接到本身，则出度减少for (int j = 1; j <= linesarr.length - 1; ++j) {if (linesarr[j].equals(linesarr[0]))outdegree--;}if (linesarr[0] != null) {//这里存放每个链接的索引docIDandNum.put(linesarr[0], total);//System.out.println("链接" + linesarr[0] + "的出度为" + outdegree);}}linesarr = null;line = linkinput.readLine();}linkinput.close();//System.out.println("链接总数为：" + total);if (total > 0) {// pageRank[]存放PR值float[] pageRank = new float[total + 1];// 链入页面的计算总和float[] prTmp = new float[total + 1];// 设置pageRank[]初始值为1.0ffor (int i = 1; i <= total; ++i) {pageRank[i] = 1.0f;prTmp[i] = 0.0f;}// 当前页面的PR值float fatherRank = 1f;// 阻尼系数d或称为alphafloat alpha = 0.85f;// 进行100次迭代，迭代次数越多越收敛for (int iterator = 0; iterator < 100; iterator++) {long startTime = System.currentTimeMillis();linkinput = new BufferedReader(new FileReader(linkfile));line = linkinput.readLine();while (line != null) {linesarr = line.split(" ");if (linesarr.length > 0) {outdegree = linesarr.length - 1;for (int j = 1; j <= linesarr.length - 1; ++j) {// 指向自身的链接无效，不计算在内if (linesarr[j].equals(linesarr[0]))outdegree--;}}if (outdegree > 0) {father = (int) docIDandNum.get(linesarr[0]);// 对应公式中的pr(Ti)/c(Ti),Ti为指向father的页面fatherRank = pageRank[father] / outdegree;for (int k = 1; k <= linesarr.length - 1; ++k) {if (linesarr[k].equals(linesarr[0])) {continue;}son = docIDandNum.get(linesarr[k]);if (total >= son && son >= 0) {prTmp[son] += fatherRank;}}}linesarr = null;line = linkinput.readLine();}// 准备下次迭代的初始值for (int i = 1; i <= total; ++i) {/** * PR公式1，这里有两个，只因为：在Sergey Brin和Lawrence Page的1998年原文中给 * 每一个页面设定的最小值是1-d而不是(1-d)/N，具体参考英文版的维基百科词条 */// prTmp[i] = 1.00f-alpha + alpha * prTmp[i];// PR公式2prTmp[i] = (1.00f-alpha) / total + alpha * prTmp[i];// 每次迭代后的真正pr值pageRank[i] = prTmp[i];prTmp[i] = 0.0f;}linkinput.close();long endTime = System.currentTimeMillis();System.out.println("第" + iterator + "次迭代耗时"+ (endTime - startTime) + "ms"); /**  * 打印出每次迭代值，此操作耗费时间和内存  */// for (int i = 1; i <= total; ++i)// System.out.print(pageRank[i] + " \t ");// System.out.println(" ");}// 将最终PR值输出至文件BufferedWriter newlink = new BufferedWriter(new FileWriter(new File("C:/text.txt")));for (int i = 1; i <= total; ++i) {//控制台打印PR值//System.out.println(docIDandNum.toString());newlink.write(String.valueOf(pageRank[i]));newlink.newLine();}newlink.flush();newlink.close();pageRank = null;prTmp = null;}}}