Course Description: The Internet, like other social networks, is comprised of independent agents who interact in complex ways to create a web of relations. These local decisions result in a global structure of a surprisingly predictable form. This course studies the structure of these networks with a particular focus on the Internet and web graph. We explore how this structure can be exploited to extract information from such networks. We further study the economic incentives facing the agents in the network, how these incentives affect the structure, and how we can design mechanisms to account for these incentives. Finally, we discuss several mechanism design questions motivated by e-commerce applications.

Topics include: Power law degree distribution in social networks, Small world phenomena, Models of power law random graphs, Game-theoretic approaches to modeling network creation, Crawling the web, HITS and Page Rank, Web spam, Rank aggregation and voting theory, Spectral clustering, Peering relations on the Internet, Mechanisms for routing, Spread of viruses on networks, Issues in P2P networks, Recommendation systems, Reputation mechanisms, and Online ad auctions.

Prerequisites: Some background in algorithms, familiarity with graphs, some linear algebra and probability.

Course work: reading papers and possibly a few short problem sets, including simple programming exercises.