CAS CS 591 - Fall 2016 - Networks and Markets: Theory and Applications
Recently, the concept of a network has outgrown the narrower engineering mindset of a collection of
interconnected machines to become more broadly relevant in a variety of applied settings which feature
connectedness. Biological networks, social networks, online advertising networks, and networks involving
hyperlinks, i.e., the WWW, are all examples of domains in which the theory and practice of networking
science has now being applied. In parallel with this trend is the rise of online markets as a mediation
point for commercial activity. Beginning with the advent of Internet platforms like eBay that employ online
auctions, are many fascinating new markets: pay-per-click advertising markets, prediction markets, and
two-sided platforms such as Uber and Airbnb. All of these application domains draw deeply on established
methodologies that are highly familiar to computer scientists, notably graph theory and algorithms.
However, they also build on theoretical foundations that is often unfamiliar territory to computer scientists,
such as auction design, mechanism design, and the theory of matching markets. Finally, many important new
technologies incorporate a mix of networks and markets, including information networks and recommender systems.
In this class, we will build on the highly successful undergraduate text of Easley and Kleinberg to learn about
the underlying theory of networks and markets, understand how modern-day digital applications connect to these
foundations, and conduct our own independent projects to explore an aspect of a digital market more deeply.
In this class, we will consider networks and markets from a broad and inter-disciplinary perspective,
drawing primarily from insights from the Computer Science, Economics, and Marketing communities.
This course is designed for students who are potentially interested in either pursuing a career in or
conducting research related to online networked platforms. Please note that this course is not about
entrepreneurship per se, but will provide useful background for prospective entrepreneurs.
The capstone project of the course will be a research effort, conducted by teams of two or three,
in which students conduct a quantitative
measurement-driven analysis of a computational aspect of an e-commerce firm or of consumer
behavior with respect to an e-commerce marketplace.
This course is designed for declared CS majors who are fulfilling 400-level electives,
as well as Masters students and entering Ph.D. students. CS 112, CS 131, and some knowledge of probability and
statistics is required. CS 330 is suggested as a co-requisite.
While students' backgrounds will vary, it is expected that students are nearing completion
of an undergraduate CS major or are beginning their graduate studies. Seniors who are not CS majors should
seek the instructor's permission to enroll.
Lectures: Tues/Thurs 12:30-2:00, CAS 237.
I expect students to come to class, to come on time, and to be prepared to actively engage in class discussion.
I will be eliciting responses from all students to hear their opinions.
Prof. John W. Byers
Email: byers @ cs . bu . edu [preferred]
Office Hours (Fall 2016):
Open hours: Tues 2-4
By prior appointment only: Wed 10-11.
For technical questions beyond what Piazza can answer (see below), or when you need a consultation.
During office hours, I'll answer my phone at 617-353-8925.
Other times, I generally let phone calls go to voicemail. Please send email instead.
Academic: John is Professor of Computer Science at Boston University. His academic research interests are broadly focused on algorithmic and economic aspects of e-commerce, networking, and large-scale data management. His work strikes a balance between
theoretical foundations and rigorous data-driven experimentation.
Entrepreneurial: John is founding Chief Scientist and Board Member at Cogo Labs, a start-up based in Cambridge, MA, where
he has had an executive role since the company's founding in 2005. Cogo leverages a unique proprietary
technology platform for algorithmic marketing, data mining, and quantitative business analytics to guide incubated
portfolio companies from inception to profitability and beyond.
Textbook and Readings
Primary Text: "Networks, Crowds, and Markets: Reasoning About a Highly Connected World",
by Easley and Kleinberg. ISBN: 9780521195331
A/B testing and running controlled experiments.
"Controlled experiments on the web: survey and practical guide",
R. Kohavi, R. Longbotham, D. Sommerfield, R. Henne, DMKD (18) 140-181, 2009.
J. Feigenbaum, D. Parkes, and D. Pennock,
in E-Commerce", CACM, January 2009, 52(1), pp. 70-74.
- Recommender systems: overview of objectives and basic methods.
The 2005 survey
by Adomavicius and Tuzhilin, IEEE TKDE 17(6), June 2005, still serves as a useful
- The Netflix Prize. Several good summaries of the Netflix competition are out there,
including from Smyth (UCI)
Technical foundation: "Modeling
Relationships at Multiple Scales to Improve Accuracy of Large Recommender Systems",
by R. Bell, Y. Koren, and C. Volinsky.
We will be using Piazza for all discussions outside of class.
Rather than emailing questions about the class to me, I encourage you to post your questions on Piazza, where
you are also welcome to answer questions posted by others.
Our class page is located at:
Please go there to sign up today.
We will also use Piazza to post announcements, homework assignments, etc.
Course Requirements and Grading:
There will be three components of the grade in the class:
For class, we will be drawing primarily from the Easley-Kleinberg textbook, but as this is an
introductory text, we will also be going deeper with additional lecture material and some outside readings
tailored for advanced CS undergraduates and beginning graduate students.
- Summarization and in-class discussion of the readings in the course (10%).
- Homework assignments (25%).
- In-class quizzes/exams (25%).
- Comprehensive, semester-long research project (40%).
We will have periodic homework assignments, in-class quizzes comprising short answer problems, and perhaps a few
longer homework problems.
Project: The capstone project for the course will be a semester-long research project, culminating in a writeup and a
presentation to the class, which will take the form of a poster and/or a demo at a class-wide poster+demo session.
The topic of the research project will be for students to conduct a study of a computational aspect of an e-commerce firm
or of consumer behavior with respect to an e-commerce marketplace. Students may work in teams of two or three,
with the expected output of the teams to be commensurately larger. Suggested project topics and project deadlines will be
announced after the first few weeks of the course, with regular milestones throughout the semester. I will expect
students in this class to take the project very
seriously and there will be regular interaction with the instructor outside of class to work on the projects ---
ideally, several of the best projects in the class will eventually continue beyond the class, in a direction towards
publication or commercialization.
Research studies may take a variety of forms, depending on students' interests and aptitudes. The most typical
project will be to conduct and write up a research study that is a quantitative, i.e., data-driven, analysis of a
computational aspect of an e-commerce firm or of consumer behavior with respect to a networked marketplace. We
will discuss several examples of these a few weeks into the semester. An ambitious, but reasonable goal for CS
graduate students, would be to initiate a line of work with the potential to further develop as a publishable paper
in the experimental track of the ACM Symposium on Economics and Computation,
or to develop into a Masters thesis or dissertation chapter. Work will be graded based both on the effort
demonstrated in the pilot study and on the promise of the proposed future work.
A second option is to design and write up an app, or other software system, that addresses a challenging direction
in the general space of networked platforms. Work will again be graded based both on the demonstrated output and
in the promise of the proposed future work, using grading at Hackathons as a barometer.
A third (and perhaps the most difficult) option is to develop a business plan to tackle a problem in this space,
formatted both as a writeup and as a presentation pitch deck for seed funding in the $50K range (which will also be
presented as a poster at the poster session). Work will be graded based on the quality of the pitch from the
perspective of an investor, using competitiveness at a student business plan competition as a barometer.
If a team has an alternative project idea in mind that they believe is in scope, they should feel free to pitch it
as a potential project direction at the appropriate early milestone in the class.
- Course overview. Technical backdrop, graphs [EK, Chapters 1 & 2]
- Strong and weak ties [EK, Chapter 3]
- Homophily and network structure [EK, Chapter 4 and 5]
- Game theory and strategic behavior [Ek, Chapter 6]
- Auction design and auction theory, Ebay [EK, Chapter 9]
- Methods and practice of large-scale data analysis [outside readings]
- Matching markets and applications to ad auctions [EK, Chapter 10, 15]
- Network equilibria and bargaining [EK, Chapter 11]
- Web structure, page rank [EK, Chapter 13-14]
- Recommender systems and personalization. Netflix challenge. [outside readings]
- Information cascades, network effects and power laws [EK, Chapter 16-18]
- Diffusion, epidemics and "small-worlds" [EK, Chapter 19-21]
- Markets with information [Ek, Chapter 22]
- Peer-to-peer markets, e.g., Uber, Airbnb [outside readings]
Course Schedule (as it evolves). Handouts and lecture slides are available on Piazza.
- [Tues 9/6]: Class syllabus and overview/review of networks.
Reminder of graph definitions, data structures and basic graph
algorithms. Reading EK: Chapter 1.
- [Thurs 9/8]: Network structure and metrics. In-degree,
out-degree and degree distributions. Average and worst-case path
lengths. Connected components and giant component. Erdos-Renyi
random graph model. Reading: EK Chapter 2.
For next week: Please watch the 1-hour documentary:
"Connected: The Power of Six Degrees", directed by Talas.
For class on Tuesday, in a few paragraphs, briefly describe an example of an online market that could leverage the six degrees
of separation principle to further its business goals. I'm looking for cleverness, conciseness, and clarity in your example.
E-mail me your reply no later than 9AM Tuesday, 9/13.
- [Tues 9/13]: Discussion of Six Degrees documentary, student intros.
Concepts and applications of node centrality. Various measures: betweenness, closeness, eigenvector. PageRank.
- [Thurs 9/15]: Conclude discussion of PageRank. Strong and weak ties, triadic closure, overlap and span, structural holes. Reading: EK Chapters 3.
Homework #1 is now posted on Piazza, due Tuesday, September 27 in class.
- [Tues 9/20]: No class. John away at NSF PI meeting in Washington DC.
Office hours on Tuesday are also canceled. Send e-mail to make an appointment Thursday or Friday.
- [Thurs 9/22]: Network constraint measure, group formation and community detection. Girvan-Newman algorithm. Modularity definition and use as a stopping condition.
Reading: EK Chapter 5.
- [Tues 9/27]: Intro to game theory: players, strategies, payoff matrix. Prisoner's dilemma and many other examples. Dominant strategies, best response, Nash equilibria.
Reading: EK Chapter 6.
- [Thurs 9/29]: Computing Nash equilibria: brute-force algorithms and NP-hardness. Mixed strategies, various notions of optimality. Applications to evolutionary biology.
Reading: EK Chapter 7 (skim).
- [Tues 10/4]: Discussion of class project (handout),
Wrap up biology applications. Discussion of congestion in traffic networks. Definitions, equilibria, and Braess's paradox.
Reading: EK Chapter 8.
Homework #2 is now posted on Piazza, due Tuesday, October 18 in class.
- [Thurs 10/6]: Auctions, part I. Basic definitions: valuations, rules of the game, taxonomy of auction formats.
Ascending and descending-price auctions. Open cry vs. sealed bid. First and second-price auctions.
Reading: EK Chapter 9.
- [Tues 10/11]: BU is on a Monday schedule due to Columbus Day. No lecture.
- [Thurs 10/13]: Auctions, part II. Equilibrium strategies in various auction formats.
Truthfulness in second-price auctions, optimal shading of bids in first-price auctions with uniform valuations.
- [Tues 10/18]: Auctions wrap-up: revenue equivalence, winner's curse.
Matching markets, part I. Review of bipartite graphs, and efficient matching algorithms via max-flow reduction.
Rules of the game, notion of preferred seller and market-clearing prices (MCPs).
Reading: EK Chapter 10.
- [Thurs 10/20]: Matching markets, part II. Algorithm to compute MCPs, including proofs of
correctness, termination and running time. Proof that MCPs achieve socially optimal allocation.
Motivation for ad auctions: EK Chapter 15.
- [Tues 10/24]:
Prof. Peter Marton
from Questrom will be giving us a tutorial on the art of the elevator pitch. Then we will construct elevator
pitches for our class projects, deliver them, and get feedback. (Pitch delivery will continue on Thursday).
- [Thurs 10/26]: Elevator pitches. Ad auctions as a matching market. GSP auctions, EK Chapter 15.
- [Tues 11/1]: Elevator pitches and wrap up of ad auctions. VCG principle and proof of truthfulness.
VCG vs. GSP-based ad auctions, EK Chapter 15.
- [Thurs 11/3]: Recommender systems: overview of objectives and basic methods. Emphasis on collaborative filtering.
The 2005 survey
by Adomavicius and Tuzhilin, IEEE TKDE 17(6), June 2005, still serves as a useful
- [Tues 11/5]: Recommender systems in practice: the Netflix prize competition. Description of methods
and the competition itself. Slides on Piazza.
- [Thurs 11/10]: Cascading behavior in networks. Diffusion, cascades and clusters. EK Chapter 19.
- [Tues 11/15]: Comprehensive in-class midterm. Covers material up through Thurs 11/3.
- [Thurs 11/17]: Probabilistic models of contagion. Spreading models and the reproductive number.
SIR model and epidemic threshold. Diffusion applied to viral marketing.
- [Tues 11/22]: Answers to midterm questions. Cody Doucette presented tips on how to make a great
poster for the poster session, and provided examples of the good, the bad, and the ugly (on Piazza).
- [Thurs 11/24]: Happy Thanksgiving!
- [Tues 11/29]: Heavy-tailed degree distributions: what they are and how to
spot them. Power-law models and characteristics. Distinction from ER random graphs. Generation
of power law random graphs through preferential attachment.
- [Thurs 12/1]: No class. Homework #4 (optional), due Monday, December 12th, posted on Piazza.