Conditioning of the entries in the stationary vector of a Google-type matrix (Q855557): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 01:24, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Conditioning of the entries in the stationary vector of a Google-type matrix |
scientific article |
Statements
Conditioning of the entries in the stationary vector of a Google-type matrix (English)
0 references
7 December 2006
0 references
Given a stationary vector \(\alpha^T\) of a stochastic matrix of the form \(cA + (I - c)B\), where \(c \in(0, 1)\) is a scalar, and \(A\) and \(B\) are stochastic matrices, with rank \(B\) = 1, condition bounds for \(\alpha^T\) are given. Based on combinatorial and analytic techniques the conditioning bounds considered include normwise, absolute componentwise, and relative componentwise bounds. 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\). If a vertex is on only long cycles in that directed graph, then the corresponding entry in \(\alpha^T\) exhibits better conditioning properties, and that for dangling nodes, the sensitivity of the corresponding entries in \(\alpha^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 \(\alpha^T\).
0 references
Stochastic matrix
0 references
stationary vector
0 references
condition number
0 references
PageRank
0 references
rank
0 references
directed graph
0 references
power method
0 references