PGX 20.2.2
Documentation

PageRank Algorithms

Assigns a numerical weight to each vertex, measuring its relative importance within the graph.


Classic PageRank

Category ranking and walking

Algorithm ID pgx_builtin_k1a_pagerank

Time Complexity O(E * k) with E = number of edges, k <= maximum number of iterations

Space Requirement O(V) with V = number of vertices

Javadoc


PageRank is an algorithm that computes ranking scores for the vertices using the network created by the incoming edges in the graph. Thus it is intended for directed graphs, although undirected graphs can be treated as well by converting them into directed graphs with reciprocated edges (i.e. keeping the original edge and creating a second one going in the opposite direction). The edges on the graph will define the relevance of each vertex in the graph, reflecting this on the scores, meaning that greater scores will correspond to vertices with greater relevance.

Signature

Input Argument Type Comment
G graph
tol double maximum tolerated error value. The algorithm will stop once the sum of the error values of all vertices becomes smaller than this value.
damp double damping factor.
max_iter int maximum number of iterations that will be performed.
norm boolean boolean flag to determine whether the algorithm will take into account dangling vertices for the ranking scores.
Output Argument Type Comment
rank vertexProp vertex property holding the (normalized) PageRank value for each vertex (a value between 0 and 1).

Code

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
package oracle.pgx.algorithms;

import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.Scalar;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Out;

@GraphAlgorithm
public class Pagerank {
  public void pagerank(PgxGraph g, double tol, double damp, int maxIter, boolean norm,
      @Out VertexProperty<Double> rank) {
    Scalar<Double> diff = Scalar.create();
    int cnt = 0;
    double n = g.getNumVertices();

    rank.setAll(1 / n);
    do {
      diff.set(0.0);
      Scalar<Double> danglingFactor = Scalar.create(0d);

      if (norm) {
        danglingFactor.set(damp / n * g.getVertices().filter(v -> v.getOutDegree() == 0).sum(rank::get));
      }

      g.getVertices().forEach(t -> {
        double inSum = t.getInNeighbors().sum(w -> rank.get(w) / w.getOutDegree());
        double val = (1 - damp) / n + damp * inSum + danglingFactor.get();
        diff.reduceAdd(Math.abs(val - rank.get(t)));
        rank.setDeferred(t, val);
      });
      cnt++;
    } while (diff.get() > tol && cnt < maxIter);
  }
}
/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */

procedure pagerank(graph G, double tol, double damp, int max_iter, bool norm; vertexProp<double> rank) {

  double diff;
  int cnt = 0;
  double N = G.numNodes();

  G.rank = 1 / N;
  do {
    diff = 0.0;
    double dangling_factor = 0;

    if (norm) {
      dangling_factor = damp / N * sum (v: G.nodes) (v.outDegree() == 0) {v.rank};
    }

    foreach (t: G.nodes) {
      double in_sum = sum (w: t.inNbrs) {w.rank / w.outDegree()};
      double val = (1 - damp) / N + damp * in_sum + dangling_factor;
      diff += |val - t.rank|;
      t.rank <= val;
    }
    cnt++;
  } while (diff > tol && cnt < max_iter);

}

Approximate PageRank

Category ranking and walking

Algorithm ID pgx_builtin_k1b_pagerank_approximate

Time Complexity O(E * k) with E = number of edges, k <= maximum number of iterations

Space Requirement O(V) with V = number of vertices

Javadoc


This variant of the PageRank algorithm computes the ranking scores for the vertices in similar way to the classic algorithm without normalization and with a more relaxed convergence criteria, since the tolerated error value is compared against each single vertex in the graph, instead of looking at the cumulative vertex error. Thus this variant will converge faster than the classic algorithm, but the ranking values might not be as accurate as in the classic implementation.

Signature

