• Administrative details, how the fact that we live in a networked world leads to fundamentally new problems and to unexpected variants of classical problems.
• Key methodological ingredients: graph theory, probability & statistics, (distributed) algorithms for now (game theory to come later).
• The expectation: definition, interpretations (laws of large numbers and the probabilistic method viewpoint of "weighted average"), linearity of expectation, comparison to the median, alternative formula, examples.
• Random walks on graphs, coupon collector, Markov's inequality.
• The Second Moment Method and Chebyshev's inequality.

• MAX CUT and large cuts (to be seen again later in pricing problems).
• The union bound.
• Contention resolution and distributed algorithms.
• Distributed scheduling, graph coloring, probabilistic recurrence relations, and a full analysis of Luby's coloring algorithm (along with discussions of symmetry-breaking via distributed random permutations).

• The kth moment inequality.
• The variance-covariance formula, negative correlation, and sampling with/without replacement.
• Sampling using k-wise independence; brief discussion of data-streams and Alon-Matias-Szegedy.
• Start discussion of sparse cuts; separator theorems for planar and fixed-minor-free graphs.

• (The first few among Luca Trevisan's lectures provide excellent background for the lectures of Feb 8 and Feb 15.)
• Vertex- and edge-expansion, sparsest cut, Ramanujan graphs, and the resilience of expanders.
• Basic properties of eigenvalues and eigenvectors.
• A sneak peek at homophily and the strength of weak ties.

• Graph density and its applications to networks.
• Max-flow-based exact algorithm for computing maximum-density subgraph and a linear-time greedy approximation algorithm.
• The densest k-subgraph problem: algorithms and hardness.

• Eigenvalues and expansion for regular graphs: Trevisan's notes on Linear Algebra review and Cheeger's inequality.

• Bounds on binomial coefficients and binomial sums.
• Random graphs G(n,p): regions with the double jump, connectivity, and expansion: heuristic proofs.
• Poisson and Normal approximations, power-law degree distributions, and "long tails".
• (See this Wikipedia article for the positive, perhaps less-known, role played by Edgar Gilbert in developing random graphs.)

• Random graphs G(n,p): examining their expansion.
• Tail bounds under negative correlation; positive correlation and cascades.
• Long-range links in social and peer-to-peer networks.
• Long-range links yield expansion: Theorem 1 in Abie Flaxman's paper; discussion of why a direct plugging-in of the Chernoff lower-tail bounds will not work for small-set expansion.

• Very large deviations above the mean; finish discussion of Flaxman's work.
• Milgram's experiments, small-world phenomena, and Kleinberg's work on distributed navigability in small-world networks.
• Rank-based friendship and some of the findings of Liben-Nowell, Novak, Kumar, Raghavan & Tomkins and Backstrom, Sun & Marlow; the work of Sandberg in brief.

• Discussion of mid-term class evaluation.
• Complete the discussion of small-world routing.

• Link-based search: Kleinberg's work on hubs and authorities.
• A brief introduction to PageRank.

• Finish hubs-and-authorities and PageRank.
• General discussion of the role of bootstrapping & modeling, and examination of three examples of bootstrapping in Web search: starting with an approximately-good ranking, repeated improvement in hubs-and-authorities, and search engines/machine learning improving from user-clicks.
• Recap of basic probabilistic tools.
• Introduction to basic game theory, mostly from Chapter 6 of Easley-Kleinberg: motivation, games in normal form, examination and critique of modeling strategic interaction/games in this manner, best responses, dominant strategies, and strategy elimination.
• (This video of Dan Ariely is worth watching.)

• Continuation of game theory from Chapter 6 of Easley-Kleinberg: Nash equilibria, multiple equilibria, zero-sum games, mixed strategies, Pareto- and social- optimality, dynamic- and multi-player- games.
• Zero-sum games and linear programming.

• Exact and approximate computation of Nash equlilibria.
• Aumann's correlated equilibria and linear programming.

• Network Traffic and Game Theory (largely following Chapter 8 of Easley-Kleinberg).
• Pricing problems: the Balcan-Blum model.
• (Check out this video and a similar one that give physical demonstrations of Braess' paradox.)

• Pricing when the market is known: the approximation algorithms of Balcan-Blum for graphs and hypergraphs; see also Avrim Blum's talk slides.
• Pricing digital goods when the market is not known: the RSOP auction.
• A brief classification of single-item auctions.

• Incentive-compatibility of the second-price auction; optimal bidding strategies under randomly-chosen valuations (largely from Chapter 9 of Easley-Kleinberg).
• Start matching-markets.

• Matching markets (largely following Chapter 10 of Easley-Kleinberg): bipartite graphs, perfect matchings and Hall's Theorem, valuations and weighted matchings, market-clearing using prices (social-optimality and construction using Egervary's approach), and relation to single-item auctions.

• Algorithmic proof of Hall's Theorem.
• Algebraic approaches to matching: the Isolating Lemma and the Mulmuley-Vazirani-Vazirani algorithm.
• Whirlwind coverage of Chapter 11 of Easley-Kleinberg.
• (See these CMU lecture notes for more on probabilistic approaches to basic algebraic problems.)

• Stable marriages and stable rommmates/matchings: algorithm and proof of correctness for stable marriage, quick coverage of stable roommates, NP-hard variants, and college admissions (hospital/resident allocation).
• Bargaining and power in networks, largely from Chapter 12 of Easley-Kleinberg: basic models for power and social exchange, network-exchange experiments, interpretation of the Ultimatum Game, Nash Bargaining for two players, and stable outcomes.

• Balanced outcomes in bargaining.
• Game-theoretic reasoning in bargaining.
• (Watch this video and related ones on bargaining by William Spaniel.)

• Network dynamics: information cascades and very brief coverage of direct-benefit effects.
• A quick introduction to submodular functions, the properties they share with concave and convex functions, and the performance of the associated greedy algorithm.
• (See Jan Vondrak's Charles University thesis for an excellent modern study of submodularity.)

• Network effects on dynamics: examples from medicine & agricultural practices, and lessons learned.
• Networked coordination game with binary options: cascades, clustering & weak ties, and the cascade capacity.
• Epidemics: contact networks and branching processes, the basic reproductive number, SIR and SIS models, wireless worms.
• A basic "bipartite influence-maximization" problem (motivated, e.g., by banner advertising): two (1 - 1/e)-approximation algorithms based on submodularity and rounding an LP relaxation.

Web Accessibility