A Study of PageRank in Undirected Graphs

Document Type : Original Scientific Paper

Authors

Department of Mathematics, Faculty of Science, Shahid Rajaee Teacher Training University, Tehran, Iran

Abstract

The PageRank (PR) algorithm is the base of Google search engine. In this paper, we study the PageRank sequence for undirected graphs of order six by PR vector. Then, we provide an ordering for graphs by variance of PR vector which it’s variation is proportional with variance of degree sequence. Finally, we introduce a relation between domination number and PR-variance of graphs.

Keywords


[1] C. J. Augeri, On Graph Isomorphism and the PageRank Algorithm, Ph.D. Thesis, Air Force Institute of Technology, USA, 2008.
[2] P. Berkhin, A survey on PageRank computing, Internet Math. 2 (2005) 73–120.
[3] S. Brin and L. Page, Reprint of: The anatomy of a large-scale hypertextual web search engine, Comput. Netw. 56 (2012) 3825–3833.
[4] S. Brown, A PageRank model for player performance assessment in basketball, soccer and hockey, arXiv:1704.00583.
[5] D. F. Gleich, PageRank beyond the web, SIAM Rev. 57 (2015) 321–363.
[6] V. Grolmusz, A note on the PageRank of undirected graphs, Inform. Process. Lett. 115 (2012) 633–634.
[7] B. Jiang, K. kloster, D. F. Gleich and M. Gribskov, AptRank: an adaptive PageRank model for protein function prediction on bi-relational graphs, Bioinformatics 33 (2017) 1829–1836.
[8] V. Kandiah and D. L. Shepelyansky, PageRank model of opinion formation on social networks, Physica A 391 (2012) 5779–5793.
[9] A. N. Langville and C. D. Meyer, Google’s PageRank and Beyond: The Science of Search Engine Rankings, Princeton University Press, Princeton and Oxford, 2005.
[10] V. Lazova and L. Basnarkov, PageRank approach to ranking national football teams, arXiv:1503.01331 (2015).
[11] Ch. Liao, K. Lu, M. Baym, R. Singh and B. Berger, IsoRankn: spectral methods for global alignment of multiple protein networks, Bioinformatics 25 (2009) i253–i258.
[12] B. L. Mooney, L. R. Corrales and A. E. Clark, Molecularnetworks: An integrated graph theoretic and data mining tool to explore solvent organization in molecular simulation, J. Comput. Chem. 33 (2012) 853–860.
[13] J. L. Morrison, R. Breitling, D. J. Higham and D. R. Gilbert, GeneRank: Using search engine technology for the analysis of microarray experiments, BMC Bioinform. DOI: 10.1186/1471-2105-6-233.
[14] N. Mukai, PageRank-based traffic simulation using taxi probe data, Procedia Comput. Sci. 22 (2013) 1156–1163.
[15] F. Pedroche, E. García, M. Romance and R. Criado, Sharp estimates for the personalized multiplex PageRank, J. Comput. Appl. Math. 330 (2018) 1030–1040.
[16] Z. L. Shen, T. Z. Huang, B. Carpentieri, X. Gu and C. Wen, An efficient elimination strategy for solving PageRank problem, Appl. Math. Comput. 298 (2017) 111–122.
[17] C. Wen, T. Z. Huang and Z. L. Shen, A note on the two-step matrix splitting iteration for computing PageRank, J. Comput. Appl. Math. 315 (2017) 87–97.
[18] Ch. Winter, G. Kristiansen, S. Kersting, J. Roy, D. Aust, T. Knöse, P. Rümmele, B. Jahnke, V. Hentrich, F. Rückert, M. Niedergethmann, W. Weichert and M. Bahra, Google goes cancer: Improving outcome prediction for cancer patients by network-based ranking of marker genes, PLOS Comput. Biol. 2 (2012) e1002511.