Input Argument Type Comment
G graph
tol double maximum tolerated error value. The algorithm will stop once the sum of the error values of all vertices becomes smaller than this value.
damp double damping factor.
max_iter int maximum number of iterations that will be performed.
Output Argument Type Comment
rank vertexProp vertex property holding the (normalized) PageRank value for each vertex (a value between 0 and 1).

Code

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
package oracle.pgx.algorithms;

import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.Scalar;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.annotations.Out;

@GraphAlgorithm
public class PagerankApproximate {
  public void approximatePagerank(PgxGraph g, double tol, double damp, int maxIter, @Out VertexProperty<Double> rank) {
    VertexProperty<Boolean> active = VertexProperty.create();
    VertexProperty<Double> myDelta = VertexProperty.create();
    VertexProperty<Double> newDelta = VertexProperty.create();

    double initialRankValue = 1.0 / g.getNumVertices();

    // initialize
    Scalar<Boolean> nodesActive = Scalar.create(true);
    Scalar<Integer> iteration = Scalar.create(0);
    active.setAll(true);
    myDelta.setAll(initialRankValue);
    newDelta.setAll(0.0);
    rank.setAll(initialRankValue);

    // push
    while (nodesActive.get() && iteration.get() < maxIter) {
      nodesActive.set(false);

      // push
      g.getVertices().filter(active).forEach(n ->
          n.getOutNeighbors().forEach(k -> newDelta.reduceAdd(k, myDelta.get(n) / n.getOutDegree()))
      );

      // consolidate
      g.getVertices().forEach(n -> {
        double newPageRank;
        double normalizedDelta;

        if (iteration.get() == 0) { // first iteration needs special handling
          newPageRank = initialRankValue * (1 - damp) + damp * newDelta.get(n);
          normalizedDelta = newPageRank - initialRankValue;
        } else {
          newPageRank = rank.get(n) + damp * newDelta.get(n);
          normalizedDelta = damp * newDelta.get(n);
        }

        rank.set(n, newPageRank);
        myDelta.set(n, normalizedDelta);

        if (normalizedDelta < 0) {
          normalizedDelta = -1 * normalizedDelta;
        }

        if (normalizedDelta < tol) {
          active.set(n, false);
        } else {
          active.set(n, true);
          nodesActive.reduceOr(true);
        }
        newDelta.set(n, 0d);
      });
      iteration.increment();
    }
  }
}
/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */

procedure approximate_pagerank(graph G, double tol, double damp, int max_iter; vertexProp<double> rank) {

  vertexProp<bool> active;
  vertexProp<double> my_delta;
  vertexProp<double> new_delta;

  double initial_rank_value = 1.0 / G.numNodes();

  // initialize
  bool nodes_active = true;
  int iteration = 0;
  double N = G.numNodes();
  G.active = true;
  G.my_delta = initial_rank_value;
  G.new_delta = 0.0;
  G.rank = initial_rank_value;

  // push
  while (nodes_active && iteration < max_iter) {

    nodes_active = false;

    // push
    foreach (n: G.nodes) (n.active) {
      foreach(k: n.outNbrs) {
        k.new_delta += n.my_delta / n.outDegree();
      }
    }

    // consolidate
    foreach(n: G.nodes) {

      double new_page_rank;
      double normalized_delta;

      if (iteration == 0) { // first iteration needs special handling
        new_page_rank = initial_rank_value * (1 - damp) + damp * n.new_delta;
        normalized_delta = new_page_rank - initial_rank_value;
      }
      else {
        new_page_rank = n.rank + damp * n.new_delta;
        normalized_delta = damp * n.new_delta;
      }

      n.rank = new_page_rank;
      n.my_delta = normalized_delta;

      if (normalized_delta < 0) {
        normalized_delta = -1 * normalized_delta;
      }

      if (normalized_delta < tol) {
        n.active = false;
      } else {
        n.active = true;
        nodes_active |= true;
      }
      n.new_delta = 0;
    }
    iteration++;
  }
}

