Metcalfe's Law Refuted

pdp0x14 writes "Cnet News reports on a powerful refutation of Metcalfe's Law (that the value of a network goes up with n^2 in the number of members). The academic paper is available at Southwest Missouri State University. Basically, the thesis is that not all the links in a network are equally valuable, so Metcalfe's argument that everyone can connect to everyone (n(n-1)/2 links, roughly n^2) is irrelevant. The authors propose nlog(n) instead, a much smaller increase."

Comments

Figures.

[darth_MALL]

Anything that can be refuted...will.

Re:Figures.

[Lord Pillage]

That's a lie and you know it!

Re:Figures.

[Eryq]

Anything that can be refuted...will.

I think that opinion has been refuted.

Re:Figures.

[grumpygrodyguy]

That's a lie and you know it!

Yeah, I think we all do. CS theory is just like math or logic theories. You start with a set of reasonable assumptions and then try to deduce a theorem. It's perfectly correct to say the value of the network increases at C*(node)^2 provided that you're talking about generic nodes. I.e. they are the same.

If you're folding or SETI'ing, the nodes with water-cooled FX-55s will obviously outperform the P3-700 nodes. Or in the case of data-sharing the 100mbps connected nodes(the link between the main ISP hub and all customer hub would be considered a node) will clearly outperform the 1.5mbps nodes. But nodes of variable value were not in Metcalfe's list of assumptions, so why argue about his theorem in cases like these?

Use it for what

[Tribbin]

For what do they use this formula.

Erdos-Bacon numbers, for example.

[Masker]

Everyone knows that having a low Erdos-Bacon number is more valuable than having a high one, so the proof of this is trivial. Oh, wait, computer networks? Never mind.

"Refuted"?

[Anonymous Coward]

"Refutation" seems like almost as big an overstatement in this context as is the use of "law" to describe some wild-ass aphorism or a disagreement with it.

It's not like "value of a network" is some precisely measurable quantity.

Re:"Refuted"?

[Smallpond]

The article is misquoting. Metcalfe said something like "usefulness" of a network. The squared term is because there are two endpoints to each connection, so it makes sense that the usefulness goes up as the number of possible connections.

Re:"Refuted"?

[stupidfoo]

But MS says I can increase my ROI on my network infrastructure by using their software.

And Sun tells me that the Network is the computer!

Re:"Refuted"?

[susano_otter]

Not only that, but isn't this actually a case of "potential value" (not greater than the total number of possible connections inherent to the network - Metcalfe's Law) versus "typical usaage patterns"?

Networks are just like anything else in life. They have a maximal or optimal value, but most people don't bother trying to get full value out of them.

If Metcalfe were to say "the average mid-sized sedan seats up to five people, for which reason I value it as a five-person car", these guys would reply "yeah, but most people don't fill all five seats in their mid-sized sedans, therefore mid-sized sedans don't really seat five people after all... pwn3d!"

It's stupid. Metcalfe is talking about potential value. These guys are talking about typical utilization.

Andrew Odlyzko is godlike

[Paul Crowley]

It's a shame the summary didn't say who the authors are. Odlyzko is a Very Good Thing - he writes intelligently about everything from cryptographic number theory to making academic papers freely available online. I've long thought that n^2 was too high - though n log(n) sounds a little low...

Re:Andrew Odlyzko is godlike

[Catiline]

No, I don't think the log scale wears down.

After all, it's the high end of that curve -- e.g. the anybody-to-anybody connection of the 'net -- that brings us things like wikipedia and Linux. IMO, when you start reaching scales "beyond mortal comprehension" (or at least everyday life) the growth isn't as much being able to connect to more individuals, but being able to have more specialized groupings and network those.

Even if the average person doesn't get very connected into the network, the value can still be quite high. Never forget the "Kevin Bacon" effect.

Re:Andrew Odlyzko is godlike

[iabervon]

His economic arguments seem to neglect a number of factors in coming to the conclusion that large networks would always merge.

The first is that a single user may be a user of multiple networks; obviously, little value is created on account of a user of both networks when they merge, since the user could already communicate with all of the users. This effect can mean that two networks combined can simply cause the two network owners to share the value each of them had before (for example, the advent of VoIP means that people no longer need POTS lines, so the amount of money that can be extracted from consumers drops).

The second is that the communication value of a network may not be the reason for having it. For example, in the US, cell phones often have SMS, but it's a fragmented network. The networks don't merge, however, because SMS isn't widely used in comparison to voice service. The companies derive the greatest benefit from people paying a bit extra to get a SMS-capable phone, but using voice instead. Merging the SMS networks would increase their value greatly, but still wouldn't compare to the value of the existing universal network.

