Dead end

As explained in Graph Algorithms for Data Science

A dead end is a graph node with no outgoing relationships.

In a directed graph, a dead end is a node with no outgoing relationships. In simplified PageRank, it has nowhere to pass its rank, so influence leaks from the network and some or all scores can fall to zero. section 5.4.1

PageRank addresses dead ends through teleportation: instead of always following an outgoing link, a random-surfer model sometimes jumps to another node. The damping factor controls the probability of following links. section 5.4.1

A node with no outgoing links

Node D in a directed network illustrates a dead end. A web page with no links to other pages creates the same problem for a link-following PageRank calculation. section 5.4.1

Figure 5.17 PageRank treats every relationship as a vote of influence.

Use the network diagram to trace how directed relationships pass influence and identify a node that sends none onward. section 5.4.1

How Graph Algorithms for Data Science covers it

How deep it goes

Defines the node structure, explains rank leakage, and names teleportation as the remedy without deriving its full calculation.

Examples

Uses node D and the web-surfer model to illustrate dead ends and their effect on rank flow.

What it assumes

Assumes directed relationships and the basic idea that PageRank passes influence through outgoing links.

What you can do after

Diagnose PageRank rank leakage and recognize why teleportation is required for networks containing dead ends.

How it connects

Connects dead ends to directed relationships, PageRank, teleportation, and the damping factor.

liveBookmanning.com

Read Graph Algorithms for Data Science on liveBook Get the book at manning.com

Related concepts

• teleportationaddressed by · Teleportation is the PageRank mechanism that assigns a probability of jumping from the current node to a randomly selected node instead of following an outgoing relationship.

This explainer was generated by Manning's knowledge graph from the text of Graph Algorithms for Data Science. The section links point to the parts of the book it draws on.