Software > Random Breadth First Search Algorithm Description | 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 Breadth First Search (BFS) is an uninformed search algorithm that has been proposed as an alternative to basic uninformed "flooding" [1, 2, 3]. It utilizes only local connectivity knowledge of the graph during search. Basic BFS begins at the source node by checking each neighbor if it is the destination node. If this fails, each of these neighbors check their neighbors and this continues until destination node is found. Random Random Breadth First Search improves upon basic BFS by reducing the number of messages passed during search. It randomly eliminates a fraction p of neighbors that are checked for each node. Search then proceeds from the start node checking only n neighboring nodes and proceeding forward. If at any time during the search a node N contacts a "dead-end" node (a leaf in the graph), the search process backtracks to N and continues.
Applicable to network graphs only. Random Breadth First 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 topologies. It can also be used to study its performance against other widely-known search algorithms like Basic Breadth First Search (BFS), Depth First Search (DFS) or Random Walk [4].
Pseudo Code of the algorithm is as follows: define randomBFS(Graph g, float prob, Node startNode, Node destinationNode)
In the IVC Software Framework, simply select a network data model and use Analysis > Search > Breadth First Search to analyze it.
This package was developed by George Fletcher and Hardik Sheth. Hardik Sheth integrated the code into the IVC Software Framework. |
||||||||||||||