4. (40 points) Given an undirected graph G = (V, E), the core number of a node u € V is the largest integer k such that

[answerhappygod]

4 40 Points Given An Undirected Graph G V E The Core Number Of A Node U V Is The Largest Integer K Such That 1 (82 KiB) Viewed 42 times

4. (40 points) Given an undirected graph G = (V, E), the core number of a node u € V is the largest integer k such that there exists a subgraph (subset of nodes) S CV where u € S and every node in S is connected to at least k other nodes in S. (1) (15 points) Calculate the core number of each node in the graph in the figure of Question 2. (2) (10 points) Figure out an algorithm that calculates the core number of each node for any input graph G = (V, E). Analyze the time complexity of your algorithm. (Hint: recall the Greedy algorithm for computing an approximate densest subgraph) (3) (15 points) i). (10 points) Download the file "DBLP.txt" where the first line describes how many nodes and edges are in the DBLP graph, and each line starting from the second line is in the form "u r" which means there is an edge between the node u and the node v. Write a program to calculate the core number of each node for the DBLP graph. Output your results in a txt file where every line is in the form "U : Cr" indicating that the core number of node u is C. Note that similar to Assignment 1, you also need to upload your code and a readme file describing how to run your code. ii) (5 points) Try to make your program finish running within 10 seconds (including reading the data file, calculating core numbers, and outputting the results to a txt file).