Conditioning of the entries in the stationary vector of a Google-type matrix

Using combinatorial and analytic techniques, we give conditioning bounds for the stationary vector πT of a stochastic matrix of the form cA + (1 − c)B, where c ∈ (0, 1) is a scalar, and A and B are stochastic matrices, the latter being rank one. Such matrices and their stationary vectors arise as a key component in Google’s PageRank algorithm. The conditioning bounds considered include normwise, absolute componentwise, and relative componentwise, and the bounds depend on c, and on quantities such as the number of dangling nodes (which correspond to rows of A having all entries equal), or the lengths of certain cycles in the directed graph associated with A. It is shown that if vertex j is on only long cycles in that directed graph, then the corresponding entry in πT exhibits better conditioning properties, and that for dangling nodes, the sensitivity of the corresponding entries in πT decreases as the number of dangling nodes increases. Conditions are given that are sufficient to ensure that an iterate of the power method accurately reflects the relative ordering of two entries in πT.