Eur. Phys. J. B (2015) 88: 18
https://doi.org/10.1140/epjb/e2014-50595-0

Regular Article

Preferential attachment with partial information

Department of Mathematics and Namur Center for Complex Systems – naXys, University of Namur, rempart de la Vierge 8, 5000 Namur, Belgium

^a e-mail: renaud.lambiotte@unamur.be

Received: 3 September 2014
Received in final form: 20 October 2014
Published online: 14 January 2015

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.