Computer scientists test social network theory

US computer scientists have devised an experiment to test the famous claim of psychologists Jeffrey Travers and Stanley Milgram that everyone is separated by only six connections from everyone else.

Researchers at the University of Pennsylvania's School of Engineering and Applied Science found that some of the simplest social networks function the most poorly, and that information beyond a "local" view of the network can actually hinder the ability of some complicated social networks to accomplish tasks.

"Travers and Milgram's classic six degrees of separation experiment was one of the first large-scale attempts at studying a human network," said Michael Kearns, a professor in Penn's Computer and Information Science Department.

"But almost 40 years later the interaction between social network structure and collective problem solving is still largely a matter of theoretical conjecture.

"Our goal was to initiate a controlled, behavioural component of social network studies that lets us deliberately vary network structure and examine its impact on human behaviour and performance."

To empirically test a number of standard network theories, Kearns teamed up with Penn doctoral students Siddharth Suri and Nick Montfort and gathered 38 Penn students to play a game of colour selection on networked computers.

The game required each of the students to choose a colour that did not match the colour of any person who was immediately connected to him or her in the network.

The researchers changed the patterns of the networked connections, i.e who was connected to whom, in ways that corresponded to the theoretical models.

"This colouring problem models social situations in which each person needs or wants to distinguish his or her behaviour or choices from neighbouring parties," said Kearns.

The tests allowed Kearns and his colleagues to examine in real time how well networks of people work together to solve colouring problems.

They performed a number of trials based on each model, looking at the speed at which the trial was completed and varying how much information subjects had about what colours were being selected elsewhere in the network.

"We see that social networks with more connectivity are not necessarily more efficient, but that it depends strongly on the collective problem being solved," Kearns explained.

"Less connectivity and less information about the network can sometimes make the problem easier.

"But now we have an experimental framework in which we can systematically investigate how social network structure influences actual human performance."