Software > k Random-Walk Search AlgorithmDescription | Pros and Cons | Applications | Details | Usage Hints | References | Acknowledgments
Search in a graph is defined as finding a path from a start node to a destination node. The cost of a search is the number of edges traversed in locating the destination node (i.e. the number of "messages" sent in the network during the search process).
Random walk on a graph is a well known uninformed search technique [1,2]. In this approach, a reduction in message overhead is attempted by having a single message routed through the network at random. Search proceeds from the start node by randomly selecting one of its neighbors N. Then node N further selects one of its neighbors, avoiding re-selecting the node, the search message came from. This process continues until the desination node is found.
This search mechanism does not generate as much message traffic as the Breadth-First-Search (BFS) algorithms since there is only one message being routed through the network graph. The trade-off is that the search response time is significantly longer. k-random walk extends this process to k random walkers that operate simultaneously with the goal of reducing user-perceived response time.
Applicable to network graphs only. k-Random Walk Search Algorithm can be used to perform search on any of the structured (e.g. CAN, Chord), unstructured (e.g. PRU, Hypergrid) or random network models.
This algorithm can be used to perform search on any network graph (structured or unstructured). The search cost can be useful in comparing search performance among structured and unstructured P2P networks and also across different toplogies.
Pseudo Code of the algorithm is as follows:
define kRandomWalk(Graph g, int numWalkers, Node startNode, Node destinationNode)
In the IVC Software Framework, simply select a network data model and use Analysis > Search > k Random-Walk Search to analyze it.
This package was developed by George Fletcher and Hardik Sheth. Hardik Sheth integrated the code into the IVC Software Framework.