Prelab 9: Networks

Reading

1. David Easley and Jon Kleinberg, Graph Theory handout from Cornell University Information Science 204: Networks - Spring 2007, January 24, 2007. (on Blackboard in the Course Documents/Networks folder)
2. Lecture slides on networks

Part 1: Networks

1. (From Michael Kearns) In this question, we consider the World Wide Web as a graph, with HTML Web pages being vertices and hyperlinks being edges. For this problem, we'll consider only HTML Web pages (not Flash files or PDFs or anything else) as vertices and only plain, static hyperlinks (not Google's search facility or any other fancy way of linking) as edges. If a page A has one or more hyperlinks to page B, we consider that there is a single directed edge from page A to page B; it does not matter whether there is one link or ten. We'll ignore any links from a page to itself, and any links that lead to or from things other than HTML Web pages.

   1. Is the graph of the Web, as described above:

      • complete?

      • acyclic?

      • of uniform out-degree distribution, over the entire range of possible out-degrees?

   2. One page on the Web, and one node in our graph, is the course page itself: http://www.cs.duke.edu/courses/cps001/spring07/index.html

      • What is this node's out-degree?

      • What is its in-degree?

      • How did you determine its out-degree and in-degree?

   3. You will now do a search on the Web graph, beginning at the node above. You are to only use local information (the HTML page you are examining at each step) to determine where to go next. Do no use Google or any other Web resource to direct your search: simply pick the link that seems most likely to take you to your destination, while looking only at the current page. Your target is the official Web site of Star Wars, the movie.

      For ten steps, or until you reach starwars.com, if you reach the site in fewer than ten steps, record all of the following information:

      • The URL of the link you followed.
      • A phrase or sentence explaining why you followed that link.

      Note that you do not need to reach starwars.com to get full credit for this part of the problem. You just need to record all the links that you followed and why you followed them. If you hit a dead end of any sort or seem to be on an unhelpful path, you can backtrack and start from an earlier point on your path; just note clearly that you are doing this.

2. For each of the following general categories of networks discussed in class, give a real-world example of such a network. Your example should be different than one given in class.

   For each of your networks you should specify

   • What are the vertices (nodes)?
   • What are the edges (links)?
   • How is the network formed? Is it decentralized or centralized? Is the communication or interaction local or global?
   • What is the network's topology? For example, is it connected? What is its size? What is the degree distribution?
   1. Social networks

   2. Computer network

   3. Content networks

   4. Business and economic networks

   5. Biological networks

Part 2: Facebook exercise

Consider Facebook, an online directory that connects people.

Lets consider the connection by friends. On Facebook, a friend is someone who mutually agrees with you that the two of you are friends. You are listed as one of their friends and they are listed as one of your friends.

Suppose we draw a graph in which each node in the graph is a person at Duke and each edge in the graph is a connection between two people at Duke who are friends (determined by Facebook). If we could collect the data of everyone's list of friends at Duke, we could show a large graph of all the Duke friend connections. Our goal is to determine who is in the center of the graph, and to determine if the center person has the most friends or not.

We will work with a much smaller graph to study this problem. Consider the following eight people and their friend connections.

A: Number of friends

In a graph the degree of a node is the number of edges attached to the node. When the graph represents the connections between friends, then the degree is the same as the number of friends.

For each person in the graph, determine their number of friends.

1. Arin
2. Betsy
3. Chris
4. Daoxin
5. Erich
6. Fran
7. Geoff
8. Hannah

B: Shortest Path Distance

The shortest path distance between two nodes in a graph is the fewest number of edges one must walk along to get from one node to the next. For example, to get from Chris to Erich, there are several paths. One path goes through Betsy and then Geoff and is of length 3 (3 edges are traversed: Chris to Betsy, Betsy to Geoff, Geoff to Erich). There is a shorter path of length 2 through Fran (Chris to Fran, Fran to Erich). There are many more paths.

List the shortest path distance between every pair of names. The shortest path between a name and itself is zero and has been labeled for you.

C: Algorithm for shortest path

Write an algorithm to find the shortest path from one node in a graph to all the other nodes. Assume there exists a path from that node to all the other nodes in the graph.

D: Center of a graph

For each node in the graph above, calculate the sum of the shortest distances to all the other nodes in the graph. The node with the smallest sum is the center of the graph.

1. Arin
2. Betsy
3. Chris
4. Daoxin
5. Erich
6. Fran
7. Geoff
8. Hannah

Which node is the center of the graph?

Does the center of the graph have the most friends (i.e. more than everybody else)?

E: Does Center of a graph mean the most friends?

Is the center of the graph always the person with the most friends? Draw a graph in which the center of the graph does not have the most friends. Your graph should have fewer than 12 nodes.

F: Diameter

The diameter of a graph is the longest shortest path between any two vertices. In other words, the diameter of a graph is the greatest distance between any two vertices. The diameter gives a measure of the breadth of a network. For example, the following paper discusses the diameter of the World Wide Web.

Réka Albert, Hawoong Jeong and Albert-László Barabási, Diameter of the World Wide Web, Nature 401, 130 (1999)

What is the diameter of the graph above?