PageRank beyond the Web

David F. Gleich

Source-linked AI summary

PageRank beyond the Web

David F. Gleich

arXiv:1407.5107v1Jul 18, 2014cs.SIcs.CEmath.NAphysics.soc-ph

TL;DR

The paper addresses how a method created for ranking web pages can apply to arbitrary graphs and networks. It develops the common mathematics and surveys constructions and applications across domains. The survey presents PageRank as a broadly useful baseline while emphasizing that construction choices can substantially affect results.

Problem
PageRank originated in web search, but its broader mathematical applicability and diverse domain uses require a unified account of the underlying models and constructions.
Method
The paper develops PageRank and pseudo-PageRank formulations, then surveys their variants, generalizations, and applications across graph-based domains.
Results
PageRank's formal results apply generally to stochastic or substochastic matrices, teleportation distributions, and parameter α, while generalized forms include polynomial combinations of PageRank vectors.
Takeaways & Limitations
PageRank is a useful baseline and modified random walk across applications, but selecting the appropriate construction can make a large difference in result quality.
Takeaways & Limitations
The extent to which PageRank or link-analysis measures contribute to Google's current search ordering is unclear, and one published study found PageRank underperformed in-degree.

Abstract

from arXiv · show

Google's PageRank method was developed to evaluate the importance of web-pages via their link structure. The mathematics of PageRank, however, are entirely general and apply to any graph or network in any domain. Thus, PageRank is now regularly used in bibliometrics, social and information network analysis, and for link prediction and recommendation. It's even used for systems analysis of road networks, as well as biology, chemistry, neuroscience, and physics. We'll see the mathematics and ideas that unite these diverse applications.

1. Google’s PageRank.

PageRank generalizes the random-surfer model from web pages to arbitrary graphs through stochastic transitions and teleportation. Its guaranteed, unique, computationally accessible scores support both global centrality and localized analysis across many domains.

Teleportation models external influence on node importance and ensures that PageRank scores exist uniquely.The teleportation distribution can be more nuanced than uniform random choice.
Simplicity, generality, guaranteed existence, uniqueness, and fast computation motivate PageRank applications beyond web search.The text gives GeneRank as one example of transferring the original motivation and mathematics to biology.
Global PageRank measures node importance in the full graph, whereas localized PageRank measures importance around a selected target set.Global applications typically use near-uniform teleportation, while localized applications use more varied teleportation behavior.
Replacing web-link transitions with a stochastic matrix makes PageRank mathematics applicable beyond the Web.The core formulation uses transition probability α and teleportation probability 1 − α.

2. The mathematics of PageRank.

PageRank is defined by a stochastic or substochastic graph transition system combined with teleportation. Its solutions are unique, its basic iteration converges predictably, and localized formulations concentrate importance near selected regions.

PageRank solves x = αPx + (1 − α)v, where P is column-stochastic, v is a teleportation distribution, and 0 < α < 1.The equivalent linear system is (I − αP)x = (1 − α)v.
The linear-system formulation makes existence, uniqueness, nonnegativity, and normalization immediate through M-matrix properties.The authors describe this formulation as more straightforward and effective than the eigensystem approach.
Starting from x(0) = v gives ||x − x(k)||_1 ≤ 2α^k, while starting from zero yields ||x − x(k)||_1 = α^k.For α in the stated range, at most 3656 iterations suffice for a global 1-norm error of 2^-52 ≈ 10^-16; sparse systems can be computed efficiently.
Pseudo-PageRank vectors always exist uniquely and become ordinary PageRank vectors after renormalization and a stochastic correction.The distinction between the systems is entirely a matter of solution normalization.
Localized PageRank places large values in an isolated region surrounding teleportation nodes and small values elsewhere.This behavior is intended to identify nodes near selected targets and distant from the rest of a graph.
Applications use PageRank either to assess importance across an entire graph or relative to a small subset of objects.Both cases require constructing a stochastic or substochastic matrix from the input graph.

3. PageRank constructions.

PageRank constructions adapt the transition matrix and teleportation behavior to graph structure and application goals. Variants address weighted, reverse, dangling-node, boundary-constrained, preferential, and undirected settings.