Weighted PageRank

Category ranking and walking

Algorithm ID pgx_builtin_k1c_pagerank_weighted

Time Complexity O(E * k) with E = number of edges, k <= maximum number of iterations

Space Requirement O(2 * V) with V = number of vertices

Javadoc


The Weighted PageRank works like the original PageRank algorithm, except that it allows for a weight value assigned to each edge. This weight determines the fraction of the PageRank score that will flow from the source vertex through the current edge to its destination vertex.

Signature

Input Argument Type Comment
G graph
tol double maximum tolerated error value. The algorithm will stop once the sum of the error values of all vertices becomes smaller than this value.
damp double damping factor.
max_iter int maximum number of iterations that will be performed.
norm boolean boolean flag to determine whether the algorithm will take into account dangling vertices for the ranking scores.
weight edgeProp edge property holding the weight of each edge in the graph.
Output Argument Type Comment
rank vertexProp vertex property holding the (normalized) PageRank value for each vertex (a value between 0 and 1).

Code

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
package oracle.pgx.algorithms;

import oracle.pgx.algorithm.EdgeProperty;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.PgxEdge;
import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.Scalar;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.annotations.Out;

import static java.lang.Math.abs;

@GraphAlgorithm
public class PagerankWeighted {
  public void pagerankWeighted(PgxGraph g, double tol, double damp, int maxIter, boolean norm,
      EdgeProperty<Double> weight, @Out VertexProperty<Double> rank) {
    double numVertices = g.getNumVertices();
    rank.setAll(1.0 / numVertices);

    VertexProperty<Double> weightSum = VertexProperty.create();
    g.getVertices().forEach(n -> {
      weightSum.set(n, n.getOutEdges().sum(weight));
    });

    Scalar<Double> diff = Scalar.create();
    int cnt = 0;

    do {
      diff.set(0d);
      Scalar<Double> danglingFactor = Scalar.create();

      if (norm) {
        danglingFactor.set(damp / numVertices * g.getVertices().filter(v -> v.getOutDegree() == 0).sum(rank));
      }

      g.getVertices().forEach(t -> {
        Scalar<Double> s = Scalar.create(0d);
        t.getInNeighbors().forEach(src -> {
          PgxEdge in = src.edge();
          s.reduceAdd(rank.get(src) * weight.get(in) / weightSum.get(src));
        });
        double val = (1 - damp) / numVertices + damp * s.get() + danglingFactor.get();
        diff.reduceAdd(abs(val - rank.get(t)));
        rank.setDeferred(t, val);
      });
      cnt++;
    } while (diff.get() > tol && cnt < maxIter);
  }
}
/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */

procedure pagerank_weighted(graph G, double tol, double damp, int max_iter, bool norm,
    edgeProp<double> weight; vertexProp<double> rank) {

  double N = G.numNodes();
  G.rank = 1.0 / N;

  vertexProp<double> weight_sum;
  foreach (n: G.nodes) {
    n.weight_sum = sum(out: n.outEdges) {out.weight};
  }

  double diff;
  int cnt = 0;

  do {
    diff = 0.0;
    double dangling_factor = 0;

    if (norm) {
      dangling_factor = damp / N * sum (v: G.nodes) (v.outDegree() == 0) {v.rank};
    }

    foreach (t: G.nodes) {
      double s = 0.0;
      foreach (src: t.inNbrs) {
        edge in = src.edge();
        s += src.rank * in.weight / src.weight_sum;
      }
      double val = (1 - damp) / N + damp * s + dangling_factor;
      diff += |val - t.rank|;
      t.rank <= val;
    }
    cnt++;
  } while (diff > tol && cnt < max_iter);
}

Personalized PageRank

Category ranking and walking

Algorithm ID pgx_builtin_k2_personalized_pagerank

Time Complexity O(E * k) with E = number of edges, k <= maximum number of iterations

