Searching with Multiple Random Walk Queries
Santpal S. Dhillon, Piet Van Mieghem · 2007
We analyze the performance of searching with multiple random walk queries on Erdos-Renyi (ER) random graphs and power law graphs generated using preferential attachment. Our simulations show that searching with multiple random walk queries reduces message overhead as compared to flooding with sequence numbers. Moreover, the performance of searching by using multiple random walk queries is better in ER random graphs than in power law graphs grown by preferential attachment rule.