Between these two effects, the dot-com bust is predictable, especially when you realize that it happened among a userbase who could already call each other on the phone. Even if the value of a global network is huge, the ability of companies to extract that value in revenue is very limited.

The effect of spam can be seen as changing the nature of the network to a broadcast network, generally acknowledged to be worth O(n). The change is value from adding users is negated if they communicate with the network as a whole rather than individually with each (or some) of the members.

The argument based on Zipf's Law makes sense as a general rule, because an individual gets 1/k value from the kth most valuable user. On the other hand, this misses two points.

The links which would be most valuable may not be in the network yet. Adding user k+1 doesn't give only value 1/(k+1) to each user, because the new user is probably not less valuable than all of the existing users to each of the existing users. If the network already included everyone, Zipf's law would apply directly. But the total value to a user of n users out of a world of m users is (n log m)/m. If we assume that there is a constant number of people in the world and that the users of a network are randomly chosen from that pool, then the total value to any given user of that user's links is O(n), and the value of the network is O(n^2). We just have to remember that we hit a wall at the point where practically everyone is connected, and growing the population is only worth O(m log m).

The basic insight is that, if your friends are split across two SMS networks, there is a large value to you in them joining. If your friends picked SMS networks at random (or based on some unrelated consideration), this is likely to happen.

On the other hand, a network constructed by value (that is, if new users are chosen to be of high value to the existing users) is going to extract the value of a larger network at a smaller size and then grow at the O(n log n) rate in a merger. This is why AOL was of high value by itself (lots of friends and family) and the internet was of high value by itself (lots of people who collaborated), but the connection did not add all that much to either (with the primary exception of AOL users going off to college). Opposed to this is the fact that a user may get a different set of high-value links by having new needs; picking up a new hobby will radically improve the values of a set of previously low-valued links, and, to a certain extent, reshuffle the selection of users on the network.

So my estimation is that there are several flaws with the essentially correct O(n^2) idea: separate networks get extra total value out of duplication, at the expense of the users; all networks, even with different properties, compete with each other; it's limited and

It's harder than that...

[Cantide]

More like (n-k)log(n-k) where k is the frequency coefficient of That Big Dumb Guy Who Has Nothing Useful to Say.

Re:It's harder than that...

[yotto]

More like (n-k)log(n-k) where k is the frequency coefficient of That Big Dumb Guy Who Has Nothing Useful to Say.

Actually, would't that be (n-2k)log(n-2k)? Each big dumb guy who has nothing useful to say has to be talking to someone who would otherwise be productive.

The real Metcalfe law

[Rosco P. Coltrane]

You can read this law like this:

"hello, I'm Robert Metcalfe. I state that the value of a network grows exponentially to the number of nodes present in it. So the more nodes you have, the better your network. Oh, and incidentally, I'm the CEO of 3Com, a company that sells network cards..."

misattribution

[Anonymous Coward]

The link that the submission attributes to Southwest Missouri State University is actually at the University of Minnesota... (Not terribly surprising, given that Odlyzko is at the University of Minnesota!) Please correct the article accordingly.

Example: AOL

[suso]

Number of members: Millions
Value: Debatable

suso.org website/email hosting, no disk space quotas and personalized support.

Smaller Networks Win Out

[MankyD]

The last paragraph makes a very interesting point:

When two networks merge, "the smaller network gains considerably more than the larger one. This produces an incentive for larger networks to refuse to interconnect without payment, a very common phenomenon in the real economy," the researchers conclude.

Assuming their research holds true, adding 100 computers to 100,000 computers is pretty worthless for a big network - they get only a small gain compared to their starting value. The small network, on the other hand, has huge amounts compared to where they started.

It's common sense, of course, but worth taking note of.

Re:Smaller Networks Win Out

[AnotherBlackHat]

While it's true that an individual user of the smaller network sees a bigger increase than a user on the larger network,
the total value of the larger network increases more.

Assuming a value of N log(N);

Value of 100,000 is 500,000
Value of 100 is 200
The value of 100,100 (the two together) 500,543

Increase in value per node for larger; 0.00543
Increase in value per node for smaller; 3.00543

Total increase across larger network 543
Total increase across smaller network 300

-- Should you believe authority without question?

In other news...

[barfy]