The standard construction uses a random walk derived from the adjacency matrix, with dangling nodes requiring a substochastic correction.The matrix is formed as P̄ = A^T D+ and the correction vector indicates dangling nodes.
Strongly preferential PageRank uses P = P̄ + vc^T, whereas weakly preferential PageRank uses P = P̄ + uc^T with u = e/n.These choices determine how the walk behaves at dangling nodes.
Reverse PageRank transposes the graph so the random walk follows in-links and helps determine why a particular node is important.It reverses each edge direction and is distinct from identifying which nodes are important through ordinary PageRank.
Dirichlet PageRank fixes boundary values for a subset of nodes and reduces the remaining problem to pseudo-PageRank.For boundary set S, the fixed values satisfy x_i = b_i for i ∈ S.
Weighted PageRank makes transition probabilities depend on edge or node weights rather than uniform neighbor choice.The weighting may derive from out-degree, in-degree, total degree, or an external source.
On undirected graphs, the ordinary random walk is reversible with stationary distribution x = De/(e^T d), but PageRank with α < 1 generally is not.Carefully chosen teleportation vectors can nonetheless reveal small isolated regions.

4. PageRank applications.

The surveyed constructions and applications show PageRank being adapted across diverse graph-based domains. The section emphasizes breadth rather than exhaustive detail, spanning systems, information resources, and scientific networks.

PageRank constructions include random-walk, strongly preferential, and weakly preferential variants, with different transition treatments for dangling nodes.Figure 3.2 illustrates these constructions on a directed graph using teleportation vectors and correction terms.
The survey covers applications in databases and knowledge systems, engineered systems, mathematical systems, recommender systems, and the Web.The section is intended to survey application diversity rather than provide full details of every use.
PageRank can assess hydrogen-bond network changes in water and identify molecular outliers whose scores deviate from degree-based expectations.The cited chemistry application uses uniform teleportation with α = 0.85.

4.1. PageRank in chemistry.

PageRank applications in biology use network structure together with experimental or functional information to identify related genes and proteins. These localized approaches also extend to cross-species network matching and brain-connectome analysis.

GeneRank: GeneRank uses noisy microarray results as teleportation information over a gene-relationship network to identify related genes not themselves marked experimentally.Its experimentally best α ranges between 0.75 and 0.85.
Disease-related genes: PageRank and BlockRank use 34 disease-associated proteins as teleportation information to find genes related to type 2 diabetes.The reported teleportation parameter is α = 0.92.
Cancer prognosis: Seven genes for pancreatic ductal adenocarcinoma better predicted patient survival than existing tools and were validated in a clinical trial.The study used α = 0.3, selected through cross-validation, with teleportation based on gene-expression and survival-time correlation.
ProteinRank: ProteinRank localizes PageRank around proteins with a curated functional annotation to find unlabeled proteins that may share that function.It uses an undirected protein-interaction network and annotation-specific teleportation.
IsoRank: IsoRank formulates cross-network vertex matching as a PageRank problem on the tensor-product Markov chain Q ⊗ P.The intended application is matching protein-interaction networks across species to infer possible human-protein functions.
Connectomes: PageRank has also been used with observed brain-activity correlations to evaluate the importance of brain regions in connectome-related networks.The cited application studies brain-network properties using correlations of brain activity.

4.3. PageRank in neuroscience.

The section presents PageRank across neuroscience and engineered networks, including connectome analysis, anomaly diagnosis, software dependencies, and road or urban-space modeling. It also emphasizes that model choice can determine whether PageRank is useful.

Neuroscience: PageRank combined with community detection and known brain regions was used to identify brain-structure changes correlated with age across 1000 individuals.The underlying graph retained functional-MRI correlations as binary or correlation weights after weak edges were removed.
Neuroscience: PageRank performed poorly for recovering hierarchical order in C. Elegans neural networks compared with Katz score and communicability.The authors suggest the flow modeled by PageRank may have been mismatched to the application.
Engineered systems: MonitorRank applies personalized PageRank to an anomaly-dependent weighted, augmented call graph to rank systems likely contributing to detected issues.The localized scores guide administrators or developers during log searching and debugging.
Engineered systems: In Linux-kernel call graphs, PageRank and reverse PageRank provide centrality scores for a system containing 15.8 million lines of code and around 300,000 functions.The kernel has evolved through contributions from nearly 2000 individuals over 20 years.
Roads and urban spaces: Weighted PageRank with α = 1 best predicted human mobility in a London urban-space network, accounting for up to 60% of observed movement.The network contains up to 20,000 nodes and 100,000 links; the authors hypothesize α < 1 may generalize better over longer timespans.

4.5. PageRank in mathematical systems.

PageRank extends to mathematical systems by ranking states in discretized dynamical networks and by ranking teams in sports winner networks. These applications use transition structure to expose transient behavior or relative team importance.

