Sparse Networks: Constant Average Degree

Sparse Network Formula:
Edge Density: p = c/n (where c = constant average degree)
Total Edges: m = cn/2
For c = 2: m = n (linear growth vs quadratic in dense networks)
Key Insight: In sparse networks, edge density decreases as 1/n, but average degree remains constant. This represents many real-world networks where each node maintains roughly the same number of connections regardless of network size (e.g., social networks, biological networks).

Dense Networks (Previous Example)

  • Constant density: p = 0.5
  • Edge growth: m ∝ n²
  • Average degree: grows with n
  • Example: Complete or near-complete graphs

Sparse Networks (Current Example)

  • Decreasing density: p = c/n
  • Edge growth: m = cn/2 (linear)
  • Average degree: constant (c = 2)
  • Example: Social networks, neural networks

Dense vs Sparse Network Comparison

Network Type n=4 n=6 n=8 n=10 n=20 n=50 n=100
Dense (p=0.5)
Edges		 3 8 14 23 95 613 2475
Sparse (c=2)
Edges		 4 6 8 10 20 50 100
Density Ratio
Dense/Sparse		 0.75 1.33 1.75 2.30 4.75 12.26 24.75