The Structure of Information Networks

CS584 Spring 2015

Multiple fields, including computer science, political science, physics, epidemiology, biology, ecomics and social science, have independently tackled surprisingly related problems in the past, but are now joining forces to create a new science of the structure of large real-world networks. The course studies the connectness of our social, technological and biological worlds through the lens of graphs and networks. We will look into how people are connected in social networks; how opinions, disease and political activism spreads through society; how communities form and can be inferred from data; theories underlying strong and weak ties in relationships; ranking of the web hyperlink graph (PageRank), and various other topics. We will study models and theory to help explain and exploit the structure of information and social networks. We will also discuss some tools to facilitate the analysis of these networks.

Instructor and TAs

Prof. Ymir Vigfusson.
Helga Gudmundsdottir
Helgi K. Sigurbjarnarson
Petur O. Ragnarsson


Tu/Th 10:00-11:15am W306 Lectures.
Tu 2:30-3:30pm E416 Office hours (Ymir).
W 13:00-14:00 E425 Office hours (Helga/Helgi/Petur)

An up to date schedule is on Google Docs

Homework #1 Due 1/31 at 23:59 ET. Problem set 1. PDF.
Homework #2 Due 3/19 at 23:59 ET. Problem set 2. PDF.
Lecture 1 1/13/15 Introduction. Graph theory. (YV). Slides Video (Emory only)
Lecture 2 1/15/15 More graph theory. The Web as a graph. Slides Video (Emory only)
Lecture 3 1/19/15 The strength of weak ties. (YV) Slides Video (Emory only)
Lecture 4 1/22/15 Structural Balance (YV). Slides Video (Emory only)
Lecture 5 1/27/15 Game theory (YV). Slides Video (Emory only)
Lecture 6 1/29/15 Evolutionary game theory (YV). Slides Video (Emory only)
Lecture 7 2/3/15 Game theory in networks, Braess' Paradox. (YV) Slides Video (Emory only)
Lecture 8 2/5/15 Auctions. (YV). Slides Video (Emory only)
Lecture 13 2/24/15 Sponsored search markets (YV). Slides Video (Emory only)
Lecture 15 3/3/15 Information cascades (YV). Slides Video (Emory only)
Lecture 17 3/17/15 The Small-World Phenomenon. (YV) Slides Video (Emory only)
Lecture 19 3/24/15 HITS and PageRank algorithms. (YV) Slides Video (Emory only)

Integrity. Students are also expected to abide to the SPCA policy on computer assignments.