Evaluación de la longitud media de caminos aleatorios en redes con ley de potencias (Estimation of the Average Search Length of Random Walks in Power-Law Networks)

Luis Rodero-Merino (lrodero@gsyc.es)1, Antonio Fernández (anto@gsyc.es)1, Luis López (llopez@gsyc.es)1, Vicent Cholvi (vcholvi@lsi.uji.es)2

1Universidad Rey Juan Carlos
2Departamento de Lenguajes y Sistemas Informáticos, Universitat Jaume

This paper appears in: Revista IEEE América Latina

Publication Date: Oct. 2007
Volume: 5,   Issue: 6 
ISSN: 1548-0992

In this paper we introduce a model to study random walks in power-law networks with one-hop replication. Basically, this model gives a set of expressions that captures how the knowledge about the network evolves as the random walk traverses the network: how many nodes have been known, either because they or their neighbors have been visited by the random walk. With this, we obtain an expression that gives a good estimation of the average number of hops needed to find some random peer from any other random peer. We denote this metric the average search length, and we deem it can be very useful to evaluate random walk based resource location solutions in P2P networks.

Index Terms:
networks, power-law, random-walks, model, search length.   

Documents that cite this document
This function is not implemented yet.

[PDF Full-Text (686)]