HW10. Graphs II (25th of Nov, 23.59)
Essays have been uploaded in here ( Essays of 2019 ). The randomised assignment has been created in this worksheet. Please look up your name and two assigned numbers after that. These are your peer review assignments. If for some reason there is conflict (same numbers are in the columns) with two first columns then select the value from the "Backup" column. You can also try to mark in the sheet that you have started to work on reviews. So if some works will be unassigned we know early... Make sure you provide a new submission of feedback, not editing an old one.
EX1. Peer review the first article; submit it via web form
EX2. Peer review the second article; submit it via web form
EX3. 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.
EX4. 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.
EX5. 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 the most important nodes.
EX6 (Bonus 2p). 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 the 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?
EX7 (Bonus 2p). Extend your solution from EX6 and implement the Google Page Rank algorithm (here is a small playground), the algorithm itself is very simple) 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 EX6.