id: 05794725
dt: a
an: 05794725
au: Csáji, Balázs Csanád; Jungers, Raphaël M.; Blondel, Vincent D.
ti: PageRank optimization in polynomial time by stochastic shortest path
    reformulation.
so: Hutter, Marcus (ed.) et al., Algorithmic learning theory. 21st
    international conference, ALT 2010, Canberra, Australia, October 6‒8,
    2010. Proceedings. Berlin: Springer (ISBN 978-3-642-16107-0/pbk).
    Lecture Notes in Computer Science 6331. Lecture Notes in Artificial
    Intelligence, 89-103 (2010).
py: 2010
pu: Berlin: Springer
la: EN
cc: 
ut: PageRank; graphs; complexity; Markov decision processes
ci: 
li: doi:10.1007/978-3-642-16108-7_11
ab: Summary: The importance of a node in a directed graph can be measured by
    its PageRank. The PageRank of a node is used in a number of application
    contexts ‒ including ranking websites ‒ and can be interpreted as
    the average portion of time spent at the node by an infinite random
    walk. We consider the problem of maximizing the PageRank of a node by
    selecting some of the edges from a set of edges that are under our
    control. By applying results from Markov decision theory, we show that
    an optimal solution to this problem can be found in polynomial time. It
    also indicates that the provided reformulation is well-suited for
    reinforcement learning algorithms. Finally, we show that, under the
    slight modification for which we are given mutually exclusive pairs of
    edges, the problem of PageRank optimization becomes NP-hard.
rv: