Lecture Schedule for CMSC858E, Models and Algorithms for Socio-Technical Networks, Spring 2011
Class Venue and Time: CSI 3118, 9:30-10:45AM Tue, Thu
The following is an outline of the main topics discussed in each class
of CMSC858E, Spring 2011.
This is an approximate summary, but gives an idea of the primary issues
covered. Thanks to student Karla Saur for her help with this!
Please let Aravind know if there are any major omissions or
Lecture 1, Jan 25, 2011:
Lecture 2, Feb 1, 2011:
- Administrative details, how the fact that we live in a networked world
leads to fundamentally new problems and to unexpected variants of classical
- 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,
- Random walks on graphs, coupon collector, Markov's inequality.
- The Second Moment Method and Chebyshev's inequality.
Lecture 3, Feb 3, 2011:
- MAX CUT and large cuts (to be seen again later in pricing
- The union bound.
- Contention resolution and distributed algorithms.
- Distributed scheduling, graph coloring, probabilistic
recurrence relations, and a full analysis of
algorithm (along with discussions of symmetry-breaking
via distributed random permutations).
Lecture 4, Feb 8, 2011:
- 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.
Lecture 5, Feb 10, 2011 -- Guest Lecture by Barna Saha:
- (The first few among
Luca Trevisan's lectures
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.
Lecture 6, Feb 15, 2011:
Lecture 7, Feb 17, 2011:
- 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.
Lecture 8, Feb 24, 2011:
- 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
- (See this
Wikipedia article for the positive, perhaps less-known,
role played by Edgar Gilbert in developing random graphs.)
Lecture 9, Mar 1, 2011:
Lecture 10, Mar 3, 2011:
Lecture 11, Mar 8, 2011:
- Random graphs G(n,p): examining their expansion.
- Tail bounds under negative correlation; positive correlation and
- Long-range links in social and
- 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.
Lecture 12, Mar 10, 2011:
- Link-based search: Kleinberg's
hubs and authorities.
- A brief introduction to PageRank.
Lecture 13, Mar 15, 2011 -- Guest Lecture by Tom DuBois:
- 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
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.)
Lecture 14, Mar 29, 2011:
Lecture 15, April 5, 2011:
- Continuation of game theory from Chapter 6
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.
Lecture 16, April 7, 2011:
- Network Traffic and Game Theory (largely following
Chapter 8 of
- Pricing problems: the Balcan-Blum model.
- (Check out this video and a similar one that give physical demonstrations of Braess' paradox.)
Lecture 17, April 12, 2011:
- 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
- A brief classification of single-item auctions.
Lecture 18, April 14, 2011:
- Incentive-compatibility of the second-price auction;
optimal bidding strategies under randomly-chosen valuations
Chapter 9 of
- Start matching-markets.
Lecture 19, April 16, 2011:
- 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.
Lecture 20, April 19, 2011:
- Algorithmic proof of Hall's Theorem.
- Algebraic approaches to matching: the
and the Mulmuley-Vazirani-Vazirani algorithm.
- Whirlwind coverage of Chapter 11 of
- (See these CMU lecture
notes for more on probabilistic approaches to basic algebraic
Lecture 21, April 21, 2011:
- 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
- Bargaining and power in networks, largely from
Chapter 12 of
Easley-Kleinberg: basic models for power and social exchange,
interpretation of the Ultimatum Game, Nash Bargaining for two players,
and stable outcomes.
Lecture 22, April 26, 2011:
- Balanced outcomes in bargaining.
- Game-theoretic reasoning in bargaining.
- (Watch this
video and related ones on bargaining by William Spaniel.)
Lecture 23, April 28, 2011:
- Network dynamics: information cascades and very brief coverage of
- 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.