*Networked* Networks

Network

A network is a Graph, but imagine there are real entities and relationships.

Network Science and Graph Theory

Graph Theory is a subfield of Math while network science is an engineering or interdisciplinary subject. Underneath, they share the same model, graphs or networks. But they focus on different research questions and adopt different approaches. Graph theory focuses on proving the (combinatorial) properties of graphs, while network science focuses on quantifying the structure and dynamics of complex systems on networks, and make predictions. Network science researchers are more interested in large-scale networks with an underlying generative mechanism, motivated by real-life systems such as social, economic, information, physical, and biological systems, calling the use of statistical methods. Graph theory focuses on structures that are more analytically treatable, while network science focuses on those observed in actual networks.

• Basic Concepts
  • Graph
    • Spectral Graph Theory
  • Branching
  • Markov Chain
• Properties
  • Transitivity
  • Centrality
  • Assortativity
  • Conductance
• Random Graph Models
  • Erdos-Renyi Random Graph
  • Configuration Model
  • Chung–Lu Model
  • Stochastic Block Model
  • Random Geometric Graph
  • Watts-Strogatz Model
  • Preferential Attachment
  • Kleinberg Model
• Network Phenomena
• Applications
  • Model: $(\mathcal{V},\mathcal{E},X)$ for various $X$
  • Question: What is the network effect and how does the network structure manifest?
  • Network Propagation: $X=$ (status, dynamics)
  • Network Game: $X=$ (payoff, strategy)
    • Congestion Game
    • Potential Game
    • Fictitious Play
  • Network Learning/Optimization: $X=$ (objective, decision, data)

References

• M. Jackson. Social and Economic Networks. Princeton University Press, 2008.
• R. Durrett. Random graph dynamics. Cambridge University Press, 2007.
• M. Newman. Networks. Oxford University Press, second edition, 2018.
• MIT 6.7260 w/ Prof. Patrick Jaillet, Spring 2026.