/*
 * (C) Copyright 2016-2017, by Dimitrios Michail and Contributors.
 *
 * JGraphT : a free Java graph-theory library
 *
 * This program and the accompanying materials are dual-licensed under
 * either
 *
 * (a) the terms of the GNU Lesser General Public License version 2.1
 * as published by the Free Software Foundation, or (at your option) any
 * later version.
 *
 * or (per the licensee's choosing)
 *
 * (b) the terms of the Eclipse Public License v1.0 as published by
 * the Eclipse Foundation.
 */
package org.jgrapht.alg.scoring;

import java.util.*;

import org.jgrapht.*;
import org.jgrapht.alg.interfaces.*;

/**
 * PageRank implementation.
 * 
 * 

* The wikipedia article contains a nice * description of PageRank. The method can be found on the article: Sergey Brin and Larry Page: The * Anatomy of a Large-Scale Hypertextual Web Search Engine. Proceedings of the 7th World-Wide Web * Conference, Brisbane, Australia, April 1998. See also the following * page. *

* *

* This is a simple iterative implementation of PageRank which stops after a given number of * iterations or if the PageRank values between two iterations do not change more than a predefined * value. The implementation uses the variant which divides by the number of nodes, thus forming a * probability distribution over graph nodes. *

* *

* Each iteration of the algorithm runs in linear time O(n+m) when n is the number of nodes and m * the number of edges of the graph. The maximum number of iterations can be adjusted by the caller. * The default value is {@link PageRank#MAX_ITERATIONS_DEFAULT}. *

* *

* If the graph is a weighted graph, a weighted variant is used where the probability of following * an edge e out of node v is equal to the weight of e over the sum of weights of all outgoing edges * of v. *

* * @param the graph vertex type * @param the graph edge type * * @author Dimitrios Michail * @since August 2016 */ public final class PageRank implements VertexScoringAlgorithm { /** * Default number of maximum iterations. */ public static final int MAX_ITERATIONS_DEFAULT = 100; /** * Default value for the tolerance. The calculation will stop if the difference of PageRank * values between iterations change less than this value. */ public static final double TOLERANCE_DEFAULT = 0.0001; /** * Damping factor default value. */ public static final double DAMPING_FACTOR_DEFAULT = 0.85d; private final Graph g; private Map scores; /** * Create and execute an instance of PageRank. * * @param g the input graph */ public PageRank(Graph g) { this(g, DAMPING_FACTOR_DEFAULT, MAX_ITERATIONS_DEFAULT, TOLERANCE_DEFAULT); } /** * Create and execute an instance of PageRank. * * @param g the input graph * @param dampingFactor the damping factor */ public PageRank(Graph g, double dampingFactor) { this(g, dampingFactor, MAX_ITERATIONS_DEFAULT, TOLERANCE_DEFAULT); } /** * Create and execute an instance of PageRank. * * @param g the input graph * @param dampingFactor the damping factor * @param maxIterations the maximum number of iterations to perform */ public PageRank(Graph g, double dampingFactor, int maxIterations) { this(g, dampingFactor, maxIterations, TOLERANCE_DEFAULT); } /** * Create and execute an instance of PageRank. * * @param g the input graph * @param dampingFactor the damping factor * @param maxIterations the maximum number of iterations to perform * @param tolerance the calculation will stop if the difference of PageRank values between * iterations change less than this value */ public PageRank(Graph g, double dampingFactor, int maxIterations, double tolerance) { this.g = g; this.scores = new HashMap<>(); if (maxIterations <= 0) { throw new IllegalArgumentException("Maximum iterations must be positive"); } if (dampingFactor < 0.0 || dampingFactor > 1.0) { throw new IllegalArgumentException("Damping factor not valid"); } if (tolerance <= 0.0) { throw new IllegalArgumentException("Tolerance not valid, must be positive"); } run(dampingFactor, maxIterations, tolerance); } /** * {@inheritDoc} */ @Override public Map getScores() { return Collections.unmodifiableMap(scores); } /** * {@inheritDoc} */ @Override public Double getVertexScore(V v) { if (!g.containsVertex(v)) { throw new IllegalArgumentException("Cannot return score of unknown vertex"); } return scores.get(v); } private void run(double dampingFactor, int maxIterations, double tolerance) { // initialization Specifics specifics; if (g instanceof DirectedGraph) { specifics = new DirectedSpecifics((DirectedGraph) g); } else { specifics = new UndirectedSpecifics(g); } int totalVertices = g.vertexSet().size(); boolean weighted = (g instanceof WeightedGraph); Map weights; if (weighted) { weights = new HashMap<>(totalVertices); } else { weights = Collections.emptyMap(); } double initScore = 1.0d / totalVertices; for (V v : g.vertexSet()) { scores.put(v, initScore); if (weighted) { double sum = 0; for (E e : specifics.outgoingEdgesOf(v)) { sum += g.getEdgeWeight(e); } weights.put(v, sum); } } // run PageRank Map nextScores = new HashMap<>(); double maxChange = tolerance; while (maxIterations > 0 && maxChange >= tolerance) { // compute next iteration scores double r = 0d; for (V v : g.vertexSet()) { if (specifics.outgoingEdgesOf(v).size() > 0) { r += (1d - dampingFactor) * scores.get(v); } else { r += scores.get(v); } } r /= totalVertices; maxChange = 0d; for (V v : g.vertexSet()) { double contribution = 0d; if (weighted) { for (E e : specifics.incomingEdgesOf(v)) { V w = Graphs.getOppositeVertex(g, e, v); contribution += dampingFactor * scores.get(w) * g.getEdgeWeight(e) / weights.get(w); } } else { for (E e : specifics.incomingEdgesOf(v)) { V w = Graphs.getOppositeVertex(g, e, v); contribution += dampingFactor * scores.get(w) / specifics.outgoingEdgesOf(w).size(); } } double vOldValue = scores.get(v); double vNewValue = r + contribution; maxChange = Math.max(maxChange, Math.abs(vNewValue - vOldValue)); nextScores.put(v, vNewValue); } // swap scores Map tmp = scores; scores = nextScores; nextScores = tmp; // progress maxIterations--; } } abstract class Specifics { public abstract Set outgoingEdgesOf(V vertex); public abstract Set incomingEdgesOf(V vertex); } class DirectedSpecifics extends Specifics { private DirectedGraph graph; public DirectedSpecifics(DirectedGraph g) { graph = g; } @Override public Set outgoingEdgesOf(V vertex) { return graph.outgoingEdgesOf(vertex); } @Override public Set incomingEdgesOf(V vertex) { return graph.incomingEdgesOf(vertex); } } class UndirectedSpecifics extends Specifics { private Graph graph; public UndirectedSpecifics(Graph g) { graph = g; } @Override public Set outgoingEdgesOf(V vertex) { return graph.edgesOf(vertex); } @Override public Set incomingEdgesOf(V vertex) { return graph.edgesOf(vertex); } } }

Ads help maintain this website.