Space Requirement O(V) with V = number of vertices

Javadoc


The Personalized Pagerank allows to select a particular vertex or a set of vertices from the given graph in order to give them a greater importance when computing the ranking score, which will have as result a personalized Pagerank score and reveal relevant (or similar) vertices to the ones chosen at the beginning.

Signature

Input Argument Type Comment
G graph
v node the chosen vertex from the graph for personalization.
tol double maximum tolerated error value. The algorithm will stop once the sum of the error values of all vertices becomes smaller than this value.
damp double damping factor.
max_iter int maximum number of iterations that will be performed.
norm boolean boolean flag to determine whether the algorithm will take into account dangling vertices for the ranking scores.
Output Argument Type Comment
rank vertexProp vertex property holding the (normalized) PageRank value for each vertex (a value between 0 and 1).

Code

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
package oracle.pgx.algorithms;

import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.PgxVertex;
import oracle.pgx.algorithm.Scalar;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.annotations.Out;

import static java.lang.Math.abs;

@GraphAlgorithm
public class PagerankPersonalized {
  public void personalizedPagerank(PgxGraph g, PgxVertex v, double tol, double damp, int maxIter, boolean norm,
      @Out VertexProperty<Double> rank) {
    double numVertices = g.getNumVertices();
    Scalar<Double> diff = Scalar.create();
    int cnt = 0;
    rank.setAll(0d);
    rank.set(v, 1.0);

    do {
      diff.set(0.0);
      Scalar<Double> danglingFactor = Scalar.create(0d);

      if (norm) {
        danglingFactor.set(damp / numVertices * g.getVertices().filter(n -> n.getOutDegree() == 0).sum(rank));
      }

      g.getVertices().forEach(t -> {
        double val1 = (t == v) ? (1 - damp) : 0;
        double val2 = damp * t.getInNeighbors().sum(w -> rank.get(w) / w.getOutDegree());
        double val = val1 + val2 + danglingFactor.get();
        diff.reduceAdd(abs(val - rank.get(t)));
        rank.setDeferred(t, val);
      });
      cnt++;
    } while (diff.get() > tol && cnt < maxIter);
  }
}
/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */

procedure personalized_pagerank(graph G, node v, double tol, double damp, int max_iter, bool norm;
    vertexProp<double> rank) {

  double N = G.numNodes();

  double diff;
  int cnt = 0;
  G.rank = 0;
  v.rank = 1.0;

  do {
    diff = 0.0;
    double dangling_factor = 0;

    if (norm) {
      dangling_factor = damp / N * sum (n: G.nodes) (n.outDegree() == 0) {n.rank};
    }

    foreach (t: G.nodes) {
      double val1 = (t == v) ? (1 - damp) : 0;
      double val2 = damp * sum (w: t.inNbrs) {w.rank / w.outDegree()};
      double val = val1 + val2 + dangling_factor;
      diff += |val - t.rank|;
      t.rank <= val;
    }
    cnt++;
  } while (diff > tol && cnt < max_iter);
}

Personalized PageRank (for a set of vertices)

Category ranking and walking

Algorithm ID pgx_builtin_k2b_personalized_pagerank_from_set

Time Complexity O(E * k) with E = number of edges, k <= maximum number of iterations

Space Requirement O(2 * V) with V = number of vertices

Javadoc


The Personalized Pagerank allows to select a particular vertex or a set of vertices from the given graph in order to give them a greater importance when computing the ranking score, which will have as result a personalized Pagerank score and reveal relevant (or similar) vertices to the ones chosen at the begining.

Signature

Input Argument Type Comment
G graph
source nodeSet the set of chosen vertices from the graph for personalization.
tol double maximum tolerated error value. The algorithm will stop once the sum of the error values of all vertices becomes smaller than this value.
damp double damping factor.
max_iter int maximum number of iterations that will be performed.
norm boolean boolean flag to determine whether the algorithm will take into account dangling vertices for the ranking scores.
Output Argument Type Comment
rank vertexProp vertex property holding the (normalized) PageRank value for each vertex (a value between 0 and 1).

