1. Introduction

1. What do the authors claim are the essential properties of "scale-free" networks?
2. What is important about the authors proposed "scale-free" metric?

2. Background

1. The CCDF is given by 1-F(x) in this section. How does this compare with Neuman's presentation of the CCDF? What type of statistical distributions fit the power law exponents between zero and two for alpha?
2. Be able to explain the rank size power law. (Try an example.)
3. What is the statistical mechanics explanation for understanding complexity in networks? Compare this approach to the non-stochastic explanation of scaling. (section 2.1.1)
4. What do the authors claim is a necessary condition for many scale-free network properties? (section 2.1.2)
5. What are the invariant properties of Gaussian (normal) distributions? How is the central limit theorem linked to these properties? (section 2.1.4)
6. What is the high variance analog to the central limit theorem? How is this helpful? (section 2.1.4)
7. If highly variable node degrees are common in real systems, is power law information useful? (section 2.1.4)
8. Be able to discuss figure 3. (section 2.2)
9. What is a network motif? How are motifs connected to self-similarity? (section 2.3.3)

3. The Existing SF Story

1. Be able to discuss the 6 properties/claims listed for SF graphs.
2. What do the authors say about emergent properties associated with graphs whose degree distributions are scaling? (section 3.2)
3. What key property is associated with Internet router networks? (section 3.3.1) Why is this contradictory?

4. A Structural Approach

1. How does the rearrangement inequality show that s(g) is maximized with high-degree nodes are adjacent to other high-degree nodes?
2. Given a fixed degree distribution D, what is important about s_max(D) and s_min(D)? Which graphs are more prevalent? (section 4.1.1)
3. What connection do the authors make between s_max and similarity?
4. s_max can be constructed greedily for trees. Construct s_max for the two graphs on the exam. D_1 = (2,3,3,4,4,4) for problem 3. D_2 = (1,1,1,1,2,2,3,3,4). (section 4.1.2)
5. What explanation is given for the claim that preferential attachment generates high s(g) graphs? (section 4.5)
6. What do the authors claim are properties of high s(g) graphs? (section 4.5)
7. The authors claim greater diversity (w.r.t. s(g)) for graphs (fixed D) with low s(g). Why is this important?

5. A Probabilistic Approach

1. The GRG model (Fan Chung 2003) is the one I mentioned briefly in class in comparison to the configuration model. How is s(g)/s_max used w.r.t. to the likelihood of a graph drawn from all graphs with a fixed degree distribution? (section 5.1)
2. Figure 9 is another attempt to convince us that high s(g) graphs are what we get when we sample at random from G(D). (section 5.2)
3. Make sure you understand the connection between s(g) and r(g). (equation 14)
4. For what "background" set of graphs is r(g) defined? (section 5.4)

SF Graphs and the Internet Revisited

1. How do the authors explain why they think that the internet structure may not be scaling? (section 6.1)
2. What is the new definition of "scale-free"? What does "scale-rich" mean? (section 6.2)
3. Compare and contrast "scale-free" networks with "HOT" networks. (section 6.5)