publication . Article . Preprint . 2012

a note on the pagerank of undirected graphs

Vince Grolmusz;
Open Access
  • Published: 09 May 2012 Journal: Information Processing Letters, volume 115, pages 633-634 (issn: 0020-0190, Copyright policy)
  • Publisher: Elsevier BV
The PageRank is a widely used scoring function of networks in general and of the World Wide Web graph in particular. The PageRank is defined for directed graphs, but in some special cases applications for undirected graphs occur. In the literature it is widely - but not exclusively - noted that the PageRank for undirected graphs is proportional to the degrees of the vertices of the graph. We prove that statement for a particular personalization vector in the definition of the PageRank, and we also show that in general, the PageRank of an undirected graph is not exactly proportional to the degree distribution of the graph: our main theorem gives an upper and a lo...
arXiv: Computer Science::Information RetrievalComputer Science::Digital LibrariesComputer Science::Social and Information Networks
ACM Computing Classification System: MathematicsofComputing_DISCRETEMATHEMATICSInformationSystems_INFORMATIONSTORAGEANDRETRIEVAL
free text keywords: Comparability graph, Degree distribution, Graph (abstract data type), Combinatorics, PageRank, law.invention, law, Indifference graph, Directed graph, Discrete mathematics, Block graph, Mathematics, Pancyclic graph, Computer Science - Data Structures and Algorithms, Computer Science - Discrete Mathematics

[3] Sergey Brin and Lawrence Page. The anatomy of a large-scale hypertextual web search engine. COMPUTER NETWORKS AND ISDN SYSTEMS, 30:107-117, 1998.

[4] S. Gershgorin. Uber die abgrenzung der eigenwerte einer matrix. Izv. Akad. Nauk. USSR Otd. Fiz.-Mat. Nauk, 7:749-754, 1931.

[5] C. F. Golub, G. H.; Van Loan. Matrix Computations. Johns Hopkins University Press, 1996.

[6] Gabor Ivan and Vince Grolmusz. When the web meets the cell: using personalized pagerank for analyzing protein interaction networks. Bioinformatics, 27(3):405-407, Feb 2011.

[7] Sepandar Kamvar and Taher Haveliwala. The condition number of the pagerank problem. Technical Report 2003-36, Stanford InfoLab, June 2003.

[8] Laszlo Lovasz. Random walks on graphs: A survey. In Combinatorics, Paul Erdos is Eighty, BOLYAI SOCIETY MATHEMATICAL STUDIES. Janos Bolyai Mathematical Society, 1993.

[9] Nicola Perra and Santo Fortunato. Spectral centrality measures in complex networks. Phys. Rev. E, 78(3):036107, Sep 2008.

[10] Jinghua Wang, Jianyi Liu, and Cong Wang. Keyword extraction based on pagerank. In Zhi-Hua Zhou, Hang Li, and Qiang Yang, editors, Advances in Knowledge Discovery and Data Mining, volume 4426 of Lecture Notes in Computer Science, pages 857-864. Springer Berlin / Heidelberg, 2007. [OpenAIRE]

Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Article . Preprint . 2012

a note on the pagerank of undirected graphs

Vince Grolmusz;