Kleinberg Complex Networks.

摘要

This is the final report for AFOSR Award FA9550-09-1-0100. The award funded a research project conducted by PI Robert Kleinberg, investigating algorithmic aspects of the theory of complex networks as they relate to learning, routing, coding, and modeling of network structure and evolution. The research yielded a broad set of discoveries. Highlights over the five years of the project include the resolution of a twenty-year-old open question relating to the traveling salesman problem, the first rigorous analysis of Schelling's segregation process (a highly influential model that had been studied for decades via simulation in the social sciences, but whose behavior had resisted rigorous mathematical analysis prior to our work), a proof of the strongest separation to date between the power of linear and non-linear network codes, and a recent award-winning paper that introduces and analyzes a model of crowdsourced learning that sheds new light on the famous "exploration-exploitation" trade-off in sequential learning.