Random spread on the family of small-world networks - art. no. 041104

We present analytical and numerical results of a random walk on the family of small-world graphs. The average access time shows a crossover from regul ar to random behavior with increasing distance from the starting point of t he random walk. We introduce an independent step approximation, which enabl es us to obtain analytic results for the average access time. We observe a scaling relation for the average access time in the degree of the nodes. Th e behavior of the average access time as a function of p shows striking sim ilarity with that of the characteristic length of the graph. This observati on may have important applications in routing and switching in networks wit h a large number of nodes.