Powerful refutation of Murphy's Law! It has been determined that not everything thing that *can* go wrong *does* go wrong. Using the Apollo 13 mission as a case study, it has indeed been shown that only a small fraction of the things that could have gone wrong indeed did go wrong.

NASA Scientists have now recast murphy law as, "There are a lot of things that can go wrong. Some of them might happen." Which, of course, shows that far fewer things go wrong than previously thought.

Scientists predict that this will have no effect on the size or scope of any government project or agency.

No need to go that far.

[uberdave]

Slashdot itself is a good counter-example.

And what other "laws" will be changing?

[Vancouverite]

Now that researchers realize that the so-called laws of computing are not rigorously formed, what else will be subject to attack?

Will we see Moore's law reduced to a log-based function as well? Will Brooks' Law be shown to be fallacious, leading to a large upsurge of temporary IT jobs? And how about Godwin's Law. Will we no longer have to fear the inevitability of Nazis or Hitler?

What will this all lead to... nothing but anarchy. Anarchy, I tell you!

Annecdotal Support

[VoidPoint]

I was happily working on a project when my manager assigned two more people to the team, making us three in number. I'm John, I've got it all figurted out and would have finished the product. I now work with Bob. Bob talks too much. Always coming to me with silly questions and he never seems to quite "get it". I also now work with Tom. Tom is never available, he never answers his phone, and I swear he's cutting out at three on Fridays. I know you've been in this situation as well. We're a network, which I'd hardly refer to as peer-ro-peer. Our bandwidth may not be comparable to the study, but the general theorem is the same.

Why call it a law, exactly?

[Gothic_Walrus]

I was a bit confused about the story at first, and a quick Google define proved that I had reason:

"A statement that summarizes the results observed in an experiment that is repeated many times by many different scientists. A scientific law is widely accepted as true or as a fact." -- Source

"A general principle or rule that is assumed or that has been proven to hold between expressions." -- Source

This can't be a law. It's been proven wrong, and unless I'm mistaken, it was never proven to be correct in the first place.

Why use the word law, then? Is it a misuse of the word? Generalizing? An attempt to confuse stupid Slashdotters like me? :)

Isn't this the same Metcalfe...

[Slartibartfast]

- who said that Linux sucks, and would die years ago
- who predicted the Internet would implode... years ago
- whose ego far outpaces his abilities?

[Check old columns in InfoWorld, c. 2000, for details.]

Granted -- he did some good stuff. But the truly good stuff he's done was so long ago that the only meaning it has in contemporary terms is a resume line item. Now he's just another VC talking head, with ego to match; to find that one of his "laws" doesn't hold water is about the same as saying that SCO's legal team isn't always on the level.

Odlyzko's Arguments are Good

[filmmaker]

Especially the section on Zipf's Law.

Where I think Metcalf's Laws does apply is in an information network where no proprietary secrets exist. For instance, searching for technical documentation or a movie star's biography. In these instances, the value of the network, as measured by the immediacy with which one could obtain useful information by asking a question, is proportional to something on the order of n*n for n nodes.

Consider the network the top 10 search results in Google for all possible queries. Let's pretend for a moment that Google wasn't polluted with Spam. In this case, each node (search result) is providing a substantial amount of value to the network, although no matter how small or targeted the group, Zipf's Law will be observable to a degree.

Or consider if you had personal tele-access to every person on the planet and could ask any one of them a question at any time. Clearly here the value of the network is something on the order of n*n.

Most or all of Odlyzko's examples presupposed economic interests or constraints.

Lesson of usenet--Value? What value?

[shanen]

Consider the usenet as a kind of asynchronous network. Consider the participants as nodes that connect and disconnect at random. Now consider the result. The value has *NOT* increased along with the number of nodes. Instead, the SNR became very small, and my belief is that the current SNR is negative, at least on average. There is still some good information to be found in pockets, but there is plenty of misinformation, too, and *LOTS* of noise.

I think the decisive factor is that the fanatical propagators of misinformation must be aware (at some level) that they are fighting against reality--but their response is to shout louder and more frequently, simply repeating their misinformation. Are they hoping that lies repeated enough times will somehow become true? Or they just hope to bury the truth they hate?

Scarcely matters. The result is obvious, and the same phenomenon seems to be overtaking the WWW, too. Doesn't do a lot of good to connect to the network when all the sites are basically put on the same level by the constraints of HTML, but most of them are full of propaganda of various stripes.

But you're forgetting Hulk's Law

[gelfling]

Which says: You Make HULK AnnnnnGRRyyyyyy!!!!!! ARRRRRRRRGGGGG!!!!!