In-Class Exercise #1

___________________     ___________________

___________________     ___________________

1. Do the last-names exercise. Look at the list of last names given out in class. For every person you know whose last name appears, give yourself a point. By "know," I mean if you saw them in a store and you approached them, they would know your name and you would know theirs. If the last name "Johnson" appears on the list and you know 3 Johnsons, give yourself 3 points.
2. (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/fall05/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.

3. 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