PageRank


Definition

PageRank is an eigenvector-based algorithm. The score for a given vertex may be thought of as the fraction of time spent 'visiting' that vertex (measured over all time) in a random walk over the vertices (following outgoing edges from each vertex). PageRank modifies this random walk by adding to the model a probability (specified as 'alpha' in the constructor) of jumping to any vertex. If alpha is 0, this is equivalent to the eigenvector centrality algorithm; if alpha is 1, all vertices will receive the same score (1/|V|). Thus, alpha acts as a sort of score smoothing parameter.
Link analysis that scores relatively importance of web pages in a web network.
PageRank is a link analysis algorithm that scores the relative importance of Web pages in a hyperlinked Web network, such as the WWW, using eigenvector analysis. The PageRank of a Web page is defined recursively; a page has a high importance if it has a large number of incoming links from highly important Web pages. PageRank also can be viewed as a probability distribution of the likelihood that a random surfer will arrive at any particular page at certain time.
Page Rank
where ti, i = 1, . . . n, are the Web pages that point to page v, C(v) is the number of links originated at page v, and d is the damping factor (d ∈ [0, 1]).
The PageRank corresponds to the principal eigenvector of the normalized adjacent matrix of the Web. Therefore, PageRank can be viewed as a variant of eigenvector centrality.
Since PageRank examines a single random walk on the entire WWW, the ranking of Web pages in Google is independent of the search query (a global ranking), and no distinction is made between hubs and authorities.

See:
Lv, L., Zhang, K., Zhang, T., Bardou, D., Zhang, J. and Cai, Y., 2019. PageRank centrality for temporal networks. Physics Letters A, 383(12), pp.1215-1222.

Requirements

Require directed network.

References

  • BRIN, S. & PAGE, L. 1998. The anatomy of a large-scale hypertextual Web search engine. Computer networks and ISDN systems, 30, 107-117.
  • CSARDI, G. & NEPUSZ, T. 2006. The igraph software package for complex network research. InterJournal, Complex Systems, 1695. [http://igraph.org]
  • JUNG, the Java Universal Network/Graph Framework [http://jung.sourceforge.net]