danglepr

scikit-network's default PageRank solver returns a vector that is not the stationary distribution of the Google matrix when the directed graph has a dangling node, one with no out-edges. PageRank sends a dangling node's probability to every node through the restart vector; the default solver instead builds a static teleport term from a boolean out-degree mask, giving a dangling node its full seed and never redistributing the sink mass. On a graph with a sink the default solver is far from the true PageRank and ranks the dangling node first, while the sibling solvers diteration and RH return the correct vector exactly, so the class disagrees with itself.

The code

scikit-network, sknetwork/linalg/ppr_solver.py, RandomSurferOperator, 0.33.0 and current main (identical), lines 43-52:

out_degrees = adjacency.dot(np.ones(n)).astype(bool)          # boolean: has any out-edge
self.a = (damping_factor * normalize(adjacency)).T.tocsr()
self.b = (np.ones(n) - damping_factor * out_degrees) * seeds  # dangling node keeps its full seed
def _matvec(self, x):
    return self.a.dot(x) + self.b * x.sum()

A node with out-edges contributes (1 - d) * seed; a dangling node, whose out_degrees entry is False, contributes the full seed, and the operator never spreads the total sink mass across the nodes through the restart vector. The correct Google update is x' = d P^T x + v (1 - d) + v d Sigma_sink x_j, where the sink mass is a scalar spread over all nodes by v. The default solver piteration (and lanczos, bicgstab) uses this operator; the sibling diteration and RH solvers do not, and they are correct. The fix is to redistribute the dangling mass through v.

What it does

The random-surfer fixed point and the true Google stationary on a 4-node digraph whose node 3 is a sink:

Google stationary (true PageRank): [0.234  0.1867 0.3453 0.234 ]  residual 1.4e-16  top 2
surfer fixed point (sknetwork default): [0.1765 0.1324 0.2647 0.4265]  residual 0.186  top 3

Driving the real library:

default PageRank: [0.1766 0.1321 0.2647 0.4265] residual 0.186 top 3
true Google stationary: [0.234  0.1867 0.3453 0.234 ] residual 1.4e-16 top 2
rank flips to dangling node: True

solvers on the same graph (default params):
  piteration  residual 0.186  top 3
  diteration  residual 0.000  top 2
  RH          residual 0.000  top 2
  lanczos     residual 0.186  top 3
  bicgstab    residual 0.248  top 3
  diteration matches true: True; piteration matches true: False

no dangling node, all solvers correct: True  residuals {'piteration': 0.0, 'diteration': 0.0, 'RH': 0.0}

The residual is max|G^T pi - pi|, zero at the true stationary distribution. The default solver returns a vector with residual 0.186, so it is not the PageRank of the graph, and it ranks the dangling node 3 first, a node with no out-links that cannot be the most central under PageRank. The sibling diteration and RH solvers return the true vector to machine precision on the same call, which is the self-inconsistency and which pins the fault to the dangling handling in the default operator; bicgstab gives yet a third answer. Adding a single out-edge to node 3 removes the dangling node, and then every solver agrees with the Google stationary, isolating the fault.

Scope

piteration is the default solver and a dangling node is the ordinary case for a directed graph, crawled web graphs, citation graphs, and food webs all have sinks. The failure is silent: the scores still sum to one and look like a ranking, but they are not the stationary distribution and the ordering is wrong, so downstream ranking and centrality are corrupted whenever a sink is present. The error is a wrong teleport term, not floating-point round-off, and the sibling solvers compute the correct value. The fix is to spread the dangling mass through the restart vector.

Layout

• excerpt.py: the operator's out-degree mask, teleport term, and matvec quoted with the flags that name the fault, and the correct dangling redistribution.
• surfer.py: the Google matrix and stationary distribution, and the fixed point of the default operator, so the default reproduces sknetwork and the correct update reproduces the stationary distribution.
• consequence.py: the real PageRank, the default solver far from the stationary distribution and ranking the sink first, the sibling solvers correct, and the no-sink case where all agree.
• test_danglepr.py: the model surfer fixed point is not stationary and ranks the sink first while the Google stationary is exact, the real default disagrees with the true vector and flips the rank, the sibling solvers agree with the truth, and the no-sink case is correct.

Reproduce

python surfer.py
python consequence.py
python test_danglepr.py

The operator is quoted from current main; the scores are produced by the real PageRank solvers. The fix is to redistribute the dangling mass through the restart vector.