Strategic Models for Information Flow in Social Networks and Peer-to-Peer Systems
Jon Kleinberg

Cornell University




Abstract:
The concurrent growth of on-line communities exhibiting large-scale social structure, and of large decentralized peer-to-peer file-sharing systems, has stimulated recent interest in understanding networks of interacting agents as economic systems.  Motivated by such systems, we study some general classes of networks in which users are provided with incentives to send or receive information.

We focus primarily on query incentive networks, in which users seeking information or services can pose queries, together with incentives for answering them, that are propagated along paths in a network.  Using analysis based on branching processes, we find that the network operates efficiently when it is above a critical ``effective branching factor,'' but below this critical point the sizes of query incentives needed to extract information from the network grow dramatically.

We also briefly discuss some recent empirical studies of recommendation incentive networks, a ``dual'' type of system in which information is unsolicited rather than explicitly sought:
users are offered incentives to pass recommendations to their network neighbors. We analyze the types of collective behavior that result, using data from a large on-line retailer.

This is based on joint work with Prabhakar Raghavan, Jure Leskovec, and Ajit Singh.



--------------------------------
Jon Kleinberg
www.cs.cornell.edu/home/kleinber
--------------------------------
 

Back