The community in which I live has a handy listserv. Members pass on local news, post announcements, advertise the availability of goods and services, ask questions, and offer advice. Someone looking for a reliable company to finish a basement or a veterinarian to take care of an ailing dog can get useful recommendations from neighbors who subscribe to the list.
Facilitated by e-mail and the Internet, such social networks have grown to become important avenues for seeking information. Social networking systems, such as Orkut or LinkedIn, create online communities in which new members join by linking to friends who already belong to the system. The result is a network defined by friendships.
Whether it’s to find a new job or an apartment or some piece of vital information, you, as a member of such a network, can ask your friends, who in turn can ask their friends, and so on. This chain of acquaintances gives you access to the varied expertise of a potentially large set of people. If your friends or colleagues don’t know the answer to a question, they often know someone who might very well have the answer.
This type of information gathering can be particularly valuable because the answers you get are vetted. You trust your friends, and they in turn trust their friends, and so on.
For such a system to be effective and efficient, however, people have to be willing to participate. Friends are quite likely to help friends, but a friend of a friend may be less willing to help the person posting the original query, especially when this person may be a complete stranger to the potential helper.
In a 2003 experiment, sociologist Duncan Watts of Columbia University and his coworkers used e-mail to test the notion that every person in the world can reach any other person through a chain of just a handful of social ties. In many instances, the chain fizzled out when someone failed to pass the message on.
The high attrition rate demonstrated in the experiment suggests that it may be difficult to find “faraway” information in a social network. Many people may not be motivated enough to participate.
To overcome this problem, the idea is to offer a reward for the information. Then, as a query is passed from person to person, each participant takes a cut. The search continues until the reward money runs out or an answer is reached.
To study how the addition of incentives might affect information retrieval in a social network, Jon Kleinberg of Cornell University and Prabhakar Raghavan of Yahoo! Research have developed a simple model of how queries can spread in a random network. In this query incentive network, users seeking information or services pose questions and offer rewards for finding answers.
The key question is how much incentive is required for a member of a social network to have a reasonable probability of extracting an answer to a query from the network. Raghavan and Kleinberg focused on the size of the incentive as a function of both the difficulty of finding the answer (its rarity) and the structure of the underlying network.
The crucial parameter describing the underlying network is its “effective branching factor.” In effect, it’s the average number of friends to whom a member of the network passes on a query.
When the branching factor, b, is greater than 1, there exist reasonably short paths to the answer. However, if the branching factor is less than 2, the amount you have to pay in incentives to get an answer is prohibitive—even though short paths to the answer exist. The situation is much more favorable when the branching factor is greater than 2.
“For a large branching factor, the propagation of queries is very efficient in its use of reward,” Kleinberg and Raghavan conclude in a paper presented at the 46th Annual Symposium on Foundations of Computer Science, held recently in Pittsburgh.
“By simulation, we have found that the transition at b = 2 is already apparent for rarities n of moderate size,” the researchers report. A rarity of n means that one out of n members possesses the answer to a given question.
So, when you’re offering incentives, it’s a good strategy to ask at least two friends when you need advice. Asking just one friend isn’t enough to give you a reasonable chance of eventually getting an answer via some chain of acquaintances.
