Information networks such as the World Wide Web are characterized by the interplay between heterogeneous content and a complex underlying link structure. This course covers recent research on algorithms for analyzing such networks, and models that abstract their basic properties. Topics include combinatorial and probabilistic techniques for link analysis, centralized and decentralized search algorithms, network models based on random graphs, and connections with work in the social sciences.
The course prerequisites include introductory-level background in algorithms, graphs, probability, and linear algebra.
The work for the course will consist primarily of two problem sets, a short reaction paper, and a more substantial project.
(1) Complex Networks and the Web
(2) Small-World Properties in Networks
(3) Decentralized Search in Peer-to-Peer Networks
(4) Cascading Behavior in Networks
(5) Power-Law Distributions
(6) Economic Models for Behavior in Networks
(7) Link Analysis for Web search
(8) Spectral Analysis
(9) Rank Aggregation and Meta-Search
(10) The Time Axis
(11) Clustering, Classification, and Community Structures