{"id":7460,"date":"2017-03-28T16:16:44","date_gmt":"2017-03-28T20:16:44","guid":{"rendered":"http:\/\/esr.ibiblio.org\/?p=7460"},"modified":"2017-03-28T17:23:39","modified_gmt":"2017-03-28T21:23:39","slug":"odlyzko-tilly-raymond-scaling","status":"publish","type":"post","link":"http:\/\/esr.ibiblio.org\/?p=7460","title":{"rendered":"Odlyzko-Tilly-Raymond scaling"},"content":{"rendered":"<p>I&#8217;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.<\/p>\n<p>I&#8217;m posting it here because I think my blog regulars cast a wide enough net to tell me if I&#8217;ve merely rediscovered a thing in the existing literature or, in fact, nobody quite got here before.<\/p>\n<p><!--more--><\/p>\n<p>Back in the naive days of the dot-com boom people used to talk about Metcalfe&#8217;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.<\/p>\n<p>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.<\/p>\n<p>You can <a href=\"http:\/\/www.dtc.umn.edu\/~odlyzko\/doc\/metcalfe.pdf\">read the Odlyzko\/Tilly paper here<\/a>. It&#8217;s good; it&#8217;s lucidly written and deserves its status as a seminal classic. The <em>explanation<\/em> 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 &#8220;gravity law&#8221; 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.<\/p>\n<p>After Odzylko\/Tilly, complexity theorists looked at real-world networks and found that they frequently evolve towards a topology that is <em>self-scaling<\/em> or <em>fractal<\/em> &#8211; 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 &#8211; over and over, we find self-scaling nets anywhere evolution is trying to solve optimal-routing problems.<\/p>\n<p>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 <em>equal<\/em>, 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.<\/p>\n<p>To see why, we need to recognize a new concept of the &#8220;access cost&#8221; 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 &#8211; distance, hop count, whatever.<\/p>\n<p>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.<\/p>\n<p>That&#8217;s it. Same result as Odlyzko\/Tilly but with weaker assumptions. Put their case and my case together and you have this:<\/p>\n<p>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.<\/p>\n<p>Is this in the literature anywhere? If not, I guess it&#8217;s worth my time to do a more formal writeup.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>I&#8217;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&#8217;m posting it here because I think my blog regulars cast a wide enough net to tell me if I&#8217;ve merely&hellip; <a class=\"more-link\" href=\"http:\/\/esr.ibiblio.org\/?p=7460\">Continue reading <span class=\"screen-reader-text\">Odlyzko-Tilly-Raymond scaling<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9],"tags":[],"class_list":["post-7460","post","type-post","status-publish","format-standard","hentry","category-technology","entry"],"_links":{"self":[{"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/posts\/7460","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=7460"}],"version-history":[{"count":3,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/posts\/7460\/revisions"}],"predecessor-version":[{"id":7463,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/posts\/7460\/revisions\/7463"}],"wp:attachment":[{"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=7460"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=7460"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=7460"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}