2008 Courant Lectures
Wednesday, March 12, 2008 3:30P.M., WWH 109
Jon Kleinberg, Professor of Computer Science, Cornell University
Synopsis
The growth of on-line information systems supporting rich forms of social interaction has made it possible to study social network data at unprecedented levels of scale and temporal resolution. This offers an opportunity to address questions at the intersection of mathematics, computing, and the social sciences, where mathematical models and algorithmic styles of thinking can help in formulating models of social processes and in managing complex networks as datasets. We consider two lines of research within this general theme. The first is concerned with modeling the flow of information through a large network: the spread of
new ideas, technologies, opinions, fads, and rumors can be viewed as unfolding with the dynamics of epidemic, cascading from one individual to another through the network. This suggests a basis for models of such phenomena, as well as new kinds of open questions.
The second line of research we consider is concerned with the privacy implications of large network datasets. An increasing amount of social network research focuses on datasets obtained by measuring the interactions among individuals who have strong expectations of privacy. To preserve privacy in such instances, the datasets are typically anonymized -- the names are replaced with meaningless unique identifiers, so that the network structure is maintained while private information has been suppressed. Unfortunately, there are fundamental limitations on the power of network anonymization to preserve privacy; we will discuss some of these limitations (formulated in joint work with Lars Backstrom and Cynthia Dwork) and some of their broader implications.
Modeling Social and Economic Exchange in Networks
Thursday, March 13, 2008 3:30P.M., WWH 102
Jon Kleinberg, Professor of Computer Science, Cornell University
Synopsis
There has been a growth of recent interest in modeling markets as networks, with buyers and sellers engaging in forms of trade subject to network-based constraints on their interactions. This line of work builds on a long history of research on buyer-seller matching in economics, parts of which are closely connected to the development of matching theory in discrete optimization.
Concurrently, sociologists have used network-based models to study power imbalances in the relationships between pairs of people. This includes not just economic exchange but social interaction more generally: a common modeling strategy is to view social relations between two individuals as producing value for both; the power of an individual in the relationship is then based on the extent to which this value is divided unequally.
In all these approaches, a fundamental question is how the network structure affects the outcomes of the participants. We discuss several recent results that address this issue. We beg in with a natural extension of bargaining theory to interaction on arbitrary networks, and describe joint work with Eva Tardos in which we provide the first existence proofs and characterizations for the analogue of the Nash bargaining solution in this theory. We then describe joint work with Larry Blume, David Easley, and Eva Tardos that extends network-based models of trade to include price-setting intermediaries. Such intermediaries capture the way in which prices are set in a wide range of real markets, and they provide us with a strategic basis for the outcomes of trade in these settings.