[SOLUTION] Strategies for Landmark Selection
1. In this example you will implement the algorithm for approximating distances in networks. First, you will select ?? landmarks ?? = {??1, ??2, ????} and then compute distances from each of these landmarks to all other nodes in the network. Using the upper bound on the distance you will approximate the distances for all pairs of nodes ?? and ?? by:?????,?? = ??????????? {???,???? + ???,???? }.To practically evaluate different strategies for selecting landmarks you will work with the network from the Les Misarables book. On the course web site you can find the network and a simple python code (https://courses.isds.tugraz.at/dhelic/websci/websci1.zip) showing you how to work with the network analysis library networxs ). This network has ?? = 77 nodes (76 nodes are in the giant component and you should work only with the giant component) and for each experiment you will select ?? = 10 landmarks. Implement these three strategies for landmark selection:(a) uniform random selection of landmarks, (b) random selection of landmarks proportional to the nodes degree, (c) random selection of landmarks inversely proportional to the nodes degree.To evaluate the strategies compute distances exactly for all pairs of nodes. Than compute absolute error for each pair of nodes ?? and ??:????,?? = |????,?? ? ?????,??|. Plot the histogram of absolute errors for all three strategies, together with the mean absolute error and the sample standard deviation of the error. Label the axes of your plots and provide a descriptive title for the plots. Include the mean and the standard deviation in the title of the plot. For all computations, plots, etc. you can either implement the code yourself or find an appropriate networxs function. For plotting use matplotlib and seaborn, which provides ready to use functions for various kinds of plots. In your report submit only the plots with a short discussion of what you see in the plots and which strategy worked best in your opinion. If your results are inconclusive you can repeat the selection of landmarks many times (e.g., 1000 times) and look at the averages over the landmark selections. In case of repetitions optimize your code by e.g., computing distances in a preprocessing step. You do not need to submit the code. For creating the report you can use the provided tex file to compile to PDF or create a PDF with any other tool that you like.
