Everything is connected - from your friends, to everyone at CMU, to economic markets, disease outbreaks, and global societies. Relationships and flows of information among people and organizations form complex systems that are the fundamental structures governing our world, yet defy easy understanding. To analyze these interconnected systems we must turn to network science. This course covers the mathematical and graph theoretical foundations of network science, as well as theories and algorithms for analyzing and visualizing structures and dynamics of networked systems. Topics covered in this class include: centrality metrics, community detection, diffusion processes, scale-free and small-world networks, social media analytics, and network visualization. A special emphasis is on algorithmic challenges and solutions in the context of big data networks. Students will engage in hands-on projects learning network science, solidifying their mathematical and graph theory knowledge and learning how to apply it to a range of real world problems.

This course is open to students in all majors who have earned a C or better in 15-151 or 21-127.


  • Mathematics of networks: adjacency matrix, paths, connectivity, cut sets, the graph Laplacian, spectral analysis
  • Network models: random networks, scale-free networks & power law distribution, small-world networks & clustering coefficient
  • Centrality algorithms: eigenvector centrality, closeness and betweenness centrality, PageRank, hubs and authorities
  • Community detection: components, cliques, k-cores, Newman-Girvan algorithm, structural equivalence
  • Visualizing networks: information visualization with networks, colors, human perception
  • Diffusion processes: percolation, epidemics on networks
  • Social forces: transitivity, reciprocity, propinquity, homophily
  • Big data networks: algorithmic optimization, approximation algorithms, distributed calculations, issues related to missing data
  • Special topics: social media networks, the internet, power grids, bio-networks, co-publishing networks, business networks, semantic networks


Instructor: Jürgen Pfeffer
Units: 12 & 9
Days: Tuesday/Thursday
Time: 9:00-10:20
Location: GHC 4102
Final Exam: Yes

Guest Lecturers

Cosma Shalizi (Stats)
Jose M. F. Moura (ECE)
David Krackhardt (Heinz)


Mark Newman
Networks: An Introduction


9 Units

10 % - Assignment 1
10 % - Assignment 2
10 % - Assignment 3
20 % - Assignment 4
50 % - Final Exam

12 Units

75 % - All of the above
25 % - Research Project