# Theorem on Network Structure¶

If $d(n) \ge (1+\epsilon)log(n)$ some $\epsilon \ge 0$ and $\frac{d(n)}{n} \rightarrow 0$:

then for large n, average path length and diameter of this G(n, p) graph are approximately proportional to $\frac{log(n)}{log(d)}$

$$\frac{AvgDist(n)}{log(n) / log(d(n))} \rightarrow ^p 1$$

same for diameter

# Small Worlds/Six Degrees of Seperation¶

• n = 6.7 billion (world population)

• d = 50(friends, relatives...)

• to get from any individual to any other individual in the world. You actually don't need a lot of hops, you can get there fairly efficiently

# Examine data and diameter¶

• Schools vary in average degree and homophily

• Does diameter match log(n)/log(d)?

# Erdos Numbers¶

• Number of links in co-authorship network to Erdos

• Had 509 co-authors, more than 1400 papers

• 2004 auction of co-authorship with William Tozier (Erdos #=4) on E-Bay, winner paid > 1000\$

# Density: Average Degree¶

HS Friendships (CJP 09) 6.5

Romances (BMS 03) 0.8

Borrowing (BCDJ 12) 3.2

Co-authors (Newman 01, GLM 06)

• Bio 15.5
• Econ 1.7
• Math 3.9
• Physics 9.3