pageRank function

List<double> pageRank(Adjacency graph, { double damping = 0.85, int iterations = 100, double tolerance = 1e-9, })

PageRank scores for every node, summing to approximately 1.0.

damping is the follow-a-link probability (the classic value is 0.85). iterations caps the power-iteration passes; tolerance stops early once the total absolute change (L1 norm) between passes drops below it, which is the normal exit for well-connected graphs. An empty graph yields [].

Example:

final Adjacency g = buildGraph([(0, 1), (1, 2), (2, 0)], 3);
pageRank(g); // ~[0.333, 0.333, 0.333]

Audited: 2026-06-12 11:26 EDT

Implementation

List<double> pageRank(
  Adjacency graph, {
  double damping = 0.85,
  int iterations = 100,
  double tolerance = 1e-9,
}) {
  final int n = graph.length;
  // Empty graph has no ranks to distribute; bail before dividing by zero.
  if (n == 0) return <double>[];
  // Start from the uniform distribution so every node has equal initial mass.
  List<double> rank = List<double>.filled(n, 1.0 / n);
  for (int it = 0; it < iterations; it++) {
    final List<double> next = _pageRankStep(graph, rank, damping);
    // L1 change measures how far the distribution moved; once it settles below
    // tolerance further passes are wasted, so stop early.
    double delta = 0;
    for (int i = 0; i < n; i++) {
      delta += (next[i] - rank[i]).abs();
    }
    rank = next;
    if (delta < tolerance) break;
  }
  return rank;
}