Exam_1_spring_2024_solutions

.pdf

School

Georgia Institute Of Technology *

*We aren’t endorsed by this school

Course

3520

Subject

Computer Science

Date

Apr 3, 2024

Type

pdf

Pages

Uploaded by AmbassadorStrawKangaroo37

Problem 1 (25 points) A. Write the adjacency matrix for the above undirected graph (7 points) Solution: 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 1 1 1 0 1 1 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 point for each correct row B. Write the degree distribution of the above undirected graph. Show all your work to indicate how you arrived at the degree distribution including any calculations performed. You do not need to plot the degree distribution, instead you will provide a table or ordered list of values. (8 points) These are the degrees: Node 1 is degree 1 Node 2 is degree 2 Node 3 is degree 4 Node 4 is degree 4 Node 5 is degree 1 Node 6 is degree 1 Node 7 is degree 1 This is the degree distribution: p(1) = 4/7 2 points p(2) = 1/7 2 points p(3) = 0/7 2 points p(4) = 2/7 2 points

Degree Ratio 1 4/7 2 1/7 3 0/7 4 2/7 Both values are needed to receive both points. That is, if p(1) is not listed but only 4/7, then this is 1 out of 2 points, etc. If the number is not divided by the total (7), that is if the answer is “4” instead of “4/7”, this is –1/2 point per problem or –2 total. Could also include p(0)=0 and p(k>5)=0. Need only have p(1), p(2), p(3), and p(4) to be correct. p(3)=0 does need to be included since this is between non-zero values. 8 points C. Considering a completely new network that is not related to the graph in A, the nodes in the network have the number of edges (degrees) listed below. Based only on the degree distribution, does this network appear to meet the conditions for being a small world network? Explain why or why not. Include any code or calculations you used to justify your answer. 10 points Node Number of edges 1 2 2 3 3 3 4 1 5 4 6 2 7 1 8 2 9 1 10 1 11 1 12 1 13 1 14 1 15 1 (Note that the above table is not the degree distribution. It simply gives the number of edges for each of the 15 nodes. You will need to find the degree distribution to answer the above question.) Here is the degree distribution: Degree Fraction of nodes 1 9/15 2 3/15 3 2/15

4 1/15 5 0/15 6 0/15 7 0/15 8 0/15 Plotting this in log-log scale gives this plot: This plot in log-log scale is worth 5 points. -2 if not in log-log scale -1 if plot is mostly correct but some values are incorrect Score is pro-rated out of 5 points as needed. This appears to be a small world network because the degree distribution is approximately linear when plotted in log-log scale. Answer must say that the degree distribution is linear when plotted in log-log scale OR that the degree distribution follows a power law relationship AND either answer must be supported (either by a graph or mathematical demonstration of following a power law relationship) to receive all points. This answer that it is a small world network and the explanation why is worth 5 points. This answer that it is a small world network and the explanation why is worth 5 points. Answers that say it’s not a small world network because it’s not perfectly linear lose 2 points (worth 3/5). We said in lecture and in PSS that it does not need to be perfectly linear, just approximately. This is also shown in the book (page 58) and in the shiny apps. In PSS, when 0 0.2 0.4 0.6 0.8 log(degree) -1.2 -1 -0.8 -0.6 -0.4 -0.2 log(fraction of nodes)

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version