COMPSCI 753 Algorithms for Massive Data - Semester2 2021- Final Exam - Q3 Algorithms for Graphs
3 Algorithms for Graphs
3.1 Biased PageRank
Given a directed graph:
1. We have learnt the matrix formulation of PageRank r = M · r. Convert the above graph to a column-stochastic adjacency matrix. [1 mark]
2. Compute the PageRank of the graph above. [2 marks]
3. Let β = 0.8, calculate the biased PageRank with the teleport set S = {[the last digit of your student ID] mod 4}. [3 marks]
Note: The rank of each node should round to 3 decimal places.
3.2 Community Detection
1. Use two or three sentences to explain the differences between modularity maximization and the Girvan-Newman algorithm for community detection. [2 marks]
2. In the modularity maximization algorithm, which pair of nodes in the graph below should be merged in the first step to maximize the gain of modularity? Explain your answer. If there are multiple pairs of nodes with the same modularity gain, report all of them to get full mark. [4 marks]
3.3 Influence Maximization
1. Compute the influence spread of the seed set S = {1} using the Independent Cascade (IC) model on the following graph. [2 marks]
2. In the lecture, we have learnt a greedy algorithm to find a seed set for maximizing the influence based on the IC model. Starting with empty seed set, which node will be the first to be added to the seed set in the greedy algorithm? [2 marks]
Get the Solution to This Question
WeChat (微信)
WhatsApp
