Popularity-Driven Networking
E. Ben-Naim and P. L. Krapivsky
We investigate the growth of connectivity in a network. In our model,
starting with a set of disjoint nodes, links are added sequentially.
Each link connects two nodes, and the connection rate governing this
random process is proportional to the degrees of the two
nodes. Interestingly, this network exhibits two abrupt transitions,
both occurring at finite times. The first is a percolation transition
in which a giant component, containing a finite fraction of all nodes,
is born. The second is a condensation transition in which the entire
system condenses into a single, fully connected, component. We derive
the size distribution of connected components as well as the degree
distribution, which is purely exponential throughout the
evolution. Furthermore, we present a criterion for the emergence of
sudden condensation for general homogeneous connection rates.
source,
ps,
pdf