Regularization-based solution of the PageRank problem for large matrices. (English. Russian original) Zbl 1268.93014
Autom. Remote Control 73, No. 11, 1877-1894 (2012); translation from Avtom. Telemekh. 2012, No. 11, 144-166 (2012).
Summary: For a column-stochastic matrix, consideration is given to determination of the eigenvector which corresponds to the unit eigenvalue. Such problems are encountered in many applications, – in particular, at ranking the web pages (PageRank). Since the PageRank problem is of special interest for larger matrices, the emphasis is made on the power method for direct iterative calculation of the eigenvector. Several variants of regularization of the power methods are compared, and their relations are considered. The distinctions of their realizations are given.
MSC:
| 93A15 | Large-scale systems |
| 93B60 | Eigenvalue problems |
| 93E25 | Computational methods in stochastic control (MSC2010) |
| 93E03 | Stochastic systems in control theory (general) |
Software:
WebGraphReferences:
| [1] | Brin, S. and Page, L., The Anatomy of a Large-Scale Hypertextual Web Search Engine, Comput. Networks ISDN Syst., 1998, vol. 30, nos. 1–7, pp. 107–117. · doi:10.1016/S0169-7552(98)00110-X |
| [2] | Romanovskii, V.I., Diskretnye tsepi Markova (Discrete Markov Chains) Moscow: Gostekhizdat, 1949. |
| [3] | Feller, W., An Introduction to Probability Theory and Its Applications, New York: Wiley, 1957. Translated under the title Vvedenie v teoriyu veroyatnostei i ee prilozheniya, Moscow: Mir, 1967. · Zbl 0077.12201 |
| [4] | Agaev, R.P. and Chebotarev, P.Yu., Convergence and Stability in the Problems of Coordination of Characteristics (Review of the Basic Results), Upravlen. Bol’shimi Sist., 2010, vol. 30.1, pp. 470–505. |
| [5] | Agaev, R.P. and Chebotarev, P.Yu., The ProjectionMethod for Reaching Consensus and the Regularized Power Limit of a Stochastic Matrix, Autom. Remote Control, 2011, vol. 72, no. 12, pp. 2458–2476. · Zbl 1269.93002 · doi:10.1134/S0005117911120034 |
| [6] | Leontief, W., Studies in the Structure of the American Economy, New York: Oxford Univ. Press, 1953. Translated under the title Issledovaniya struktury amerikanskoi ekonomiki, Moscow: Gosstatizdat, 1958. |
| [7] | Franceschet, M., PageRank: Standing on the Shoulders of Giants, Commun. ACM, 2011, vol. 54, no. 6, pp. 92–101. · doi:10.1145/1953122.1953146 |
| [8] | Polyak, B.T. and Timonina, A.V., PageRank: New Regularizations and Simulation Models, in Proc. 18th IFAC World Congress, Milano, Italy, August 28–September 2, 2011. pp. 11202–11207. |
| [9] | Langville, A.N. and Meyer, C.D., Google’s PageRank and Beyond: The Science of Search Engine Rankings, Princeton: Princeton Univ. Press, 2006. · Zbl 1104.68042 |
| [10] | Jeh, G. and Widom, J., Scaling Personalized WEB Search, in Proc. 12th Int. Conf. World Wide Web, Budapest, Hungary, 2003, pp. 271–279. |
| [11] | Gantmakher, F.R., Teoriya matrits (Theory of Matrices), Moscow: Nauka, 1988. Translated into English under the title Theory of Matrices, New York: Chelsea, 1959. |
| [12] | Lancaster, P., Theory of Matrices, New York: Academic, 1969. Translated under the title Teoriya matrits, Moscow: Nauka, 1982. |
| [13] | Horn, R. and Johnson, C., Matrix Analysis, New York: Cambridge Univ. Press, 1985. Translated under the title Matrichnyi analiz, Moscow: Mir, 1989. · Zbl 0576.15001 |
| [14] | Bellman, R.E., Introduction to Matrix Analysis, New York: McGraw-Hill, 1960. Translated under the title Vvedenie v teoriyu matrits, Moscow: Nauka, 1969. · Zbl 0124.01001 |
| [15] | Wilkinson, J.H., The Algebraic Eigenvalue Problem, Oxford: Clarendon, 1965. Translated under the title Algebraicheskaya problema sobstvennykh znachenii, Moscow: Nauka, 1970. |
| [16] | Boldi, P., Santini, M., and Vigna, S., PageRank: Functional Dependencies, ACM Trans. Inf. Syst., 2009, vol. 27, no. 4, pp. 1–23. · doi:10.1145/1629096.1629097 |
| [17] | Bryan, K. and Leise, T., The \(25 000 000 000 Eigenvector: The Linear Algebra Behind Google, SIAM Rev., 2006, vol. 48, no. 3, pp. 569--581.\) · Zbl 1115.15007 · doi:10.1137/050623280 |
| [18] | Haveliwala, T. and Kamvar, S., The Second Eigenvalue of the Google Matrix, in Technical Report, Stanford: Stanford Univ., March 2003. |
| [19] | Kolmogorov, A.N., Markov Chains with Countable Number of Possible States, Byull. Mosk. Gos. Univ., Mat. Mekh., 1937, vol. 1, no. 3, pp. 1–16. |
| [20] | Boldi, P. and Vigna, S., The WebGraph Framework I: Compression Techniques, in Proc. 13th Int. Conf. World Wide Web, New York: ACM New York, 2004, pp. 595–601. |
| [21] | Boldi, P., Rosa, M., Santini, M., and Vigna, S., Layered Label Propagation: A MultiResolution Coordinate-Free Ordering for Compressing Social Networks, in Proc. 20th Int. Conf. World Wide Web, Hyderabad, India, 2011, pp. 587–596. |
| [22] | Boldi, P., Santini, M., and Vigna, S., A Large Time-Aware Graph, SIGIR Forum, 2008, vol. 42, no. 2, pp. 33–38. · doi:10.1145/1480506.1480511 |
| [23] | Broder, A., Kumar, R., Maghoul, F., et al., Graph Structure in the Web, Comput. Networks, 2000, vol. 33, no. 1–6, pp. 309–320. · doi:10.1016/S1389-1286(00)00083-9 |
| [24] | Vigna, S., TruRank: Taking PageRank to the Limit, in Special Interest Tracks and Posters of the 14th Int. Conf. on World Wide Web. ACM, Chiba, Japan, 2005, pp. 976–977. |
| [25] | Avrachenkov, K., Litvak, N., and Pham, K., Distribution of PageRank Mass Among Principle Components of the WEB, Algorithms and Models for the Web-Graph, 2007, pp. 16–28. · Zbl 1136.68319 |
| [26] | Gleich, D.F., Constantine, P.G., Flaxman, A.D., and Gunawardana, A., Tracking the Random Surfer: Empirically Measured Teleportation Parameters in PageRank in Proc. 19th Int. Conf. World Wide Web. ACM, Raleigh, North Carolina, USA, 2010, pp. 381–390. |
| [27] | Juditsky, A. and Polyak, B., Robust Eigenvector of a Stochastic Matrix with Application to PageRank, in Proc. 51st Conf. Decision Control, Maui, Hawaii, December 10–13, 2012. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
