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
--------------------------------