title: Searching for nodes in random graphs.
abstract: We consider the problem of searching for a node on a labeled random graph according to a greedy algorithm that selects a route to the desired node using metric information on the graph. Motivated by peer-to-peer networks two types of random graph are proposed with properties particularly amenable to this kind of algorithm. We derive equations for the probability that the search is successful and also study the number of hops required, finding both numerical and analytic evidence of a transition as the number of links is varied.
authors.affiliation: School of Computing and Mathematics, University of Plymouth, Plymouth, UK.
authors.forename: David
authors.initials: D
authors.lastname: Lancaster
mesh_terms: D000465:Algorithms; D003195:Computer Communication Networks; D003198:Computer Simulation; D015233:Models, Statistical; D008962:Models, Theoretical; D013598:Systems Theory