LINFO1115 – Reasoning about a highly connected world: graph theory, game theory, and networks

The world is increasingly connected through networked communication, principally the Internet but also other networks.  These networks evolve over time, growing and changing, and have an enormous effect on society.  Understanding this process requires a combination of disciplines: graph theory, game theory, and sociology.  This course is an introduction to this study.  We introduce the relevant elements of graph theory and game theory and use them to study the evolution of large networks with many participants.

Some of the topics we will touch in this course are:

  • Social networks and their properties: tie strength, closure, homophily, positive and negative relationships.
  • Introduction to game theory: best responses, dominant strategies, Nash equilibrium, Pareto optimality.
  • Introduction to evolutionary game theory: evolutionary stable strategies.
  • Modeling network traffic and Braess's Paradox.
  • Auctions: first-price, second-price, common values, winner's curse.
  • Markets: matching markets, market clearing, markets with intermediaries, bargaining.
  • Structure of the Web: bow-tie, Web 2.0.
  • Searching the Web: ranking, link analysis.
  • Sponsored search markets: advertising tied to search behavior.
  • Network dynamics I: information cascades, network effects, power laws, rich-get-richer phenomena, the long tail.
  • Network dynamics II: structural cascades, small-world phenomenon, epidemics.
The course is organized as weekly lectures and weekly lab sessions.  There will be a project during the last third of the semester that counts for one fourth of the final grade.  If possible, there will be an optional midterm around the middle of the semester that can count also for one fourth of the final grade.

This course is based on the book "Networks, Crowds, and Markets: Reasoning about a Highly Connected World", by David Easley and Jon Kleinberg, Cambridge University Press, 2010.  This book is the mandatory syllabus for the course.

Teaching assistants for the course are:
  • Xavier Gillard.
  • Bálint Daróczy.