PageRank

PageRank operates on a probabilistic model of user behavior. It imagines a user randomly clicking links indefinitely, but occasionally getting bored and jumping to a random page. The damping factor (d), typically set to 0.85, represents the probability that the surfer continues clicking links rather than teleporting. This prevents rank sinks—pages that accumulate rank without linking out—from gaming the system. The steady-state probability of landing on any given page becomes its PageRank score.

PageRank is computed by solving the dominant eigenvector of a modified adjacency matrix. The algorithm initializes all pages with equal rank, then iteratively redistributes rank through outgoing links until convergence.

• Power iteration method: Repeatedly multiply the rank vector by the link matrix
• Convergence threshold: Typically when rank changes drop below 10^-6
• Scalability: Originally computed on the entire web graph, now requires distributed processing frameworks like Pregel or Apache Giraph

Unlike simple citation counting, PageRank normalizes the value of each vote by the out-degree of the linking page. A link from a page with 5 outgoing links passes 1/5 of its rank, while a link from a page with 100 outgoing links passes only 1/100. This prevents link farming where pages artificially inflate their outbound links to dilute value. High-PageRank pages with few outbound links confer the most authority.

Dangling nodes—pages with no outgoing links such as PDFs, images, or orphaned documents—present a mathematical problem. They absorb rank without redistributing it, causing total rank to leak from the system. Solutions include:

• Teleportation: Dangling nodes are treated as linking to all pages equally
• Removal: Temporarily removing dangling nodes, computing rank on the remaining graph, then reinserting them
• Back-propagation: Distributing the accumulated rank of dangling nodes back into the graph

A variant that biases the teleportation vector toward a specific set of seed pages rather than the uniform distribution. This enables topic-sensitive ranking where the importance of a page is relative to a user's interests. Applications include:

• Recommendation systems: Biasing toward user's previously liked items
• Local graph clustering: Finding communities around seed nodes
• Trust propagation: Biasing toward verified authoritative sources to combat spam

The power iteration method converges at a rate determined by the second eigenvalue of the transition matrix. With damping factor d=0.85, approximately 50-100 iterations achieve practical convergence for web-scale graphs.

• Time complexity: O(|E|) per iteration, where |E| is the number of edges
• Memory complexity: O(|V|) for storing the rank vector, where |V| is vertices
• Distributed implementation: Graph is partitioned across machines; each iteration requires a MapReduce shuffle phase to aggregate incoming rank contributions

A link analysis technique designed to combat web spam by propagating trust from a manually selected seed set of highly reputable pages. Unlike PageRank, which treats all links as votes, TrustRank assumes that reputable pages rarely link to spam. The algorithm iteratively distributes a trust score through outbound links, decaying the score with each hop. Pages that receive little or no trust are flagged as spam. This method is particularly effective against link farms and comment spam, where malicious actors artificially inflate PageRank scores.

A predictive search engine ranking score developed by SEO software companies that estimates how likely a domain is to rank on search engine result pages. It aggregates multiple link metrics, including linking root domains, total backlinks, and MozRank (a PageRank derivative). The score is calculated using a machine learning model trained against actual Google rankings. Key factors include:

• Quantity and quality of referring domains
• Link profile growth patterns
• Spam score of linking sites Unlike PageRank, which is page-level, Domain Authority is a domain-level metric.

A semantic similarity measure that identifies related documents by determining how frequently they are cited together by the same third-party sources. If Document A and Document B are both frequently cited by Document C, they are considered topically related, even if they do not link to each other. This technique extends beyond PageRank's direct link graph to capture implicit semantic relationships. Co-citation is foundational to modern bibliographic coupling and is used in academic search engines and patent analysis to map the intellectual structure of a field.

A scoring metric that rewards documents for providing unique, novel information beyond what the user has already seen in previously ranked results. In the context of authority scoring, Information Gain acts as a counterbalance to PageRank's popularity bias. A highly linked page that merely repeats information found in other top-ranked pages may be penalized. The metric is calculated by comparing the conditional probability of content given the query against the probability of that content given previously seen documents. This ensures diversity in search results.

A mathematical model that gradually reduces the relevance score of a document over time to reflect the decreasing value of outdated information. PageRank is inherently static and does not account for content freshness. Temporal decay functions address this by applying a time-based weighting factor to link-based authority scores. Common implementations include:

• Exponential decay: score * e^(-λt)
• Inverse time weighting: score / (1 + k * age)
• Gaussian decay for event-driven content This is critical for queries where user intent demands recent information.

A network structure where nodes represent academic papers, patents, or articles, and directed edges represent citation links between them. This is the academic analog of the web graph that PageRank operates on. Citation graphs are used to calculate journal impact factors, author h-index scores, and patent prior art relevance. Unlike the web graph, citation edges are typically unidirectional (newer works cite older works) and carry higher semantic weight, as citations are deliberate acts of intellectual acknowledgment rather than navigational conveniences.