Networked Life (CIS 112), Spring 2009 Prof Michael Kearns Homework 1 Issued Feb 4, 2009; Due as hardcopy in class Tue Feb 17; don’t forget to staple and write your name. 1. Consider a network where each vertex corresponds to an English word. There is an edge between two words A and B if either the exact phrase “ A B” or “B A” has more than 1,000 results from Google. Be sure to put quotation marks around all phrases. This ensures that Google only returns page in which the words appear immediately next to each other. You can see the count of how many pages wer e found in the upper‐right corner of the Google search results page. For example, if you search for “own website” (including the quotation marks), there are about 8 million results returned, so there’s an edge between “own” and “website”; “science melodious” has only 2 results and “melodious science” has only 235 results, so there is not an edge between “science” and “melodious”. a. Find the shortest path you can between “epidemic” and “network”. Do not go through “a”, “an”, or “the”. b. Find the shortest path you can between “connector” and “contagion”. Do not go through “a”, “an”, or “the”. c. What parts of speech are the intermediate word(s) you used? What kind of words tend to act as Connectors in this network of words? Now assume that the network is directed, i.e. there is an edge from A to B if the search for “A B” has more than 1,000 results, but there is not necessarily an edge from B to A. Do not go through “a”, “an”, or “the”. In this directed network, find the shortest paths for: d. “network” to “epidemic” e. “epidemic” to “network” f. “connector” to “contagion” g. “contagion” to “connector” Extra credit: Consider the directed network of words in which there is an edge from word A to word B if word B occurs in the dictionary definition of word A. Find a path starting from the word “life” to the word “network” using the online dictionary: http://www.merriam‐webster.com/ 2. Experiment with the Networked Life Disease Demo http://www.cis.upenn.edu/~mkearns/teaching/NetworkedLife/demos/Epidemic.html . Leave the rewiring rate at the default of 0.1 and the random seed at the default of 73. For each infection probability in {0.0, 0.1, 0.2, 0.3,…,1.0}, run three trials of the simulation. For each of those infection probabilities, record the average number of generations your simulations lasted. The number of generations corresponds to how long it takes the disease to die out, and is displayed in the upper right corner. a. Using Excel, your other favorite plotting software, or careful handwriting, create a plot of your data. The infection probability should be on the x‐axis and the average number of generations should be on the y‐axis. b. At what infection probability does the disease last the greatest number of average generations? 3. Let’s say you’re creating a new airline company that will serve six cities: Philadelphia, D.C, Chicago, Denver, San Francisco, and Seattle. You can only afford six routes. Your consultants have two competing network designs. Network A: Network B: Seattle San Francisco ChicagoPhiladelphia Seattle San Francisco ChicagoPhiladelphia DenverDenverD.C. D.C. a. What is the worst‐case diameter (# of hops) in each network? b. What is the average‐case diameter in each network? c. Both of these networks are connected. There are 15 pairs of cities, and a traveler in each city can fly to each other city. If Chicago’s airport is closed, how many of the pairs of cities are still connected in network A? Network B? 4. (2 paragraphs or less) In The Tipping point, Gladwell gives some cases where people applied the ideas of the book to real situations (pages 262‐264). Choose something (a product, a trend, an idea, a practice, etc.) that you would like to see become more widely used or adopted, and describe how the ideas in the book could be applied to make this happen. Which of the “three rules of epidemics” according to Gladwell (the law of the few, the stickiness factor, the power of context) did you use? 5. Remember that the worst‐case diameter of an undirected network is the longest shortest‐path distance between any pair of vertices. a. Draw a connected undirected network of 10 vertices with the largest possible worst‐case diameter. Indicate two vertices that have the maximum shortest path. b. Draw an undirected network consisting of 10 vertices and 9 edges with the smallest possible worst‐case diameter. What is the diameter? c. Draw an undirected network consisting of 10 vertices, each of degree 2, with the smallest possible worst‐case diameter. What is the diameter? 6. In a computer network, every vertex is a computer and every edge is a network connection. The network map or topology (the vertices and the edges connecting them) is stored in every computer. Messages sent on this network contain the name of the destination computer and are passed from vertex to neighboring vertex until they reach their destination. When a computer receives a message destined for another computer, it looks up the location of the destination in the network, computes the shortest path to the destination using the map of the network stored in its memory, and forwards the message to the next vertex on the path. Consider two designs for such a network. The first design uses a small number of hubs connected to each other and most other vertices are connected to one of the hubs. The second design is more distributed with each vertex connected to several other vertices, but there are no vertices of extremely high degree (i.e. there are no hubs). What are the advantages and disadvantages of each design? Consider things such as message routing, cost, susceptibility to failures, congestion, speed of message delivery and anything else you can think of. 7. For this question you will need a Facebook account. Define your immediate neighborhood on Facebook to be yourself plus all the people you are linked to as friends. a. A “clique” in a network is a subset of vertices, every pair of which are directly connected to each other by edges (that is, all pairs of a clique are neighbors). The size of the clique is just the number of vertices in the clique. For example, the network below has