2024-03-29T04:44:42Zhttps://repositori.uji.es/oai/requestoai:repositori.uji.es:10234/1618842023-11-03T12:29:47Zcom_10234_7038com_10234_9col_10234_8634
Repositori UJI
author
López Millán, Víctor M.
author
Cholvi, Vicent
author
Fernández Anta, Antonio
author
López, Luis
2016-07-22T11:28:43Z
2016-07-22T11:28:43Z
2016
1389-1286
http://hdl.handle.net/10234/161884
http://dx.doi.org/10.1016/j.comnet.2016.04.008
The problem of finding a resource residing in a network node (the resource location problem) is a challenge
in complex networks due to aspects as network size, unknown network topology, and network
dynamics. The problem is especially difficult if no requirements on the resource placement strategy or
the network structure are to be imposed, assuming of course that keeping centralized resource information
is not feasible or appropriate. Under these conditions, random algorithms are useful to search the
network. A possible strategy for static networks, proposed in previous work, uses short random walks
precomputed at each network node as partial walks to construct longer random walks with associated
resource information. In this work, we adapt the previous mechanisms to dynamic networks, where resource
instances may appear in, and disappear from, network nodes, and the nodes themselves may leave
and join the network, resembling realistic scenarios. We analyze the resulting resource location mechanisms,
providing expressions that accurately predict average search lengths, which are validated using
simulation experiments. Reduction of average search lengths compared to simple random walk searches
are found to be very large, even in the face of high network volatility. We also study the cost of the
mechanisms, focusing on the overhead implied by the periodic recomputation of partial walks to refresh
the information on resources, concluding that the proposed mechanisms behave efficiently and robustly
in dynamic networks.
eng
© 2016 Published by Elsevier B.V.
Resource location
Dynamic networks
Random walks
Complex networks
Resource location based on precomputed partial random walks in dynamic networks
info:eu-repo/semantics/article
TElDRU5DSUEgREUgRElTVFJJQlVDScOTTiBOTyBFWENMVVNJVkEKCkFjZXB0YW5kbyBlc3RhIGxpY2VuY2lhLCB1c3RlZCAoZWwgYXV0b3IvZXMgbyBlbCBwcm9waWV0YXJpby9zIGRlIGxvcyBkZXJlY2hvcyBkZSBhdXRvcikKZ2FyYW50aXphIGEgbGEgVW5pdmVyc2l0YXQgSmF1bWUgSSBlbCBkZXJlY2hvIG5vIGV4Y2x1c2l2byBkZSBhcmNoaXZhcgplbiBlbCBSZXBvc2l0b3JpbyBVSkksIHJlcHJvZHVjaXIgKGNvbW8gc2UgZGVmaW5lIG3DoXMgYWJham8pLApjb211bmljYXIgeS9vIGRpc3RyaWJ1aXIgc3UgZG9jdW1lbnRvIG11bmRpYWxtZW50ZSBlbiBmb3JtYXRvIGVsZWN0csOzbmljby4KClRhbWJpw6luIGVzdMOhIGRlIGFjdWVyZG8gY29uIHF1ZSBsYSBVbml2ZXJzaXRhdCBKYXVtZSBJIHB1ZWRhIGNvbnNlcnZhciAKbcOhcyBkZSB1bmEgY29waWEgZGUgZXN0ZSBkb2N1bWVudG8sIHksIHNpbiBhbHRlcmFyIHN1IGNvbnRlbmlkbywKdHJhbnNmb3JtYXJsbyBhIG90cm9zIGZvcm1hdG9zLCBhcG95b3MgbyBtZWRpb3MgcGFyYSBnYXJhbnRpemFyCmxhIHNlZ3VyaWRhZCwgcHJlc2VydmFjacOzbiB5IGFjY2Vzby4KCkRlY2xhcmEgcXVlIGVsIGRvY3VtZW50byBlcyB1biB0cmFiYWpvIG9yaWdpbmFsIHN1eW8geS9vIHRpZW5lIGVsIGRlcmVjaG8KcGFyYSBvdG9yZ2FyIGxvcyBkZXJlY2hvcyBjb250ZW5pZG9zIGVuIGVzdGEgbGljZW5jaWEuClRhbWJpw6luIGRlY2xhcmEgcXVlIHN1IGRvY3VtZW50byBubyBpbmZyaW5nZSBsb3MgZGVyZWNob3MKZGUgYXV0b3IgZGUgb3RyYSBwZXJzb25hIG8gZW50aWRhZC4KClNpIGVsIGRvY3VtZW50byBjb250aWVuZSBtYXRlcmlhbGVzIGRlIGxvcyBjdWFsZXMgbm8gdGllbmUgZGVyZWNob3MgZGUgYXV0b3IsCmRlY2xhcmEgcXVlIGhhIG9idGVuaWRvIGVsIHBlcm1pc28gbmVjZXNhcmlvIHBhcmEgb3RvcmdhciBhIGxhIFVuaXZlcnNpdGF0IEphdW1lIEkKbG9zIGRlcmVjaG9zIHJlcXVlcmlkb3MgcG9yIGxhIHByZXNlbnRlIGxpY2VuY2lhLCB5IHF1ZSBlbCBtYXRlcmlhbCBjb24gZGVyZWNob3MKZGUgdGVyY2Vyb3MgZXN0w6EgY2xhcmFtZW50ZSBpZGVudGlmaWNhZG8geSByZWNvbm9jaWRvIGVuIGVsIGNvbnRlbmlkbwpkZWwgZG9jdW1lbnRvIGVudHJlZ2Fkby4KClNpIGVsIGRvY3VtZW50byBzZSBiYXNhIGVuIHVuYSBvYnJhIHF1ZSBoYSBzaWRvIHBhdHJvY2luYWRhIG8gYXBveWFkYQpwb3IgdW5hIG9yZ2FuaXphY2nDs24gZGlmZXJlbnRlIGVuIGxhIFVuaXZlcnNpdGF0IEphdW1lIEksIApzZSBwcmVzdXBvbmUgcXVlIHNlIGhhIGN1bXBsaWRvIGNvbiBjdWFscXVpZXIgZGVyZWNobyBkZSByZXZpc2nDs24KdSBvdHJhcyBvYmxpZ2FjaW9uZXMgcmVxdWVyaWRhcyBwb3IgZXN0ZSBjb250cmF0byBvIGFjdWVyZG8uCgpMYSBVbml2ZXJzaXRhdCBKYXVtZSBJIGlkZW50aWZpY2Fyw6EgY2xhcmFtZW50ZSBzdS9zIG5vbWJyZS9zIGNvbW8gYXV0b3IvcwpvIHByb3BpZXRhcmlvL3MgZGUgbG9zIGRlcmVjaG9zIGRlIGV4cGxvdGFjacOzbiB5IG5vIGhhcsOhIG5pbmd1bmEgYWx0ZXJhY2nDs24KZGUgc3UgZG9jdW1lbnRvIGRpZmVyZW50ZSBhIGxhcyBwZXJtaXRpZGFzIGVuIGVzdGEgbGljZW5jaWEuCgpMYSBVbml2ZXJzaXRhdCBKYXVtZSBJIGFzaWduYXLDoSBhIHN1IGRvY3VtZW50bywgZW4gY2FzbyBxdWUgYXPDrSBsbyBoYXlhIGluZGljYWRvLApsYSBsaWNlbmNpYSBDcmVhdGl2ZSBDb21tb25zICBjb3JyZXNwb25kaWVudGUgcGFyYSBwcm90ZWdlciBsYSBwcm9waWVkYWQgaW50ZWxlY3R1YWwKZGVsIGF1dG9yIHkgZ2FyYW50aXphciBzdSByZXV0aWxpemFjacOzbiBlbiBsYXMgY29uZGljaW9uZXMgZXN0YWJsZWNpZGFzLiAK