Dynamical systems: A symbolic image discretizes a dynamical system into cells and represents transitions among those cells as a directed graph.The construction begins with a discrete-time map on a compact state space covered by cells.
Dynamical systems: PageRank on the resulting weighted graph produces visualizations of transient behavior, with α = 0.85 inhibiting convergence to stable attractors.The graph uses 1000 random samples from each cell and has N^2 nodes with at most N^2s edges.
Sports: Sports winner networks represent teams as nodes and direct edges toward teams that won, optionally weighting edges by winning margin.This construction supports stochastic-matrix and eigenvector-based ranking methods.
Dynamical systems: For the Chirikov typical map, standard PageRank highlights attractors and transient-manifold contours, while reverse PageRank highlights regions exited quickly.The figure compares standard, weighted, and reverse vectors with α = 0.9 and uniform teleportation; vectors are cube-root scaled for visualization.
Sports: Govan et al. used centrality PageRank with uniform teleportation and α = 0.85 to rank football teams.Their random-fan interpretation follows a team until it loses, then periodically restarts with an arbitrary team.

4.7. PageRank in literature: BookRank.

PageRank supports literary analysis by ranking books, story paths, and books associated with user-generated tags, while related bibliometric applications rank scholarly entities. These uses adapt graph construction and teleportation to the information being studied.

Books and authors: PageRank applied to a topic-model-based distance graph led Jockers to argue that Jane Austen and Walter Scott were the most original nineteenth-century authors.The analysis combined PageRank centrality with other graph-analytic tools.
Hypertextual literature: In hypertextual literature, PageRank and a derived ranking system provided useful information about story properties.The experiments used uniform teleportation and deterministically returned from terminal storylets to the book’s start.
BookRank: BookRank uses books and user-curated tags from social cataloging sites to represent literary content as a network for ranking.The approach builds on shared tagging information about books.
Bibliometrics: Bibliometric PageRank applications commonly rank important journals, papers, and authors in citation networks.The tradition extends from Garfield’s journal-citation network through later PageRank analogues.
Bibliometrics: TimedPageRank and CiteRank use paper age in edge weighting or teleportation to produce temporally relevant rankings that reduce older papers’ citation advantage.TimedPageRank assigns recent papers larger age weights, while CiteRank gives recent papers larger teleportation values.
Bibliometrics: Chen et al. recommend α = 0.5 for citation analysis and identify papers whose PageRank exceeds expectations from their citation counts.These papers are described as hidden gems.
Bibliometrics: Author-citation networks combine bipartite author-paper structure with directed paper citations, rewarding authors with many highly cited papers.The studied graphs contain a few hundred thousand authors and author-author citations.

4.9. PageRank in databases and knowledge information systems: PopRank, FactRank, ObjectRank, FolkRank.

PageRank supports both centrality and localized analyses in knowledge information systems, where it ranks entities, predicts missing information, and supports specialized search and reasoning tasks.

Centrality scores: PopRank combines web-based importance with object relationships to measure popularity, while FactRank evaluates the importance and accuracy of fact networks.PopRank uses web-importance as a teleportation vector; FactRank operates on facts extracted from large web crawls.
Localized scores: Localized PageRank supports semi-supervised learning and image-caption inference by propagating information through graph relationships from limited examples or query regions.Applications include handwritten-digit identification and caption inference over image, region, and term graphs.
Database queries: ObjectRank adapts PageRank to database queries by weighting forward and backward links differently when graph relationships lack a natural direction.The approach uses α = 0.85 on graphs with a few million edges.
Folksonomy search: FolkRank scores objects, users, and tags relative to a topic using localized PageRank on an undirected, tripartite weighted network.The scores are based on localized PageRank vectors and are intended to reveal important objects and related tags.
Semantic relatedness: Localized PageRank also measures semantic relatedness between Open Directory Project categories using the cosine of their localized PageRank vectors.Reverse PageRank is used so edges run from child to parent, and the authors report evidence that the measure is useful.
Logic programming: Random teleportation restricts logic-programming search to short and likely proofs, addressing exponential growth in potential rule combinations.The teleportation mechanism controls expansion of the proof-search procedure.

4.10. PageRank in recommender systems: ItemRank.

PageRank-related methods support recommendation and prediction by propagating user or item information through graphs, while localized PageRank also serves broader link-prediction tasks.

ItemRank: ItemRank solves a PageRank problem over item relationships derived from user ratings to score recommendations for users.Each column of S represents recommendations for a user, and Sij proxies the user’s interest in item i.
Link prediction: PageRank scores were weaker link-prediction predictors than Katz’s matrix in one co-authorship evaluation, while later Facebook work learned transition weights for higher prediction.Katz achieved one of the best results with α = 0.0005; PageRank was evaluated with α between 0.5 and 0.99.

4.11. PageRank in social networks: BuddyRank, TwitterRank.

In social networks, PageRank is used to rank people, identify influential individuals, and localize importance toward topical or network-specific interests.

