Preferential attachment with partial information

Abstract

We propose a preferential attachment model for network growth where new entering nodes have a partial information about the state of the network. Our main result is that the presence of bounded information modifies the degree distribution by introducing an exponential tail, while it preserves a power law behaviour over a finite small range of degrees. On the other hand, unbounded information is sufficient to let the network grow as in the standard Barabási-Albert model. Surprisingly, the latter feature holds true also when the fraction of known nodes goes asymptotically to zero. Analytical results are compared to direct simulations.

References in corpus (5)

• Power-law distributions in empirical data
• Geographical dispersal of mobile communication networks
• Scale-free network growth by ranking
• Scale Free Networks from Self-Organisation
• The power of choice in network growth