More random graph theory on the web

Picking up an earlier thread, I went looking for papers on non-uniform random graphs, that is to say, connected networks where some members have many more connections than others, but that's about all we know. I turned up an interesting one by Fan Chung and Linyuan Lu describing the characteristics of graphs more like ones you'll find in the context of the web.

In particular, social networks and others commonly encountered appear to follow a power law, meaning that, for some particular number b, there are roughly b times as many people with n connections as there are with n+1. In social networks, b tends to be between 2 and 3, so for example there might be around 1000 members with just one connection, 500 with two, 250 with three, and so on to only a handful having eight or more.

Chung and Lu show that under such conditions, there will very likely be a core of closely connected people, that two people chosen at random will very likely be close to each other, but there will also be some significantly less-connected members. Connecting two people outside the core will generally take considerably more steps than connecting most pairs of people.

So: six degrees of separation (or whatever it really is) in most cases, but considerably more in a few cases.

The vague terms like "very likely," "some" and "significantly" have precise mathematical definitions. The details are in the paper if you're interested.

On a recent plane flight, I looked at the route map to see if the airline's network behaved like a social networking graph. Airline networks are specifically designed to connect destination cities well but as cheaply as possible, keeping in mind that cost depends on a number of complex factors. In particular, you want to minimize the number of stops needed to get from point A to point B.

Did the airline's network follow a power law? It did, but only up to a point. Most cities had only a single connection. Fewer had two and about the same proportion fewer had three. And then there were the two hubs, each with dozens of connections. There was nothing in between. You could get from almost anywhere in the network to almost anywhere else by flying to a hub and then on to the final destination — not a big surprise.

The interesting thing is that airline networks specifically don't behave like social networks, precisely because social networks tend to leave some members out in the cold and in air travel, that just won't do. It may be worthwhile in many cases to emulate some naturally-arising structure, but it's not always the best choice. Sometimes you actually have to plan.