CMSC 11710 Networks
What we covered so far
What we may cover next class
Assignments and Handouts
Things you should do urgently
email: simon (at) cs.uchicago.edu
Office Hours: Thursday 2-3
Huseyin Gokalp Demirci
Office Hours:Fri 3-4
Office hours: Tue 2-3
Textbook: "Networks, Crowds and Markets" by Easley and Kleinberg
A preprint of the text can be found
Grading will be based on weekly homework assignments, midterm (30%) and
a final (30%).
We will study examples of where the way objects or people are interconnected may help
understand they interact. We will look at mathematical models of networks and of some
interactions. This is a gentle introduction to apsects of mathematical and computational
modeling, as well as to algorithmic thinking and to some ideas in Economics.
This is a first draft, subject to changes depending on class preparation and interest. We may not cover all this material, and I may include other topics.
- Introduction. Course outline. Chapter 1
- Ch. 2: Graphs, directed graphs. Terminology. BFS
- Ch. 3: Strong and weak ties. Triadic closure. Clustering and graph partitioning.
- Ch. 4 Homophily. Link formation. Schelling model of spatial segregation.
- Ch. 5 Positive and negative relations. Structural balance.
Elements of Game Theory
- Ch. 6: Games. Equilibria, Nash Equilibria. Pure and mixed strategies, examples.
- Ch.7: Ideas about evolutionary games.
- Ch 8: An unintuitive fenomenon--Braess' paradox.
- Ch 9: Auctions: First and Second Price auctions.
Markets, bargaining and power in networks
- Ch.10: Matching markets. Market-clearing prices, and how to compute them.
- Ch.11: Trading with Intermediaries.
- Ch 12: Network Exchange and Game Theory.
Internet, Internet structure and protocols. Google search
- The http protocol and internet routing (handout)
- Ch.13: The interent as a graph.
- Ch.14: The google Page Rank algorithm (main idea)
- Ch 15: Determining ad prices on the internet: sponsored search markets.
- Ch 16: Information Cascades. Simple mathematical models.
- Ch 17: Network effects (sketch)
- Ch 18: Power Laws. Rich get richer.
Cascading and Epidemics
- Ch 19: Diffusion in Networks. Simple models.
- Ch 21: Epidemics: simple analysis of some simple models.
- Ch 22: Information and Markets: market for lemons, signaling, reputations. Information markets.
- Ch 23: Voting. Paradoxes, Arrow's Theorem.
Material covered so far
This is what I plan to cover in the next lecture or two.
- Assignment 1 Due Monday, April 14 in class.
- Assignment 2 Due Monday, April 21 in class.
Important Homework Instructions
Students are encouraged to work together, but each student must
independently write up their solutions.
Write-ups must include the
names of any collaborators and any sources used to help solve a
problem, other than the textbook.
Do NOT search the web for solutions!