Code

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
package oracle.pgx.algorithms;

import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.Scalar;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.VertexSet;
import oracle.pgx.algorithm.annotations.Out;

import static java.lang.Math.abs;

@GraphAlgorithm
public class PagerankPersonalizedSet {
  public void personalizedPagerank(PgxGraph g, VertexSet source, double tol, double damp, int maxIter, boolean norm,
      @Out VertexProperty<Double> rank) {
    double numVertices = g.getNumVertices();
    long m = source.size();

    Scalar<Double> diff = Scalar.create();
    int cnt = 0;

    VertexProperty<Boolean> isStart = VertexProperty.create(false);
    rank.setAll(0d);

    source.forEach(n -> {
      rank.set(n, 1.0 / m);
      isStart.set(n, true);
    });

    do {
      diff.set(0.0);
      Scalar<Double> danglingFactor = Scalar.create(0d);

      if (norm) {
        danglingFactor.set(damp / numVertices * g.getVertices().filter(n -> n.getOutDegree() == 0).sum(rank));
      }

      g.getVertices().forEach(t -> {
        double val1 = (isStart.get(t)) ? (1 - damp) : 0;
        double val2 = damp * t.getInNeighbors().sum(w -> rank.get(w) / w.getOutDegree());
        double val = val1 + val2 + danglingFactor.get();
        diff.reduceAdd(abs(val - rank.get(t)));
        rank.setDeferred(t, val);
      });
      cnt++;
    } while (diff.get() > tol && cnt < maxIter);

    g.getVertices().forEach(n -> rank.set(n, rank.get(n) / m));
  }
}
/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */

procedure personalized_pagerank_from_set(graph G, nodeSet source, double tol, double damp, int max_iter,
      bool norm; vertexProp<double> rank) {

  double N = G.numNodes();
  int M = source.size();

  double diff;
  int cnt = 0;

  vertexProp<bool> is_start;
  G.rank = 0;
  G.is_start = false;

  foreach (n: source.items) {
    n.rank = 1.0 / M;
    n.is_start = true;
  }

  do {
    diff = 0.0;
    double dangling_factor = 0;

    if (norm) {
      dangling_factor = damp / N * sum (n: G.nodes) (n.outDegree() == 0) {n.rank};
    }

    foreach (t: G.nodes) {
      double val1 = (t.is_start) ? (1 - damp) : 0;
      double val2 = damp * sum (w: t.inNbrs) {w.rank / w.outDegree()} ;
      double val = val1 + val2 + dangling_factor;
      diff += |val - t.rank|;
      t.rank <= val;
    }
    cnt++;
  } while (diff > tol && cnt < max_iter);

  foreach (n: G.nodes) {
    n.rank = n.rank / M;
  }
}

Personalized Weighted PageRank

Category ranking and walking

Algorithm ID pgx_builtin_k2c_personalized_weighted_pagerank

Time Complexity O(E * k) with E = number of edges, k <= maximum number of iterations

Space Requirement O(2 * V) with V = number of vertices

Javadoc


The Personalized Weighted Pagerank combines elements from the weighted and the personalized versions in order to make the personalization of the results more unique, since both: the selection of a subset of vertices and the inclusion of specific weights in the edges, will help to set the importance of the ranking scores when these are being computed.

Signature

Input Argument Type Comment
G graph
v node the chosen vertex from the graph for personalization.
tol double maximum tolerated error value. The algorithm will stop once the sum of the error values of all vertices becomes smaller than this value.
damp double damping factor.
max_iter int maximum number of iterations that will be performed.
norm boolean boolean flag to determine whether the algorithm will take into account dangling vertices for the ranking scores.
weight edgeProp edge property holding the weight of each edge in the graph.
Output Argument Type Comment
rank vertexProp vertex property holding the (normalized) weighted PageRank value for each vertex (a value between 0 and 1).

