HW10. Graphs II (12th of Nov, 23.59)
EX1. The undirected graph below is given by the file. Find the Minimum Spanning Tree following the Prim's algorithm (form a single tree by expanding it one node at a time; start from A;). Verify that if you start from other nodes, e.g. "K" - it should yield the same cost tree. This task could be done either on paper or with a script/program. In any case report MST that you have obtained and explain the algorithm.
EX2. Use the following directed graph. Convert it into adjacency matrix representation and then convert the matrix into the graph where the original edges are replaced by "3-hop" edges or in other words - connect only vertices that are reachable in 3 steps of the original graph.
EX3. Make a transitive closure of the same graph - using three approaches. 1) G*G*G...; 2) making use of the following property - G2 = G*G, G4 = G2*G2, G8 = G4*G4 and 3) with Warshall algorithm. Verify that you got the same answer.
EX4. Implement a "random walk" procedure following links randomly (equal probabilities). Estimate the probability of being in any given node by varying how you deal with "dead ends" (e.g. node B) and "nodes with no links into it" (e.g. nodes D or A). First, try "re-appearing anywhere" from dead ends only. Secondly, when walking, with 20% probability jump to any random vertex in the network, and 80% of times select randomly and go to one of the neighbouring vertices. For both scenarios, provide the respective probabilities and identify most important nodes.
EX5. Use the random walk data from the previous exercise. Implement the "same" random walk procedure but now clearly using matrix multiplications much like in finding transitive closures. Assign uneven probabilities to links - e.g. 80%-20% for two-link nodes (larger probability to alphabetically first neighbour) and 60%-30%-10% for three link ones. Feel free to modify the input graph a bit. Introduce enough links so that you do not have "dead ends" or nodes where nothing leads into. E.g. I recommend introducing links G->H, B->K, K->H. But feel free to experiment. Of course, you should also figure out what happens to graph multiplications when you have not yet changed the graph. Your task is to report transition probabilities after N steps. How do you know when to stop multiplying?
EX6 (Bonus 1p). Extend from 5 and implement the Google Page Rank algorithm (here is a small playground) where 20% of times you would re-appear anywhere in graph. Both using equal-probabilities links and the uneven 80-20, 60-30-10 probabilities. Report the outcome probabilities and compare to results in EX5.