The University of Wales – COMP9312 – 23T2 – Data Analytics for Graphs
Q1 (4 marks)
START OF QUESTIONS
Assignment 2
Copyright By PowCoder代写 加微信 powcoder
Cohesive Subgraphs, Distributed Graph Processing, and Graph Feature
Submission Submit an electronic copy of all answers on Moodle (Only the last submission will be used).
Required Files A .pdf file is accepted. The file name should be ass2_zid.pdf
Deadline 9pm Friday 4 August ( )
Marks 20 marks (10% toward your total marks for this course)
Late penalty. 5% of max assessment marks will be deducted for each additional day (24hr) after the specified submission time and date. No submission is accepted 5 days (120hr) after the deadline.
1.1 Are the graphs in Figure 1 and Figure 2 homomorphic? If so, demonstrate a matching instance from vertices in Figure 1 to those in Figure 2. (2 marks)
1.2 Present all unique subgraphs in Figure 1 that are isomorphic to the graph in Figure 3. (2 marks)
Q2 (5 marks)
Consider a graph G with n vertices and m edges. We have a precomputed array L storing the truss number of each edge in G. Note that the truss number of an edge e is the largest integer k such that there exists a k-truss containing e. Each item in the array is a tuple including two vertex IDs of the edge and the truss number. Items in the array is already sorted in non-increasing order of the truss number.
Design an algorithm that finds the vertex set of every (connected) k-truss. You may show your algorithm by presenting the pseudocode. The input of your pseudocode includes a graph G represented by adjacency lists, the precomputed array L, and an integer k. Analyze the time complexity of your algorithm.
Take the graph G shown in Figure 4 and the corresponding array L shown in Table 1 as an example. With input k=3, your algorithm should return a two-dimentional array: [[1,2,3,4,5,11],[6,7,8,9,10,12]], which indicates two resulting 3-truss. Note that both k-truss vertex sets and vertices in each k-truss can be in any order. For example, [[10,6,7,8,9,12],[11,3,1,2,4,5]] is also a valid result.
Q3 (5 marks)
Consider the basic distributed algorithm to compute connected components in Pregel that has been mentioned in lecture [topics
Write the pseudocode of a combiner implementation to optimize the message passing.
Q4 (6 marks)
Consider the graph in Figure 5,
4.1 Compute the betweenness centrality and closeness centrality of nodes C and D. (3 marks)
4.2 Given the graphlets in Figure 6, derive the graphlet degree vector for nodes E and A. Only consider the induced matching instances. (3 marks)
Marking for Q1.1: 2 marks are given for the correct answer. 0 mark is given for all other cases.
Marking for Q1.2: 2 marks are given if the result subgraphs are correct, complete, and not redundant. If incorrent subgraphs exists or some correct subgraphs are missing, some points may be given by considering the proportion of correct subgraphs.
Marking for Q2: Two factors are evaluated in marking: (1) How good is your algorithm; (2) Does your time complexity match your algorithm. Full marks are given if your algorithm achieves our expected efficiency and your time complexity corresponds your algorithm. To identify the efficiency of your algorithm, the marking tutor will read your pesudocode and calculate a corresponding time complexity. Then, the marking tutor will compare the calculated time complexity with your submitted time complexity. For the pseudocode, you need to clearly present operations in each step. For complexity analysis, you need to provide correct, simplified, and tight time complexity (refer to Topic 3.2).
virtual void Compute(MessageIterator* msgs) {
int minID = GetValue();
for (; !msgs->done(); msgs->Next())
minID = min(minID,msg->Value());
if (minID < GetValue()){
*MutableValue() = minID;
SendMessageToAllNeighbors(minID);
VoteToHalt();
Marking for Q3: 5 marks are given for the correct answer. 0 mark is given for all other cases.
Marking for Q4.1: 1.5 marks are given for correct betweenness centrality values. 1.5 marks are given for correct closeness centrality values.
Marking for Q4.2: 3 marks are given if the vector is correct. 2 marks are given if 4/5 values in the vector are correct. 1 mark is given if 2/5 values in the vector are correct.
END OF QUESTIONS
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com