Odlyzko-Tilly-Raymond scaling

I’ve been ill with influenza and bronchitis for the last week. Maybe this needs to happen more often, because I had a small but fundamental insight into network scaling theory a few minutes ago.

I’m posting it here because I think my blog regulars cast a wide enough net to tell me if I’ve merely rediscovered a thing in the existing literature or, in fact, nobody quite got here before.

Back in the naive days of the dot-com boom people used to talk about Metcalfe’s Law: the value of a node of n networks scales as O(n**2). This heuristic drove a lot of the early excitement about Internet-related stocks.

But then the boom busted, and in 2006 along come Odlyzko and Tilly to explain that. What they said is: empirically, networks actually seem to top out at O(n log n) value, and this is superlinear but way lower than O(n**2), and thus dot-com boom fall down go bust.

You can read the Odlyzko/Tilly paper here. It’s good; it’s lucidly written and deserves its status as a seminal classic. The explanation of O(n log n) that the authors give is that in a world where not all connections have equal value, people build only the connections with the best cost-benefit ratio, and due to an effect called the “gravity law” the value of traffic between any two nodes falls off superlinearly with distance. This produces a substantial disincentive to build long-distance links, leading to a network of clusters of clusters with O(n log n) link density and value scaling.

After Odzylko/Tilly, complexity theorists looked at real-world networks and found that they frequently evolve towards a topology that is self-scaling or fractal – clusters of clusters at any scale you examine. Circulatory systems in the body, neural networks in the brain, road and rail networks in human cities, the Internet itself – over and over, we find self-scaling nets anywhere evolution is trying to solve optimal-routing problems.

So here is my small stone to add to the Odlyzko/Tilly edifice: their assumption in 2006 was stronger than it needed to be. You still get selective pressure towards an O(n log n) self-scaling network even if the cost of connections still varies but the value of all potential connections is equal, not variable. The only assumptions you need are much simpler ones: that the owner of each node has a finite budget for connection-building small in relation to the cost of providing links to all nodes, and that network hops have a nonzero cost.

To see why, we need to recognize a new concept of the “access cost” of a node. The value of a node is by hypothesis constant: the access cost is the sum over all other nodes of any cost metric over a path to each node – distance, hop count, whatever.

in this scenario, each node owner wants to find the best links to the network, but the valuation minimizes access costs . Under this assumption, everyone is still trying to solve an optimal routing problem, so you still get self-scaling topology and O(n log n) statistics.

That’s it. Same result as Odlyzko/Tilly but with weaker assumptions. Put their case and my case together and you have this:

The value of a network of n nodes will rise as O(n log n) under the following assumptions: (a) node hops have variable costs, and (b) each node owner has a small budget.

Is this in the literature anywhere? If not, I guess it’s worth my time to do a more formal writeup.