public class PageRankExample2 extends PageRanker { public PageRankExample2() { super( new String[] {"ID=1", "ID=2", "ID=3", "ID=4", "ID=5", "ID=6", "ID=7"} ); addLinks(); setDampingFactor(1.0); } private void addLinks() { addLink("ID=1", "ID=2"); addLink("ID=1", "ID=3"); addLink("ID=1", "ID=5"); addLink("ID=1", "ID=6"); addLink("ID=2", "ID=1"); addLink("ID=2", "ID=3"); addLink("ID=2", "ID=4"); addLink("ID=3", "ID=1"); addLink("ID=3", "ID=4"); addLink("ID=3", "ID=5"); addLink("ID=4", "ID=1"); addLink("ID=4", "ID=5"); addLink("ID=5", "ID=1"); addLink("ID=5", "ID=4"); addLink("ID=5", "ID=6"); addLink("ID=5", "ID=7"); addLink("ID=6", "ID=5"); addLink("ID=7", "ID=1"); } public static void main(String[] args) throws Exception { PageRanker pr = new PageRankExample2(); double[] ranks = pr.solve(); print(pr.getPages(), ranks); } private static void print(String[] pages, double[] ranks) { int i = 0; for (String page : pages) { print(page, ranks[i++]); } } private static void print(String page, double rank) { System.out.printf("%s\t%.4f%n", page, rank); } } |
$ java -classpath .:Jama-1.0.2.jar PageRankExample2 1.000 -1.000 -0.500 -0.000 -0.250 -0.500 -0.000 -0.200 1.000 -0.500 -0.333 -0.000 -0.000 -0.000 -0.200 -0.000 1.000 -0.333 -0.250 -0.000 -0.000 -0.200 -0.000 -0.000 1.000 -0.250 -0.000 -0.000 -0.200 -0.000 -0.000 -0.333 1.000 -0.500 -1.000 -0.000 -0.000 -0.000 -0.000 -0.250 1.000 -0.000 -0.200 -0.000 -0.000 -0.000 -0.000 -0.000 1.000 Exception in thread "main" java.lang.RuntimeException: Matrix is singular. at Jama.LUDecomposition.solve(LUDecomposition.java:282) at Jama.Matrix.solve(Matrix.java:815) at PageRanker.solve(PageRanker.java:59) at PageRankExample2.main(PageRankExample2.java:33) $ |
Damping Factor を 1.0 にして実行してみましたが、Exception が発生してしまいました。これは、B の要素がすべて 0 になり、連立方程式が一次独立でなくなったためです。例えば、ひとつ解があれば、すべ
public class PageRanker { ... public double[] solve() { int len = pages.length; Matrix A = new Matrix(len,len); for (int j = 0; j < len; j++) { int n = 0; for (int i = 0; i < len; i++) { n += links[i][j]; } double v = -1. * dampingFactor / (double)(n==0?(len-1):n); for (int i = 0; i < len; i++) { A.set(i, j, (i==j)?1.:((double)(n==0?1:links[i][j])*v)); } } if (dampingFactor == 1.) { for (int j = 0; j < len; j++) { A.set(0, j, 1.); } } A.print(5,3); Matrix B = new Matrix(len,1); if (dampingFactor == 1.) { B.set(0, 0, 1.); for (int i = 1; i < len; i++) { B.set(i, 0, 0.); } } else { double v = (1. - dampingFactor) / (double)len; for (int i = 0; i < len; i++) { B.set(i, 0, v); } } Matrix X = A.solve(B); double[] pageRanks = new double[len]; for (int i = 0; i < len; i++) { pageRanks[i] = X.get(i, 0); } return pageRanks; } } |
|
これで、図にある通りの解になりました。
Tags: programming