Schedule

Readings in normal font should be completed and annotated ahead of lecture.
Readings in italic provide optional additional depth on the material.

Reading sources:

MEJN: Networks: An Introduction by Newman (2018).
HZB+PSC: Network Science: Models, Mathematics, and Computation by Heather Zinn Brooks and Phil Chodrow.

Week 1

Mon Feb. 10	Welcome!
Mon Feb. 10	We introduce our topic and discuss how the course works.
	Learning Objectives Getting Oriented	Reading Course syllabus
Wed Feb. 12	Networks and Their Representations
Wed Feb. 12	We introduce several different types of connected systems and discuss ways of representing them in mathematical and computational structures.
	Learning Objectives Network Fundamentals	Reading Newman 6.1 - 6.6	Notes Networks and their Representations	Warmup Newman 6.2

Week 2

Mon Feb. 17	Degrees, Walks, and Paths
Mon Feb. 17	We study several important structural properties that can be computed from the adjacency matrix of a graph.
	Learning Objectives Network Fundamentals	Reading Newman 6.10 - 6.12	Notes Degrees, Walks, and Paths	Warmup Leading Eigenvalue of the Complete Graph
Wed Feb. 19	Connected Components and the Graph Laplacian
Wed Feb. 19	We study the connected components of a graph. We also relate the number of connected components to another important matrix representation of a graph, the graph Laplacian.
	Learning Objectives Network Fundamentals	Reading Newman 6.14	Notes Connected Components and the Graph Laplacian	Warmup Properties of the Graph Laplacian

Week 3

Mon Feb. 24	Network Centrality
Mon Feb. 24	Many networks define a concept of centrality, importance, or rank. We discuss several mathematical methods for operationalizing these ideas and computing them from network data.
	Learning Objectives Measuring Networks	Reading Newman 7.1.1-7.1.4	Notes Centrality	Warmup Leading Eigenvector of a Regular Graph
Wed Feb. 26	Network Visualization
Wed Feb. 26	We study an algorithm used to draw networks, and also discuss some of the limitations of visualization in large networks.
	Learning Objectives Measuring Networks	Reading Newman 6.14.2 (very short, please allocate some extra time for the warmup)	Notes Visualizing Networks (And Why You Shouldn't)	Warmup Gradient of a Visualization Objective

Week 4

Mon Mar. 03	Structure of Empirical Networks
Mon Mar. 03	We conduct a comparative study of several empirical networks.
	Learning Objectives Measuring Networks	Reading Newman, 10.1-10.4.1	Notes Structure of Empirical Networks	Warmup Triangle Counting, Revisited
Wed Mar. 05	Random Graphs: Erdős–Rényi
Wed Mar. 05	We begin our investigation of random graphs with the Erdős–Rényi model, the most random of graphs.
	Learning Objectives Random Graphs	Reading Newman, 11.1-11.4	Notes Random Graphs: Erdős–Rényi	Warmup Binomial Distribution

Week 5

Mon Mar. 10	Random Graphs: Erdős–Rényi II
Mon Mar. 10	We continue our study of the Erdős–Rényi model, with special focus on the structure of connected components.
	Learning Objectives Random Graphs	Reading Newman, 11.5	Notes Random Graphs: Erdős–Rényi	Warmup Triangles in Sparse ER

Break

Mon Mar. 17	No class: spring break
Mon Mar. 17

Wed Mar. 19	No class: spring break
Wed Mar. 19

Week 6

Mon Mar. 24	Random Graphs: Degree Sequences
Mon Mar. 24	We introduce several random graphs which approximately or exactly preserve a specified degree sequence.
	Learning Objectives Random Graphs	Reading NA	Notes Degree-Preserving Random Graphs	Warmup NA
Wed Mar. 26	Random Graphs: Degree Sequences II
Wed Mar. 26	We continue our study of random graphs which approximately or exactly preserve a specified degree sequence.
	Learning Objectives Random Graphs	Reading (Optional): Newman 12.1	Notes Degree-Preserving Random Graphs	Warmup Reindexing Sums

Week 7

Mon Mar. 31	Random Graphs: Degree Sequences III
Mon Mar. 31	We study the friendship paradox in the context of degree-preserving random graphs.
	Learning Objectives Random Graphs	Reading Newman 12.2	Notes Degree-Preserving Random Graphs	Warmup Class Sizes and Weighted Averages
Wed Apr. 02	Power Laws and Preferential Attachment
Wed Apr. 02	We study the Yule-Price-Albert-Barabási model of preferential attachment, which generates power-law degree distributions.
	Learning Objectives Random Graphs		Notes Preferential Attachment and Power Laws	Warmup Posts on EdStem project pitches

Week 8

Mon Apr. 07	Assortativity and Modularity
Mon Apr. 07	We study assortative mixing on networks and derive the modularity as a measure of qualitative assortativity.
	Learning Objectives Data Science		Notes Homophily, Assortativity, and Modularity	Warmup No warmup; midterm exam assigned
Wed Apr. 09	No class
Wed Apr. 09	I'm holding office hours for the midterm exam instead
	Learning Objectives Exam			Warmup None

Week 9

Mon Apr. 14	Modularity Maximization
Mon Apr. 14	We study the modularity objective function for graph clustering and develop a simple greedy algorithm for maximizing it.
	Learning Objectives Data Science		Notes Community Detection and Modularity Maximization	Warmup None
Wed Apr. 16	Spectral clustering
Wed Apr. 16	We develop an alternative method for graph clustering based on the spectral properties of the normalized graph Laplacian.
	Learning Objectives Data Science		Notes Spectral Clustering	Warmup The Normalized Graph Laplacian

Week 10

Mon Apr. 21	Link Prediction and Feedback Loops
Mon Apr. 21
	Learning Objectives Data Science		Notes Link Prediction and Feedback Loops	Warmup Project update
Wed Apr. 23	Random Walks and Graph Exploration
Wed Apr. 23
	Learning Objectives Graph Exploration		Notes Random Walks	Warmup Leading Eigenvector of a Stochastic Matrix

Week 11

Mon Apr. 28	Agent-Based Models: Opinion Dynamics
Mon Apr. 28
	Learning Objectives Dynamics on Networks		Notes Agent-Based Models	Warmup Project update
Wed Apr. 30	Agent-Based Models: Epidemics
Wed Apr. 30
	Learning Objectives Dynamics on Networks		Notes Agent-Based Models

Week 12

Mon May. 05	Topic TBD
Mon May. 05

Wed May. 07	Project Presentations
Wed May. 07
	Learning Objectives Projects

References

Newman, Mark E. J. 2018. Networks: An Introduction. Oxford University Press.