Growing Networks Through Random Walks Without Restarts

Abstract : Network growth and evolution is a fundamental theme that has puzzled scientists for the past decades. A number of models have been proposed to capture important properties of real networks. In an attempt to better describe reality, more recent growth models embody local rules of attachment, however they still require a primitive to randomly select an existing network node and then some kind of global knowledge about the network (at least the set of nodes and how to reach them). We propose a purely local network growth model that makes no use of global sampling across the nodes. The model is based on a continuously moving random walk that after $s$ steps connects a new node to its current location, but never restarts. Through extensive simulations and theoretical arguments, we analyze the behavior of the model finding a fundamental dependency on the parity of $s$, where networks with either exponential or a conditional power law degree distribution can emerge. As $s$ increases parity dependency diminishes and the model recovers the degree distribution of Barabási-Albert preferential attachment model. The proposed purely local model indicates that networks can grow to exhibit interesting properties even in the absence of any global rule, such as global node sampling.
Type de document :
Communication dans un congrès
Proceedings of the 7th Workshop on Complex Networks (CompleNet 2016), Mar 2016, Dijon, France
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger
Contributeur : Giovanni Neglia <>
Soumis le : mardi 13 décembre 2016 - 14:31:36
Dernière modification le : samedi 27 janvier 2018 - 01:31:41
Document(s) archivé(s) le : mardi 14 mars 2017 - 12:22:15


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01413647, version 1



Bernardo Amorim, Daniel Figueiredo, Giulio Iacobelli, Giovanni Neglia. Growing Networks Through Random Walks Without Restarts. Proceedings of the 7th Workshop on Complex Networks (CompleNet 2016), Mar 2016, Dijon, France. 〈hal-01413647〉



Consultations de la notice


Téléchargements de fichiers