BuddyRank and social ranking: PageRank has been used to rank individuals in Twitter and to characterize properties of the Twitter social network.Earlier large-scale social-network use included BuddyRank, based on AOL Instant Messenger contact lists collected by BuddyZoo.
Influence: Reverse PageRank outperforms out-degree as a heuristic for identifying influential individuals in web-blog and LiveJournal networks.The reverse formulation models the origins of influence rather than standard authority accumulation.
Influence: TwitterRank uses teleportation vectors and topic-specific transition probabilities to localize PageRank for finding topical authorities.This extends PageRank-based influence analysis to topic-specific social-network settings.

4.12. PageRank in the web, redux: HostRank, DirRank, TrustRank, BadRank, VisualRank.

Beyond page ranking, PageRank variants analyze web structure at host or directory levels, combat spam, assess hub similarity, and select representative images.

PageRank on the web: The continued role of PageRank in Google’s search ordering is unclear because Google uses a continuously evolving basket of ranking metrics.Published evidence also found PageRank underperformed in-degree in one large-scale search-engine study.
PageRank on the web: Google has publicly described using PageRank-related information for crawling behavior and adapting the method to handle rel=nofollow links.The adaptation used a full substochastic matrix for the PageRank vector.
Trust, reputation, and spam: PageRank and reverse PageRank provide measures of page-to-hub similarity and page spaminess through variants including TrustRank and BadRank.These uses evaluate web pages beyond their ordinary authority scores.
Coarse PageRank: HostRank aggregates web links at the hostname level, modeling silent within-host transitions before following a random link.All links to and from a hostname are treated as equivalent in this construction.
Trust, reputation, and spam: TrustRank and BadRank apply link analysis to combat spam sites that seek search visibility without providing new information.These methods emerged as the commercial value of websites increased the incentive to create spam.
Image search: VisualRank computes PageRank on a weighted image-similarity graph to identify canonical images for visual summaries of image-search results.The graphs contain around 1000 nodes and are symmetric and weighted.

5. PageRank generalizations.

PageRank generalizations extend the canonical model through alternative damping, teleportation, and graph constructions while preserving useful connections to diffusion, spectral analysis, and ranking systems. These variants support localized structure, limiting analyses, and applications beyond standard PageRank.

Diffusions, damped sums, & heat kernels: Generalized damped PageRank replaces geometric weights with nonnegative sequences γ_k, reducing to standard PageRank when γ_k = α^k.The sequence weights different path lengths in the diffusion interpretation.
Diffusions, damped sums, & heat kernels: Randomizing α produces an expected PageRank that integrates over path-following behaviors and yields a family of γ_k sequences.These generalized vectors can be evaluated as polynomial combinations of PageRank vectors.
PageRank limits and pseudo-PageRank: Pseudo-PageRank retains existence and uniqueness, but its limit as α → 1 can diverge or vanish depending on the support of f.Specifically, y → ∞ unless the non-zero support of f lies outside a recurrent class, where y → 0.
Over-teleportation, negative teleportation, & the Fiedler vector: Allowing negative teleportation entries adds no modeling power for symmetric adjacency matrices, although it supports the over-teleportation connection.The result is specific to the symmetric setting described in the paper.
Over-teleportation, negative teleportation, & the Fiedler vector: Over-teleportation connects generalized PageRank continuously to the Fiedler vector on suitable connected, undirected graphs.The construction uses α > 1 and a particular generalized PageRank formulation, with the limiting value equal to the Fiedler vector.
Censored node constructions: Censored-node constructions express non-uniform teleportation as implicit PageRank and relate Colley sports rankings to generalized pseudo-PageRank.The Colley formulation also permits use of fast PageRank solvers for those systems.

6. Discussion & a positive outlook on PageRank’s wide usage.

PageRank has expanded from web-page ranking into diverse graph applications, while its small-scale use cases often permit simple, rapidly convergent iterations. The discussion also emphasizes careful choice of PageRank construction and recognizes related models outside the paper’s framework.

PageRank is used across applications beyond web search, including social networks, similarity, food webs, and opinion dynamics.The paper also notes that several PageRank-like models fall outside its specific framework.
Simple iterations generally converge quickly for the modest-sized PageRank problems common in applications.For α values below 0.99, fewer than 2000 iterations can suffice for convergence to machine precision.
Algorithmic innovations remain relevant, but should be developed for the small-scale application regime where simple iterations already suffice.PerturbationRank is one example of computing additional rankings from perturbations to an existing PageRank vector.
Related methods adapt PageRank-like ideas to continuous-time browsing, voting, node similarity, and nutrient flow in food webs.These adaptations change the modeled dynamics or transition structure to fit the application.
PageRank’s success over extremely simple baselines suggests that its modified random walk is a generally useful alternative resembling regularization.The paper advises selecting the PageRank construction carefully because weighted, reverse, and Dirichlet variants can produce substantially different results.