Cornell University
more options

Kleinberg a Key Player in Searchable Social Networks

Searchable Social Networks

Two key pieces of research from Info Sci Chair Jon Kleinberg are cited in an exceptional, long-form MIT Media Lab piece exploring the last 90 years of searchable social networks. Kleinberg's exploration of "small world" networks from 2000 showed that social search is easily done without global knowledge of a particular network, but only to the extent that "we know someone far removed from us, socially, in the social network."

In 2005, Kleinberg's research – this time with collaborator Prabhakar Raghavan – would again have a profound impact on searchable social networks. Their paper, "Query Incentive Networks",  "provided a powerful way of exchanging favors in a social networks," according to the MIT article. 

"Individuals interested in recruiting other individuals for an ongoing social search would set the terms of the 'favor exchange' for their recruited friends: 'If you help me with the search, I give you X.' This is how networks usually work: they do so by the fact that people expect some sort of payoff when helping out. Query Incentive Networks compute a value for X that keeps the recruitment chain growing until the elusive information or individual is found by the network."

Kleinberg's work with Raghavan on query-incentive networks also popped up in a Bitcoin Magazine article, "The Rise of User-Monetized Actions: Bitcoin's Killer Application". In it, the Magazine cites the duo's work, saying query-incentive networks influenced the winners of DARPA's "Red Balloon Challenge". The author argues that if one uses Bitcoin to "send microtransactions to their own network of followers, what you end up with is a variant of Kleinberg and Raghavan’s Query Incentive Network model that allows one to execute MapReduce-like operations over a large network of willing participants."