A network future for web advertising

Ideas from a meeting on Complex Networks, 2-6 July, Sardinia, Italy

Andrei Broder, vice-president of emerging search technology at Yahoo, gave a nice talk this morning on the nature of web advertising and where it's going. It seems that network science is likely to play an influential role -- supporting the emergence of a powerful version of "algorithmic" advertising -- just as it has in web search.

Classic advertising, Broder pointed out, tends to work either by building image and brand -- counting on long-term allegience from consumers -- or by making more specific appeals to "act now" (say, by offering discount coupons). You find these all over the web, of course, as in ordinary print media or television, but what's different in the web is the incredible speed and volume. Whereas advertisers used to do surveys and think hard about where to place what kind of ad, increasingly the approach has to be algorithmic -- you need software to make decisions and place ads on a second-by-second basis, and to adapt rapidly to how consumers respond.

Learning to do this well (effectively bringing customers into contact with ads for things they realy want) is a big challenge, and systems today make lots of mistakes. Broder mentioned, for example, a recent New York Times article on the Lewis Libby affair, where ads showed up on the page for Libby Shoes, not exactly the connection for which the advertisers were presumably hoping. How to do this better? Broder suggests that a sophisticated mathematical/computational approach using complex network science may be the solution.

Web search was revolutionized by the PageRank algorithm, which makes vclculations on the entire network of linked pages in order to assign an "importance" to any one page. In the case of advertising, you can imagine an abstract network, where the links correspond to a trio of 1) user (the consumer), 2) the context (the web page) and 3) the advertisement. Based on historical data (which a company like Yahoo! can collect at the level of something like 10^12 points) you can (in principle) build this graph, adding edges for each trio where something positive happened (a click through). Then use this data, and do network analysis to try to predict other trios where you're likely to find success again.

I'm sure this kind of work will yield results pretty quickly, and I bet those Libby Shoes ads start finding more relevant outlets. The interesting thing, to me at least, is how rapidly the (online) advertising community has become quite sophisticated in a mathematical sense. This community has been taken over and driven by computer scientists, physicists and mathematicians -- but it also depends for success on a really new interaction between scientific disciplines, qhich is the only way to get the mathematics and algorithms to interact successfully with human psychological habits.

Learn about networks

Italian physicist Guido Caldarelli has an excellent new book out on networks. It's not exactly for the non-technical, but for anyone who really wants to learn the mathematical nuts and bolts of network theory, and to come to terms with degree distributions, adjacency matrices, clustering coefficients and the like.

If you want the more qualitative picture, you might begin with my Nexus (or either of two other popular books on the topic, Laszlo Barabasi's Linked or Duncan Watts' Small Worlds), but Guido's book is the first, to my knowledge, to put all the necessary technical information in one book that should appeal to technically-minded students interested in network science.

Damaging deliberations

Ideas from a meeting on Complex Networks, 2-6 July, Sardinia, Italy

In one of my recent New York Times columns, I explored the worrying polarization evident between the conservative and liberal bloggers in the US. I argued that it might well be the almost mechanical outcome of an amplifying feedback driven by simple psychological factors that influence how people form opinions and attitudes. First, the psychological phenomenon of “cognitive dissonance” tends to make us more comfortable with view that confirm rather than contradict our own. Second, people also have a strong tendency to adopt, even unconsciously, the attitudes of those with whom they interact. So the more conservative or liberal bloggers read the views in their own sphere, the more they're drawn into that sphere, express similar views, and end of living in an intellectual world of views that merely confirm their own.

That was speculation. But there's some exciting recent work that I think supports it -- some from network theorists here in Sardinia who are looking, rather abstractly, at the mathematics of opinion change within groups, and some from lawyers trying to address, in practical terms, how we might heal our polarization with greater deliberation. The lesson, I think, is that we had better be quite careful in what we do, or we could make the matter even worse.

Yesterday, physicist Renaud Lambiotte of the University of Liege in Belgium talked about his recent work (with physicists Marcel Ausloos and Janus Hoylst) in modeling the evolution of opinions. Their modeling suggests that two groups holding opposing views may quickly become reconciled, or remain at odds, and that what happens --and this is the important point -- can be very strongly influenced by the presence or absence of only a few social links between the groups. Here's the basic idea.

