On the relationship between PageRank and automorphisms of a graph

Modjtaba Ghorbani, Matthias Dehmer, Abdullah Lotfi, Najaf Amraei, Abbe Mowshowitz, Frank Emmert-Streib

Research output: Contribution to journalArticleScientificpeer-review

Abstract

PageRank is an algorithm used in Internet search to score the importance of web pages. The aim of this paper is demonstrate some new results concerning the relationship between the concept of PageRank and automorphisms of a graph. In particular, we show that if vertices u and v are similar in a graph G (i.e., there is an automorphism mapping u to v), then u and v have the same PageRank score. More generally, we prove that if the PageRanks of all vertices in G are distinct, then the automorphism group of G consists of the identity alone. Finally, the PageRank entropy measure of several kinds of real-world networks and all trees of orders 10–13 and 22 is investigated.

Original languageEnglish
Pages (from-to)401-417
Number of pages17
JournalInformation Sciences
Volume579
DOIs
Publication statusPublished - 2021
Publication typeA1 Journal article-refereed

Keywords

  • Eigenvalue
  • graph automorphism
  • PageRank
  • web page

Publication forum classification

  • Publication forum level 2

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Theoretical Computer Science
  • Computer Science Applications
  • Information Systems and Management
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'On the relationship between PageRank and automorphisms of a graph'. Together they form a unique fingerprint.

Cite this