Code

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
package oracle.pgx.algorithms;

import oracle.pgx.algorithm.EdgeProperty;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.PgxEdge;
import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.PgxVertex;
import oracle.pgx.algorithm.Scalar;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.annotations.Out;

import static java.lang.Math.abs;

@GraphAlgorithm
public class PagerankPersonalizedWeighted {
  public void pagerankPersonalizedWeighted(PgxGraph g, PgxVertex v, double tol, double damp, int maxIter, boolean norm,
      EdgeProperty<Double> weight, @Out VertexProperty<Double> rank) {
    double numVertices = g.getNumVertices();
    rank.setAll(0d);
    rank.set(v, 1.0);

    VertexProperty<Double> weightSum = VertexProperty.create();
    g.getVertices().forEach(n -> {
      weightSum.set(n, n.getOutEdges().sum(weight));
    });

    Scalar<Double> diff = Scalar.create();
    int cnt = 0;

    do {
      diff.set(0.0);
      Scalar<Double> danglingFactor = Scalar.create(0d);

      if (norm) {
        danglingFactor.set(damp / numVertices * g.getVertices().filter(n -> n.getOutDegree() == 0).sum(rank));
      }

      g.getVertices().forEach(t -> {
        double val1 = (t == v) ? (1 - damp) : 0;
        Scalar<Double> val2 = Scalar.create(0d);
        t.getInNeighbors().forEach(src -> {
          PgxEdge in = src.edge();
          val2.reduceAdd(rank.get(src) * weight.get(in) / weightSum.get(src));
        });
        double val = val1 + damp * val2.get() + danglingFactor.get();
        diff.reduceAdd(abs(val - rank.get(t)));
        rank.setDeferred(t, val);
      });
      cnt++;
    } while (diff.get() > tol && cnt < maxIter);
  }
}
/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */

procedure personlaized_weighted_pagerank(graph G, node v, double tol, double damp, int max_iter,
    bool norm, edgeProp<double> weight; vertexProp<double> rank) {

  double N = G.numNodes();
  G.rank = 0;
  v.rank = 1.0;

  vertexProp<double> weight_sum;
  foreach (n: G.nodes) {
    n.weight_sum = sum (out: n.outEdges) {out.weight};
  }

  double diff;
  int cnt = 0;

 do {
    diff = 0.0;
    double dangling_factor = 0;

    if (norm) {
      dangling_factor = damp / N * sum (n: G.nodes) (n.outDegree() == 0) {n.rank};
    }

    foreach (t: G.nodes) {
      double val1 = (t == v) ? (1 - damp) : 0;
      double val2 = 0.0;
      foreach (src: t.inNbrs) {
        edge in = src.edge();
        val2 += src.rank * in.weight / src.weight_sum;
      }
      double val = val1 + damp * val2 + dangling_factor;
      diff += |val - t.rank|;
      t.rank <= val;
    }
    cnt++;
  } while (diff > tol && cnt < max_iter);
}

Personalized Weighted PageRank (for a set of vertices)

Category ranking and walking

Algorithm ID pgx_builtin_k2d_personalized_weighted_pagerank_from_set

Time Complexity O(E * k) with E = number of edges, k <= maximum number of iterations

Space Requirement O(3 * V) with V = number of vertices

Javadoc


The Personalized Weighted Pagerank combines elements from the weighted and the personalized versions in order to make the personalization of the results more unique, since both: the selection of a subset of vertices and the inclusion of specific weights in the edges, will help to set the importance of the ranking scores when these are being computed.

Signature

