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

From MaRDI portal
Revision as of 01:24, 5 March 2024 by Import240304020342 (talk | contribs) (Set profile property.)
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
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references