The evolving face of social networks

It seems that everyone is excited about social networks. But not quite in the same way as Harvard graduate student Erez Lieberman, whose evolutionary graph theory is encouraging people to think about social networks in a different way: as an evolving population.

Lieberman developed the theory with Harvard mathematics professor Martin Nowak, who helped to lay its foundation through the observation that while most of evolutionary theory deals with populations that have either simple shapes or no structure at all, the world around us is full of evolving systems with all kinds of internal structure – whether it's the networks of cells present in the human body or the social networks that occur in cyberspace.

"Our work was the first really systematic attempt to study Darwinian evolution on arbitrary networks," says Lieberman. "The problem for theorists is that when you try to account for the network, the maths can get much harder. There's a back-and-forth that goes on between networks and Darwinian evolution. On the one hand, the network structure affects the direction evolution will take; but on the other hand, over time evolution will remodel the network."

Lieberman and Nowak's work builds on that of 1950s mathematician Paul Erdös, which shed light on the question of how networks change as they grow, and the work of Peter Clifford and Aidan Sudbury, who developed some of the underlying maths in their studies of competition in the 1970s.

Changing networks

At its simplest, evolutionary graph theory deals with the future of a network and the individuals that live at its nodes when the network begins to evolve and its individuals start moving, mutating and influencing their neighbours. A network can evolve in two ways: either individual nodes evolve while the network stays the same (a new strain of flu enters a population; one person gets 10 friends to vote for Obama), or the network itself changes (as continents drift, they separate subpopulations of the same species; someone makes 10 new friends on Facebook).

"People sometimes think of networks in terms of a concept called a replicator," Lieberman says. "A replicator is an entity, be it an organism, a computer virus, or even an idea, that can somehow make copies of itself. Networks are a way of thinking about where the new copy can go."

It wasn't a big surprise when evolutionary graph theory found applications in biology, which abounds with these replicators. One context where it has been applied is the study of cancer.

Lieberman explains it like this: "A really crude way of thinking about cancer is that cancer cells are ordinary cells that reproduce too fast. When you frame it that way, you see that cancer is an evolutionary problem: what makes an individual cell fitter (reproducing a lot) makes the organism a lot less fit (death from cancer). Natural selection at the level of the cell is in conflict with natural selection at the level of the organism."

"By severely restricting cellular reproduction to a small collection of cells called stem cells, the human body actually reconfigures its own network in a way that dramatically weakens natural selection at the cellular level. This enables the organism to survive without cancer for far longer."

But now evolutionary graph theorists are beginning to think about applications beyond biology. After all, the theory applies to replicators, things that somehow manage to make copies of themselves. But no one says that to be a replicator, you have to be alive.

Enter web-based social networking. On websites such as Facebook and MySpace, networks evolve as people influence one another (changing the configuration of the nodes) and as new friendships are made (changing the network as a whole). Sites such as these are just teeming with replicators. "Vampires", a Facebook application, can spread as easily as the flu: when people "bite" their friends, the "Vampires" app gets passed along the friendship network.

Evolutionary graph theorists have already begun to make progress. "One of the interesting things we've found about social networks is that the presence of network structure can give rise to pro-social behaviours," says Lieberman.

"This is an idea now called 'network reciprocity'. There's an inverse relationship between the number of connections you have in the network and the extent to which you'll 'stick your neck out' for them: the ties that bind are tighter if there are fewer ties."

Despite their ability to encourage network reciprocity, Facebook and other online social networks have been plagued by the problem of how to make money. Where is the value in a social network?

"What online social networks do is to dramatically accelerate and amplify our existing capacity to influence and co-operate with one another. And this influence is worth a lot of money," according to Lieberman.

In the recent US presidential election more than $1bn was spent by candidates trying to influence the electorate to vote in a particular way. Although the impact of a site such as Facebook has often been cited as significant, the reality is that election candidates made up only a small percentage of the total number of discussions on Facebook during the election. But while this indicates the sum total of all the influence that a site such as Facebook exerts on people is worth a lot of money, this does not always mean this value of a social network is reflected in the sale price of a social networking site, or in the site's capacity to generate revenue. This could explain why a site such as Facebook has one model of its external value, and another for its internal value – Microsoft's stock purchase valued the firm at $15bn, but Facebook's own internal valuation was just $3.7bn. But then why isn't Facebook more profitable?

"Part of the reason might be due to an economic notion called 'externality', says Lieberman. "When a company pollutes, it is often the case that they don't have to pay for the pollution they generate. By destroying a collective resource without paying for it, the company does us all a disservice. Economists call this a 'negative externality.' But companies can create 'positive externalities,' too, and social networking sites might be one example. They create all this wonderful collective resource, without really getting paid much to do it.

"It's hard to quantify the influence that people exert. Ideas are replicators, and influence makes them replicate: but when that happens, there usually isn't a birth certificate."

That's another way in which evolutionary graph theorists may have an impact. Evolutionary graph theory provides a quantitative language for describing how replicators behave on networks – and may lead to new ways of quantifying the value of influence on the web.

"Scientists are just beginning to jump into the trenches, trying to measure and quantify the spread of ideas on Facebook and other sites. But it's a long road in waters we've only begun to chart."

Friends predicted

So it may be a while before Lieberman and like-minded theorists begin making any predictions about social networks and what exactly they're evolving into. What we do know is that more measurements need to be made, spread out over the next two to five years. According to Lieberman, the only way to predict how a social network will evolve is to construct an artificial one and track the flow of ideas within it.

What is the likelihood of people forwarding on items that they receive in a social network such as Facebook (news items, links, video clips)? What is the likelihood of people responding to messages, or re-tweeting other people's tweets on Twitter?

"The idea we need to explore is this: what is the likelihood that a particular stimulus within a social network leads to a particular response?" says Lieberman.

"In my opinion, as we get better at measuring what happens within social networks, I predict a lot more organised marketing efforts on social networks as well as systematic influence campaigns."