Input Argument Type Comment
G graph
source nodeSet the set of chosen vertices from the graph for personalization.
tol double maximum tolerated error value. The algorithm will stop once the sum of the error values of all vertices becomes smaller than this value.
damp double damping factor.
max_iter int maximum number of iterations that will be performed.
norm boolean boolean flag to determine whether the algorithm will take into account dangling vertices for the ranking scores.
weight edgeProp edge property holding the weight of each edge in the graph.
Output Argument Type Comment
rank vertexProp vertex property holding the (normalized) PageRank value for each vertex (a value between 0 and 1).

Code

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
package oracle.pgx.algorithms;

import oracle.pgx.algorithm.EdgeProperty;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.PgxEdge;
import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.Scalar;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.VertexSet;
import oracle.pgx.algorithm.annotations.Out;

import static java.lang.Math.abs;

@GraphAlgorithm
public class PagerankPersonalizedWeightedSet {
  public void pagerankPersonalizedWeightedSet(PgxGraph g, VertexSet source, double tol, double damp, int maxIter,
      boolean norm, EdgeProperty<Double> weight, @Out VertexProperty<Double> rank) {
    double numVertices = g.getNumVertices();
    double m = source.size();

    VertexProperty<Double> weightSum = VertexProperty.create();
    g.getVertices().forEach(n -> weightSum.set(n, n.getOutEdges().sum(weight)));

    VertexProperty<Boolean> isStart = VertexProperty.create();
    rank.setAll(0d);
    isStart.setAll(false);

    source.forEach(n -> {
      rank.set(n, 1.0 / m);
      isStart.set(n, true);
    });

    Scalar<Double> diff = Scalar.create();
    int cnt = 0;

    do {
      diff.set(0.0);
      Scalar<Double> danglingFactor = Scalar.create(0d);

      if (norm) {
        danglingFactor.set(damp / numVertices * g.getVertices().filter(n -> n.getOutDegree() == 0).sum(rank));
      }

      g.getVertices().forEach(t -> {
        double val1 = isStart.get(t) ? (1 - damp) : 0;
        Scalar<Double> val2 = Scalar.create(0d);
        t.getInNeighbors().forEach(src -> {
          PgxEdge in = src.edge();
          val2.reduceAdd(rank.get(src) * weight.get(in) / weightSum.get(src));
        });
        double val = val1 + damp * val2.get() + danglingFactor.get();
        diff.reduceAdd(abs(val - rank.get(t)));
        rank.setDeferred(t, val);
      });
      cnt++;
    } while (diff.get() > tol && cnt < maxIter);

    g.getVertices().forEach(n -> rank.set(n, rank.get(n) / m));
  }
}
/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */

procedure personlaized_weighted_pagerank_from_set(graph G, nodeSet source, double tol, double damp, int max_iter,
    bool norm, edgeProp<double> weight; vertexProp<double> rank) {

  double N = G.numNodes();
  double M = source.size();

  vertexProp<double> weight_sum;

  foreach (n: G.nodes) {
    n.weight_sum = sum(out: n.outEdges) { out.weight };
  }

  vertexProp<bool> is_start;
  G.rank = 0;
  G.is_start = false;

  foreach (n: source.items) {
    n.rank = 1.0 / M;
    n.is_start = true;
  }

  double diff;
  int cnt = 0;

  do {
    diff = 0.0;
    double dangling_factor = 0;

    if (norm) {
      dangling_factor = damp / N * sum (n: G.nodes) (n.outDegree() == 0) {n.rank};
    }

    foreach (t: G.nodes) {
      double val1 = (t.is_start) ? (1 - damp) : 0;
      double val2 = 0.0;
      foreach (src: t.inNbrs) {
        edge in = src.edge();
        val2 += src.rank * in.weight / src.weight_sum;
      }
      double val = val1 + damp * val2 + dangling_factor;
      diff += |val - t.rank|;
      t.rank <= val;
    }
    cnt++;
  } while (diff > tol && cnt < max_iter);

  foreach (n: G.nodes) {
    n.rank = n.rank / M;
  }
}