Random Walk Method — Page Rank Algorithm using networkx.

Random Walk Method is an algorithm that is used to define and set random paths in a graph. Basically a random walk refers to where one can start from a node that is allocated randomly from a given set of nodes, then choosing a neighbor from its neighbor nodes to navigate and after walking throughout the area by keeping the path of a list of nodes. It inherits the property of probability distribution, but different from it due to its random selection nature. It is similar if someone gets drunk and move from one area to another area while searching to go home in real-life. The points distribution method is more accurate to generalize the neighborhood, but random walk work with random generate values to work upon the automatic nature.

History:

“Random walk method” comes from the Graph algorithms. In 1905, first time It was included by English Mathematician & Bio-Statistician Karl Pearson when he sent a letter of the article to Nature Magazine entitled “The Problem of the Random Walk”. Even the Gambler’s ruin problem walks back after studying random walks a date back, wherein ruin’s the problem, that is generally used to show that a gambler would eventually go bankrupt due to an opponent who has an infinite amount of wealth.

Random Walk Method

Steps to implement Random — Walk Method:

pip install networkx
pip install matplotlib

1. Selecting random graph using gnp_random_graph() method.
2. Initialize all the nodes with their initial rank value as 0.
3. Select the start node randomly.
4. Create an empty list to store all neighbors of the start node.
5. Now, select the node from the list randomly and incrementing the value of ranking.
6. Check, if the selected node has no outgoing edges.

• IF, the above condition is True, then select the node from the set of nodes randomly and increment the value of ranking.
• ELSE, select the node from the list containing all the neighbors randomly and increment the values of their ranks.

Output:

Output — Random Walk Method

<Figure size 1080x720 with 0 Axes>
Rank Of Nodes: [(4, 0.06449358755677265), (8, 0.07820038980586985), (6, 0.08626799858707523), (7, 0.09557673320104909), (0, 0.10186470965744474), (2, 0.10227566461578805), (3, 0.1028380527129143), (1, 0.10548585154621029), (9, 0.13034397420026064), (5, 0.13265303811661516)]
Random Walk: [(8, 5), (4, 7), (6, 7), (0, 8), (1, 10), (2, 10), (3, 12), (5, 13), (7, 13), (9, 16)]