September 24, 2007
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.
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.
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.
| Names: | Arin | Betsy | Chris | Daoxin | Erich | Fran | Geoff | Hannah |
|---|---|---|---|---|---|---|---|---|
| Arin | .0 | . | . | . | . | . | . | . |
| Betsy | . | .0 | . | . | . | . | . | . |
| Chris | . | . | .0 | . | . | . | . | . |
| Daoxin | . | . | . | .0 | . | . | . | . |
| Erich | . | . | . | . | .0 | . | . | . |
| Fran | . | . | . | . | . | .0 | . | . |
| Geoff | . | . | . | . | . | . | .0 | . |
| Hannah | . | . | . | . | . | . | . | .0 |
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.
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.
Which node is the center of the graph?
Does the center of the graph have the most friends?
Is the center of the graph always the person with the most friends?
Find a graph in which the center of the graph does not have
the most friends. Your graph should have fewer than 12 nodes.
There are over six thousand students at Duke. We would like to try to guess what a plotted graph looks like with respect to the number of friends people have at Duke on facebook.
Sketch what you think the following graph should look like. This is an x-y graph where the y-axis runs up and down and represents the number of friends a person has and the x-axis runs left-right and is the rank by # of friends.
The y-axis values should be 1000 or more friends, 800-1000 friends, 600-800 friends, 400-600 friends, 200-400 friends, and 0-200 friends. The x-axis should be the number of people with y-many friends. For example, if you think there are 50 people with 400-600 friends, you would put a point at (50,400-600).