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.


Volume 4, Issue 2
Special Issue: Spectral Graph Theory and Mathematical Chemistry with Connection to Computer Science
Autumn 2019
Pages 157-169