HowNetworksScale

Now for some interesting network tricks.

Erdos & Renye showed one of the first in 1956. (Suppose http://citeseer.ist.psu.edu/context/134543/0) Suppose) you start with a network containing many nodes but no connections. Then, begin adding arbitrary links at random.

How many random links do you need to have before most of the nodes are connected?

The answer is shown here :

http://www.nooranch.com/synaesmedia/ec/graph1.gif

In the graph, the horizontal axis represents the ratio of arcs to nodes, while the vertical axis represents the average size of the largest connected group of nodes. What is important to notice is that there is a short transition phase between very the largest group being quite small, to the majority of nodes being conneected; which happens as extra arcs are added.

Now this is an abstract property of networks in general. But it is one which can have dramatic practical implications. In particular many people have realized that it can be very pleasant if you can find a network shaped business opportunity where

• a) your cost is proportional to the cost of adding arcs, and

• b) the value generated (from which you can skim some kind of revenue) is a function of the number of connected people.

The classic example is a telephone system. Each new customer costs the telephone company the price of an extra arc. But the value of the network grows with the number of connected people.

Some caveats. Catching the beginnings of the right S-shaped curves is the equivalent of finding the goldmine; but that doesn't mean that every hair-brained, dumb-assed scheme with a network involved actually has the right characteristic!.

In fact there are lots of reasons such as scheme might not work.

• The market might already be at the wrong end of the S-curve, where growth in absolute size is slowing relative to each new arc added.

• The value of the network as a whole might not be a good function of the number of connected people. (ValuingNetworks next)