PageRank Algorithmus in Java

Der PageRank Algorithmus, auf dem auch der Google Algorithmus basiert, kann relativ einfach programmiert werden. Dazu muss als erstes ein Crawler(z.B. crawler4j) Seiten (URLs) nach Links durchsuchen und danach kann über die Verlinkungen der Seiten untereinander der PageRank ausgerechnet werden.

Beim PageRank erhalten Seiten mit vielen starken Backlinks einen höheren Wert, als Seiten ohne Backlinks oder die nur von Seiten mit schlechten PageRank verlinkt sind.

Weitere Informationen: Wikipedia

import java.util.List;

public class Pagerank {
    public List<Knoten> knotenList;
    private static final double terminationDelta = 0.001;
    private double teleportationPropability = 0.1;

    public Pagerank(List<Knoten> knotenList) {
        this.knotenList = knotenList;
    }
    public void calculatePagranks() {
        System.out.println("Start PageRank Calculation");
        this.setInitialPagerank();
        int iterationCounter = 1;
        while(!this.hasTerminatingAccuracy())
        {
            this.printPageRankSum();
            this.iteratePagerank();
            System.out.println("PageRank iteration " + iterationCounter);
            iterationCounter++;
        }
        System.out.println("PageRank successfull calculated");
        this.printPageRankResults();
    }

    private void printPageRankResults() {
          for ( Knoten knoten : this.knotenList )
          {
              System.out.println("#Site:" + knoten.pageUrl + " #PageRank: " + knoten.pageRankNew);
          }    

    }
    private boolean hasTerminatingAccuracy() {
        double absSumChangesWithLastIteration = 0;
          for ( Knoten knoten : this.knotenList )
          {
              absSumChangesWithLastIteration += Math.abs(knoten.pageRankNew - knoten.pageRankOld);
          }
        if(absSumChangesWithLastIteration < this.terminationDelta)
        {
            return true;
        }
        return false;
    }
    private void setInitialPagerank() {
      double initialPagerank = 1.0 / this.knotenList.size();
      for ( Knoten knoten : this.knotenList )
      {
          knoten.pageRankNew = initialPagerank;
      }
    }

    private void iteratePagerank() {
          for ( Knoten knoten : this.knotenList )
          {
              knoten.pageRankOld = knoten.pageRankNew;
              knoten.pageRankNew = 0.0;
          }
          for ( Knoten knoten : this.knotenList )
          {
              double x = this.getTeleportPagerankValue(knoten);
              double y = this.getPagesPagerankValue(knoten);
              knoten.pageRankNew = x + y; //this.getPagesPagerankValue(knoten) + this.getTeleportPagerankValue(knoten);
          }
    }
    private double getTeleportPagerankValue(Knoten knoten) {
        return (this.teleportationPropability/this.getAnzahlKnoten());
    }

    private double getPagesPagerankValue(Knoten knoten) {
        double linkedPagerankValue = this.getLinkedPagerankValue(knoten);
        double nonLinkedPagesPagerankValue = this.getNonLinkedPagesPagerankValue(knoten);
        return (1.0 - this.teleportationPropability) * (linkedPagerankValue + nonLinkedPagesPagerankValue);
    }

    private double getLinkedPagerankValue(Knoten knoten) {
      double linkedPagerankValue = 0;
      for ( Knoten andereKnoten : this.knotenList )
      {
          if(andereKnoten.isLinkedWithPage(knoten))
          {
              linkedPagerankValue += andereKnoten.pageRankOld / (double)andereKnoten.numberOfOutgoingLinks();
          }
      }
      //System.out.println("linkedPagerankValue: " + linkedPagerankValue);
      return linkedPagerankValue;
    }    

    private double getNonLinkedPagesPagerankValue(Knoten knoten) {
          double nonLinkedPagerankValue = 0;
          for ( Knoten andereKnoten : this.knotenList )
          {
              if(andereKnoten.hasNoOutgoingLinks())
              {
                  nonLinkedPagerankValue += andereKnoten.pageRankOld / this.getAnzahlKnoten();
              }
          }
          //System.out.println("nonLinkedPagerankValue: " + nonLinkedPagerankValue);
        return nonLinkedPagerankValue;
    }
    private int getAnzahlKnoten() {
        return this.knotenList.size();
    }
    private void printPageRankSum() {
        double sumPagerank = 0;
          for ( Knoten andereKnoten : this.knotenList )
          {
              sumPagerank += andereKnoten.pageRankNew;
          }
        System.out.println("Summe Pagerank:" + sumPagerank);
    }
}

Ein Knoten (eine Page/Seite) Klasse:

import java.io.Serializable;
import java.util.ArrayList;
import java.util.List;

public class Knoten implements Serializable{

    public List<String> links;
    public String pageUrl;
    public double pageRankOld = 0;
    public double pageRankNew = 0;

    Knoten(String pageUrl, List<String> links) {
        this.pageUrl = pageUrl;
        this.links = links;
    }
    public int numberOfOutgoingLinks() {
        return this.links.size();
    }
    public boolean isLinkedWithPage(Knoten knoten) {
        String knotenUrl = knoten.pageUrl;
          for ( String weburl : this.links )
          {
              if(knotenUrl.equals(weburl))
              {
                  return true;
              }
          }
        return false;
    }
    public boolean hasNoOutgoingLinks() {
        if(this.links.size() == 0)
        {
            return true;
        }
        return false;
    }