On the Complexity of Optimizing PageRank
作者： Jean-Charles Delvenne , Raphaël M. Jungers , Romain Hollanders
DOI:
关键词:
摘要: We consider the PageRank Optimization problem in which one seeks to maximize (or minimize) of a node graph through adding or deleting links from given subset. The can be modeled as Markov Decision Process and has recently received much attention. provide provably efficient methods solve on large graphs for number cases practical importance we show using perturbation analysis that close variation problem, same techniques have exponential worst case complexity.
archives-ouvertes.fr参考文章(17)
Sheri M Markose, Ali Rais Shaghaghi, Simone Giansante, Mateusz Gatkowski, Too Interconnected To Fail: Financial Contagion and Systemic Risk in Network Model of CDS and Other Credit Enhancement Obligations of US Banks Research Papers in Economics. ,(2010)
Thomas Dueholm Hansen, Uri Zwick, Lower Bounds for Howard’s Algorithm for Finding Minimum Mean-Cost Cycles Algorithms and Computation. pp. 415- 426 ,(2010) , 10.1007/978-3-642-17517-6_37
John Fearnley, Exponential Lower Bounds for Policy Iteration Automata, Languages and Programming. pp. 551- 562 ,(2010) , 10.1007/978-3-642-14162-1_46
Yinyu Ye, The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate Mathematics of Operations Research. ,vol. 36, pp. 593- 603 ,(2011) , 10.1287/MOOR.1110.0516
Morten L Bech, James TE Chapman, Rodney J Garratt, None, Which bank is the “central” bank? Journal of Monetary Economics. ,vol. 57, pp. 352- 363 ,(2010) , 10.1016/J.JMONECO.2010.01.002
Hideaki ISHII, Roberto TEMPO, Computing the PageRank Variation for Fragile Web Data SICE journal of control, measurement, and system integration. ,vol. 2, pp. 1- 9 ,(2009) , 10.9746/JCMSI.2.1
Ronald A. Howard, Dynamic Programming and Markov Processes ,(1960)
Romain Hollanders, Jean-Charles Delvenne, Raphael M. Jungers, The complexity of Policy Iteration is exponential for discounted Markov Decision Processes conference on decision and control. pp. 5997- 6002 ,(2012) , 10.1109/CDC.2012.6426485
Andrea Fracasso, Stefano Schiavo, Global imbalances, exchange rates adjustment and the crisis: Implications from network analysis Journal of Policy Modeling. ,vol. 31, pp. 601- 619 ,(2009) , 10.1016/J.JPOLMOD.2009.05.016
Omid Madani, Mikkel Thorup, Uri Zwick, Discounted deterministic Markov decision processes and discounted all-pairs shortest paths ACM Transactions on Algorithms. ,vol. 6, pp. 33- ,(2010) , 10.1145/1721837.1721849