# 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.

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.

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.

_{i}, 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.

#### Requirements

Require directed network.

#### Software

- CentiBiN

http://centibin.ipk-gatersleben.de/ - CentiLib

http://centilib.ipk-gatersleben.de/ - GraphChi

http://graphlab.org/projects/graphchi.html - GraphStream

http://graphstream-project.org/ - graph-tool

http://graph-tool.skewed.de/ - GTNA

https://www.p2p.tu-darmstadt.de/research/gtna/ - igraph

http://igraph.org - JUNG

http://jung.sourceforge.net - NetworKit

https://networkit.iti.kit.edu/ - NodeXL

http://nodexl.codeplex.com/ - Visone

http://visone.info/ - The Brain Connectivity Toolbox (BCT)

http://www.brain-connectivity-toolbox.net/ - SocNetV

http://socnetv.sourceforge.net/

#### 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]