Growing Powerlaw Networks

I note two other processes that grow a power-law distribution in Newman’s survey paper. The first is a variation of the preferential attachment model. I think of that as a shopping model. New nodes shop for what to connect to. The first of these two models has a different method of shopping.

The alternate shopping model fixes a problem with the preferential attachment model. If you look at the simulation for the preferential growth model it works by drawing a random existing connection and them mimicking that. This is not really credible. The new nodes don’t have a view of the set of all the existing connections to draw upon. Newly arriving nodes presumably can only see some local region of the network.

The alternate shopping model replaces the random draw with a bit of search. The new node starting from a random existing node proceeds to either continue searching (shopping) at a neighbor of that node or it stops shopping and mimics a connection on at that node. Each round of the search has some chance of terminating v.s. iterating. Like the preferential attachment model this shares a random draw from the universe of the whole graph. I’m particularly pleased because simulations of this model can easily be modified to include other attributes of the nodes the shopping visits – i.e. merit.

The second model might be called the acquisition model. Newman reports that if create a network by randomly adding edges between random nodes there comes a time when the network very quickly becomes entirely connected. They call that a phase transition. As we approach the phase transition the nodes form a slurry of components of various sizes. The distribution of these sizes is power-law. I think of that as an acquisition model because it mimics to a degree what happens in as an industry matures. At first there are numerous small entrants into the industry each solving local problems. Later as the industry becomes more standardized these firms begin to merge. This model helps to suggest why we see a power-law distribution of firm sizes in many industries. Industries that complete the phase transition become monopolies.

I particularly like this model because it helps to inform my thinking about what happens when one of the Porter’s barriers to a industry consolidationis eliminated.

Leave a Reply

Your email address will not be published.