Effect of coagulation of nodes in an evolving complex network

The authors focus on scale-free networks,

with reference to Moore et al’s model which includes annihilation of nodes. They analyze a Japanese business relationship network. Companies are born, grow, die, and merge. Firms have (observed and measurable) preferential attachment to firms with higher degree.

(a) The three basic processes. (b) Time evolution of the number of links. (c) LIfetime and average degree. (d) Cumulative distribution of the number of links, with c=0 (orange) to c=0.5 (blue).

The cumulative distribution of company lifetimes is exponential P(\geq t) \propto \exp(-t/\tau), where \tau=18.8 years. (we see similar patterns in speciation). A semi-log plot shows degree grows exponentially with lifetime, where expected degree is \exp(At) and $A=0.017$.

This suggests the degree distribution should be power-law with exponent 1/A\tau, or 3.1. The observed degree distribution has exponent 1.3. Conclusion: random annihilation and growth by preferential attachment do not explain the real world.

To explain this, the authors turn to coagulation models of aerosols and colloids; the mass of these clouds follows a power law. They propose a model where network nodes can merge. More specifically, starting with N nodes, evolve the network by stochastically choosing annihilation, creation, or coagulation at each time step, with probabilities a, b, c (b=a+c=0.5). With 10^5 nodes, the model converges after 10^7 iterations, suggesting one year in the real world == 10600 iterations.

They show, both analytically and by simulation that the coagulation probability controls the final shape of the degree distribution. Small c gives an exponential distribution, large c gives power law.

Phys. Rev. Lett. 108, 168701 (2012) Effect of Coagulation of Nodes in an Evolving Complex Network. Wataru Miura, Hideki Takayasu, and Misako Takayasu


Posted on June 20, 2012, in networks, papers and tagged , . Bookmark the permalink. 1 Comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: