8. A number of stories in the press about the structure of the Internet and the...

 

Transcribed Image Text:

8. A number of stories in the press about the structure of the Internet and the Web have focused on some version of the following question: How far apart are typical nodes in these networks? If you read these stories carefully, you find that many of them are confused about the difference between the diameter of a network and the average distance in a network; they often jump back and forth between these concepts as though they're the same thing. As in the text, we say that the distance between two nodes u and v in a graph G= (V, E) is the minimum number of edges in a path joining them; we'll denote this by dist(u, v). We say that the diameter of G is the maximum distance between any pair of nodes; and we'll denote this quantity by diam(G). Let's define a related quantity, which we'll call the average pairwise distance in G (denoted apd(G). We define apd(G) to be the average, over all () sets of two distinct nodes u and v, of the distance between u and v. That is, apd(G) = E dist(u, v) Here's a simple example to convince yourself that there are graphs G for which diam(G) # apd(G). Let G be a graph with three nodes u, v, w, and with the two edges (u, v) and (v, w). Then diam(G) = dist(u, w) = 2, while apd(G) = [dist(u, v) + dist (u, w) + dist(v, w)\/3 = 4/3. Of course, these two numbers aren't all that far apart in the case of this three-node graph, and so it's natural to ask whether there's always a close relation between them. Here's a claim that tries to make this precise. Claim: There exists a positive natural number c so that for all connected graphs G, it is the case that diam(G) <C. apd(G) Decide whether you think the claim is true or false, and give a proof of either the claim or its negation. 8. A number of stories in the press about the structure of the Internet and the Web have focused on some version of the following question: How far apart are typical nodes in these networks? If you read these stories carefully, you find that many of them are confused about the difference between the diameter of a network and the average distance in a network; they often jump back and forth between these concepts as though they're the same thing. As in the text, we say that the distance between two nodes u and v in a graph G= (V, E) is the minimum number of edges in a path joining them; we'll denote this by dist(u, v). We say that the diameter of G is the maximum distance between any pair of nodes; and we'll denote this quantity by diam(G). Let's define a related quantity, which we'll call the average pairwise distance in G (denoted apd(G). We define apd(G) to be the average, over all () sets of two distinct nodes u and v, of the distance between u and v. That is, apd(G) = E dist(u, v) Here's a simple example to convince yourself that there are graphs G for which diam(G) # apd(G). Let G be a graph with three nodes u, v, w, and with the two edges (u, v) and (v, w). Then diam(G) = dist(u, w) = 2, while apd(G) = [dist(u, v) + dist (u, w) + dist(v, w)\/3 = 4/3. Of course, these two numbers aren't all that far apart in the case of this three-node graph, and so it's natural to ask whether there's always a close relation between them. Here's a claim that tries to make this precise. Claim: There exists a positive natural number c so that for all connected graphs G, it is the case that diam(G) <C. apd(G) Decide whether you think the claim is true or false, and give a proof of either the claim or its negation.