The Random Surfer Gets Trapped:

The Problem of Dangling Nodes and Cycles

This section is intended to practice the concepts covered in the previous pages by answering a variety of short questions. The APPLET may be a helpful resource (you will need the most recent version of the Java Console installed and enabled to be able to view this Java applet http://java.com/en/download/index.jsp).

Question 1:

Let's look at our current algorithm closer.   Under our current model, there are times when the random surfer runs into problems. He likes to surf along hyperlinks to go from webpage to webpage, but there are situations where he can get stuck at one page or a group of pages. This will happen when the surfer reaches what is known as a "dangling node."

Experiment with the APPLET and try to create a graph in which the random surfer gets stuck in one page from which he can never leave. (There are several, 5 to be exact.)

 

Segment 3: "The Dangling Node" from "The Random Surfer" by Tim Chartier on Vimeo.

Question 2:

In the graph below, which of the five nodes is the dangling node?

 

Question 3:

Is it possible for a graph to have more than one dangling node?

When the random surfer gets stuck in a group of nodes and continues to bounce around and around among pages in this group, then the graph is said to have a cycle. Graphically, this means that there is a group of nodes that are interconnected, that is, connected with each other, yet have no connections to nodes outside the group. It’s like an insulated clique of people who refuse to make connections to outsiders. Here is an example of a graph with a two-node cycle (nodes 1 and 2).

Question 4: Critical Thinking

Do you have a Facebook account? If yes, try this challenge. Start at a friend’s page. Then skip to another friend’s page by just clicking on other friends in the Mutual Friends box. Do you have different groups of friends? For instance, school friends, work friends, or church friends. Do you get stuck in a cycle of those friends and have problems getting out? Also, do you maybe have a friend in which you have no friends in common? What happens if you start at his/her page? Can you think of other examples of dangling nodes and cycles on the Facebook graph?

 

Segment 4: "Cycles " from "The Random Surfer" by Tim Chartier on Vimeo.

Once you feel comfortable with the material proceed to The Solution of Teleportation.

ANSWERS