Graph Theory and Small World Networks: Exam Solutions Guide

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

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

using the shiny apps, the points did not need to be perfectly linear for it to be a small world network. Some partial credit was given for responses that said it is “exponential” and thus a small world network, however, these answers do not receive all the points and are not fully correct because exponential is different from a power law degree distribution. Problem 2 (12 points) A. Given the following Markov matrix, what are the missing values a, b, and c? This matrix has not been transposed. 3 points � 0.1 𝑎𝑎 0.3 0.5 𝑏𝑏 0.2 0.6 0.3 𝑐𝑐 � Rows must sum to 1 a=0.6 b=0.3 c=0.1 1 point for each of 3 answers B. Given the completed Markov matrix with the values that you found in A, what is the probability of ending in each of the 3 states after 3 iterations if the system starts in state 2? Show all details for how you found this result including any calculations or code. You can use software to do calculations, but you must show the calculation that was performed. 5 points Using � 0.1 0.5 0.6 0.6 0.3 0.3 0.3 0.2 0.1 � 3 � 0 1 0 � = � 0.3950 0.3960 0.2090 � 2 points for each of 3 values in this vector. (6 points) Full credit is not awarded for showing values in the matrix raised to a power of 3 alone. You must also show the final vector after multiplication with the initial state vector for the system starting in state 2 (as shown above) since that is the probability of ending in each of the 3 states after 3 iterations if the system starts in state 2. 3 points for showing work taking the transposed matrix to power of 3 and multiplying by � 0 1 0 � . You must show your work and not just numerical results to receive all points since it was stated in the problem to show the details of your work.

Problem 3 (33 points) A. For the pathway shown below, 1) Write equations corresponding to the diagram in the form of mass action as we have done in PSS and homework assignments, 2) Implement the equations in PLAS, and 3) Show plots for a reasonable time range and step size in order to visualize the key dynamics in the model. X2 does not have any incoming mass. X2 is a dependent variable that depletes. All rate constants are equal to 0.1. Initial conditions (at time t=0) are: X0 = 4 X1 = 3 X2 = 2 X3 = 0 The value of the kinetic order (exponent) for the negative regulation is -2. In your answer to this question, you will submit items 1-3 described above (equations, code, and plots). 20 points total 16 points for correct equations and code 8 points for each of 4 correct equations, pro-rate as needed 8 points for correct set up in PLAS, initial conditions and rate constants entered correctly, time is set up, etc. 4 points for correct plot

B. Modify the model you created in PLAS in part A to represent the new diagram below. No changes to rate constants or initial conditions are required (all are the same as in part A). The initial value of the new variable Y is zero. If you have any new rate constants, they will also be equal to 0.1. The value of the kinetic order (exponent) for the negative regulation is still -2. Show the time plot for this model. For all original variables (X0, X1, X2, and X3): 1) Describe the differences between part A and part B, particularly considering their dynamics with respect to time. 2) Separately, explain why these differences occur. You will submit: Code, plot, description of what the differences are in X1, X2, X3, and X4, and an explanation of why these differences occur.

Your preview ends here

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

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

X0 decreases to a lower value in B than it did in A. This is because it takes longer for the mass in X0 to reach X3, so X0 has depleted to a lower value before the depletion of X0 causes the flux from X2 to X3 to decrease due to the negative signaling arrow from X0 to the X2  X3 flux. So X0 is slower to replenish from X2  X3 in this case. For X1 , in B it decays immediately unlike in A, where X1 increased immediately and then later decreased. This happens because in B, it now takes longer for the mass from X0 to reach X1 because it must pass through Y first. X2 does not change because it is still depleting with no incoming mass. Adding Y did not really affect X2. (There is a slight change due to the efflux of X2 changing slightly due to the X0  Y  X1  X3  X0 part of the pathway, this does not need to be mentioned.) For X3 does not reach as high of value in B as in A for the same reason as X0: X3 receives mass from both X1 and X2, but in part B, it takes longer for the mass from X0  Y  X1 to arrive and X0 has depleted to a lower value, causing X2  X3 to reduce.

Side by side differences plotted (A on left, B on right): 13 points total 5 points for correct code and plot 4 points for what the differences are 4 points for why differences occur

Exam_1_spring_2024_solutions

Related Documents