[2022] Brunel - MA1607 Programming and Mathematical Projects - PageRank
MA1607|Brief for the Resit individual Project 2
1 Project tasks (Part 1)
Let u and v be the last two digits of your student number (as read from right to left). The tasks in Parts 1 and 2 of the project will use these digits to personalize your instructions.
In the first group of tasks you will need to compute and analyse the ranking of nodes for a pre-defined network, describing the dependencies between 6 mathematical topics. Each node represents a topic, and each edge represents the dependence. The direction of the edge goes from topic A to topic B if topic B underlies or is employed in some way in topic A; for instance the edge from “Systems of Linear Equations” to “Matrices” indicates that any analysis of systems of linear equations can be performed by studying the corresponding system matrices. If u (the penultimate digit of your student number) is odd, you will be working with the Network 1, otherwise, you will be working with the Network 2, see the diagrams above.
Task 1(a): Create script task1a.m, based upon script direct1.m, to compute the vector of limiting probabilities for your network. These are the probabilities that a random surfer following the PageRank algorithm will visit each node. The PageRank will then rank the node with the largest probability first, the node with the second largest probability second, etc (10%).
Task 1(b): Write a short section of your report to describe your findings. It must include the mathematical definition of your adjacency matrix (typed using the equation editor), as well as a brief statement of what changes to direct1.m were actually needed. Also write a paragraph to state what are the top three ranked nodes for your network, what are the values of their limiting probabilities and their ranks, and why do you think the associated topics got the highest ranks (10%).
For the next group of tasks you will need to add 3–5 nodes to your network, as well as at least 7 more edges. The resulting network should contain not fewer than 9 and not more than 11 topics. The following are some suitable examples of mathematical topics that can become new nodes, as well as possible dependencies between them:
• Systems of linear equations and matrix algebra: the latter can be used to solve the former, so if nodes systems of linear equations and matrix algebra are included in your network, there would be a directed edge pointing from systems of linear equations to matrix algebra.
• Infinite series −→ limits: the theory of limits is needed to evaluate infinite series.
• Definite integrals ←− area formulas in geometry: definite integrals can be used to calculate
the area under a curve. Is there a link in the opposite direction?
• There is a dependence between discrete distributions (in probability) and infinite series: the moments of a discrete distribution are often calculated using an infinite series. Hence, if nodes discrete distributions and infinite series are included in your network, there would be a directed edge pointing from discrete distributions to infinite series.
Also check out the discussion of suitable topics during Seminar Session 2 (Week 13). You may use one of these examples in your network, but not more than one. These are tasks that you need to perform for the newly created network:
Task 2(a): Prepare a graphical representation of your network, with each node numbered and labelled by a mathematical topic. Do not forget to clearly indicate which nodes and edges have already been there, and which ones you contributed. People usually draw their networks using Microsoft Word or Microsoft Powerpoint, but you are free to use any other software if you prefer (10%).
Task 2(b): For each edge that you added to the network to connect a pair of nodes, provide a brief justification in your report (1-2 sentences) of why do you believe these nodes must be connected (20%).
Task 2(c): Create script task2c.m based upon your earlier created script task1a.m to compute limiting probabilities for your extended network. Try running it. Write a few sentences in your report to briefly describe the results you obtain (10%).
Depending on the configuration of the network you just created, your script from Task 2(c) may fail to report the limiting probabilities (or it may give you warnings about the matrix M). If this is the case, write one or two sentences to explain why this happens for your network.
2 Project tasks (Part 2)
The tasks in Part 2 are about applying the extended version of the PageRank algorithm to your network and comparing the results with your observations from Task 2(a–c).
3 Project summary
Task 3(a): Create script task3a.m, based upon script task2c.m, to compute the vector of limiting probabilities for your network using an extended version of the PageRank algorithm. This will require you to modify task2c.m to use function cmat2() instead of cmat1(). Use the value of α = 0.1 + 0.0v, where v is the last digit of your student number (10%).
Task 3(b): Add a brief section to your report to describe the top three ranked topics for your modified network, what are their limiting probabilities and ranks, and how these results are different (if at all) from your results in Task 2(c). For full marks, get your program to print out top three PageRank values in descending order (10%).
The remaining two tasks are slightly harder.
Task 4(a): Create Matlab script task4a.m based upon script task3a.m, to generate a plot showing how limiting probabilities depend on the parameter α (α should change between 0 and 1). Make sure all your modifications are properly commented in the script (10%).
Task 4(b): Write a section in your report that includes the plot obtained during Task 4(a). Explain what specific modifications to task3a.m were needed to generate such a plot and also describe how limiting probabilities change for α ∈ [0, 1] (10%).
Overall, the key deliverables for this project are as follows:
• The report that contains answers to Tasks 1(b), 2(b), 3(b) and 4(b), which should be submitted as a .PDF file. The overall report should not be longer than 3 sides of A4 (assuming 2cm margins, at least 11pt font and 1.5 line spacing).
• The network diagram as specified in Task 2(a), which should be submitted either as a part of the report, or as a separate .PDF document.
• All Matlab scripts that were produced to answer Tasks 1(a), 2(c), 3(a) and 4(a), which should be submitted within a single .ZIP file. If you have incomplete answers to some of the tasks, please submit incomplete solutions as well, because partial marks are often possible. Use your student ID as the name of the .ZIP file.