They supposed that individuals hold one of two opinions (it's not hard to think of some relevant issue), assigned randomly at the start. People in the model would then change their views, step by step, by a “majority rule” – each person would adopt (in the next time step) the opinion held by a majority of those with whom they were linked in the social network. The interesting thing to explore is how the structure of the network influences what ultimately happens.

Lambiotte and colleagues started by imagining two groups that were isolated from one another, or nearly isolated. Not surprisingly, perhaps, they found that people within each group quickly came to share one opinion. The groups came to a consensus, although the two groups were as likely to agree as disagree with each other. But the researchers then began adding social links between the groups, to see how this might change the outcome.

They found no change, at first, as the two groups continued to form opinions independently. But rather than a gradual increase in the way opinions “leak” from one group to the other as more connections are added, the researchers found a surprise when the number of links between the groups reached a precise threshold. Abruptly, the final opinions of the two groups were now always identical. Even a few extra links between groups were enough to “tip” their final opinions from a state of full polarization to full agreement.

This finding represents the social equivalent (in this simple model) of what physicists call a "phase transition", closely akin to the abrupt transformation of liquid water to ice. The interesting thing is that the change from one outcome to the other isn't gradual, but very rapid, and happens at some critical threshold of links between the groups. Near this boundary, a tiny alteration of the network structure can lead to drastic consequences.

Now this is quite abstract, but it may still be highly relevant to the real world. A number of studies have noted increasing polarization in recent years, not only in the web, but in geographical zones as well, with some parts of the US, for example, becoming more homogeneously conservative or liberal. Legal academics have been concerned with the consequences of this trend for our democratic discourse, and ability to come to collective decisions. What can we do?

Some legal theorists have suggested that one way to counter this trend would be to have special "deliberation days", during which people would come together in "town hall" meetings to discuss key issues. But some experiments carried out by Cass Sunstein and colleagues at the University of Chicago suggest that he outcome of such meetings can be counterproductive.

They had both liberals and conservatives from different cities in Colorado come together to discuss contemporary issues (gay marriage, the Iraq war, and so on) for a day, using surveys to gauge their views both before and after the deliberations. The liberals discussed issues among themselves, in one group, as did the conservatives, in another. What they found is that both groups became more extreme in their views during the discussions, and that the distance between the two groups became larger as a result. The conservatives became more conservative, and the liberals more liberal.

The lesson of these experiments is that those intermediary links between groups are absolutely essential to building overall consensus, and that, in their absence, we should expect an evolution toward greater extremism. But the more encouraging lesson from the network theory of Labiotte and colleagues is that only a few links between such groups can be remarkably successful in breaking down such polarization. Even if the situation seems bleak, and unchangeable, it may take only a few more contacts to seed a tremendous change.

Predicting epidemics

Some ideas from a meeting on Complex Networks, 2-6 July, Sardegna, Italy

With the threat of a global outbreak of the H5N1 virus hanging over our collective heads, it's natural to wonder about our science of prediction. We can send satellites into the remotest regions of the solar system, and predict some quantities of fundamental physics to one part in 10 billion. Boeing aircraft designs its new aircraft with computational simulations so accurate that test flights are no longer necessary; in fact, as one of their executives told me last year, Boeing only does flight tests to reassure an uneasy public! Given the power of today's science, shouldn't we be able to predict the likely outcome of a new viral outbreak?

One possible response is that we shouldn't hope to be so ambitious, because the spread of disease depends not only on biological factors -- the nature of the virus, for example -- but on what individual people do, on who meets with whom and where people travel. It's deeply entangled with free will and human psychology and all the unpredictability of human behavior, and so we shouldn't be surprised if the fate of an epidemic is a matter if chance and guesswork. But is the situation really so hopeless? Increasingly, network scientists don't think so. It's may just be a matter of bringing the right data to bear, and paying attention to the surprising architecture of real-world networks -- such as the network of international air travel.

The fact is that people aren't so unpredictable, especially at the collective level, and technology is making it possible to map out human interactions with more detail than ever before. Using mobile phones, for example, researchers have been able to build up detailed pictures of the social links between people in various communities. A couple years ago, researchers at Los Alamos National Lab used information gathered this way (and from more traditional surveys) to build a computational model that could mimic the evolution of an epidemic within a city by following the second-by-second movements of millions of individuals on their daily paths. This is the social equivalent of Boeing's flight simulations. With this computational tool, you can do experiments to test the consequences of various interventions. What happens if you close the schools, perhaps, or try to reduce the movement of people by public transport? One thing the Los Alamos group found was that the timeliness of the response is absolutely crucial -- measures save many more lives if they're implemented very early on in the course of the epidemic.

Yesterday morning, physicist Alessandro Vespignani spoke about recent work with Vittoria Collizza and other members of his group at the University of Indiana, which has been aiming to bring data on international air travel into such models, which is probably the most important factor for epidemic spread at the global level. They've used a massive data set for something like 3,100 airports worldwide, and 20,000 regular flight paths (you can see some animations of such data here), which reveal the larger-scale human flows around the world. Using this data to then model the spread of a disease -- introduced at one point, say, in Vietnam.

This modeling effort is the most ambitious yet to try to bring the data we have to bear on understanding what we're likely to face with an influenza pandemic. The first surprise that emerges from it is that trying to control the epidemic by reducing the flow of people -- taking the obvious step of restricting traffic through all airports, for example -- is remarkably ineffective. Even reducing the number of people passing through airports by as much as 50% has virtually no effect on the ultimate spread of an epidemic. To have much influence, the models suggest, authorities would have to reduce airport traffic by as much as 90% everywhere -- which from an social and economic point of view is probably a non-starter.

This may be a negative lesson, but at least it helps authorities know what NOT to waste their efforts on. A more positive message that emerges from this work is that the cooperative sharing of antiviral drugs between countries may well be the best way to the stem the spread of such a disease. (Unfortunately, I have to wonder, how likely is that?)

One other interesting point to emerge from this recent work (discussed more in this paper) is that the outcome of an epidemic may well be more predictable than one might expect. They've run their simulations over many times, seeding an epidemic with the same initial conditions. Although the simulations include lots of probablistic events (it depends on the virus passing between people, after all, which are chancy events), the overall outcome remains roughly the same. The reason, they suggest, is that the global air transport is dominated by channels going between major airports. These seems to act as preferred pathways or conduits along which the virus tends to travel -- and obviously represent good targets for, say, monitoring people for infection (if feasible).

This work obviously has huge implications for our collective well being. But it also makes the point that understanding social processes, especially at the largest collective level, isn't really hampered at all by the mysteries of human psychology. In many ways, we're akin to particles following fairly simple rules, and careful science can learn how to follow and hopefully influence those movements in an intelligent way.

Complex Networks, 2-6 July, Sardinia, Italy

Even at 8 a.m., the sun is blazing hot outside, although it's cool and calm here in the Edificio II of Sardegna Ricerche, a hulking Soviet-style research building in the beautiful mountains near Cagliari, Sardinia. I'm at a satellite meeting of the yearly meeting on Statistical Physics. This satellite (graciously organized and hosted by Alessandro Chessa of the University of Cagliari and Guido Caldarelli of the University of Rome) is focussing on complex networks -- things like social networks, the Internet, food webs, and so on. This is a hot topic in physics, indeed, all of science, and something on which I wrote a book several years ago.

If you look at the physical layout of the Internet (computer linked by telephone lines or satellite links), or the wiring pattern of neurons in the human brain, or the tangled web of social bonds that links together a community (in the image to which I've linked, these are friendships between high school students), you'll see in each case what looks like an unintelligable mess. You'd see the same bewildering complexity in the network of predator-prey relationships in any ecosystem, and in many other settings -- in networks of economic trade, for example. But in fact these and many other natural networks, despite their apparent complexity, possess a hidden order and share deep architectural similarities.

Physicists and mathematicians over the past decade have begun learning how to understand the architecture of such networks, and to build up a real science that explains how and why they have the structures they do. In my book Nexus (or Small World, in the UK) I tried to offer a snapshot of this recent explosion of research.

But lots of work has happened since then, and its seems this exploding field attracts more attention every year, mainly because computers have made it possible to gather and analyze the huge amounts of data that make it possible to map out real world networks. Research on social networks is particularly important, and is showing that the human world often follows precise mathematical patterns that were unsuspected only a few years ago. Over the next few days, I'll try to report on some of the major interesting developments in this field.

Recently in this blog, I've tended to focus on the psychologial side of the social atom -- on the behavior of people as individuals and what influences it. This conference represents work on the other side -- looking at the mathematical patterns that emerge at the larger scale.