MA217 Applied Graph Theory Spring 2020
Final Exam
due at 11:30 a.m. on Tuesday, May 5, 2020
TAKE-HOME EXAM GUIDELINES
In order for this take-home test to be an honest and accurate reflection of your understanding of
the material, I am asking you to adhere to the following guidelines. Violation of these guidelines
will result, at minimum, in a score of zero on this test. There will be no opportunity to retake this
exam.
• You may use your class notes, the course textbooks, and the code I have shared with you or
code you have seen on DataCamp, but no other resources (books, articles, websites, class-
mates, friends, etc.). You are also allowed to use Help on RStudio.
• While taking this exam, with the exception of the Canvas page for this course and RStudio,
I ask that you close all the other tabs and close any other open browsers that you have.
• For the duration of the test, you may not discuss the test, or related material, with anyone
other than me.
• Giving help to others taking this test is as much a violation of these guidelines as receiving
help.
• If you are stuck on a problem, you may ask me for hints or directions. For minor hints, I
might deduct a point off; for major hints, I will deduct 1 to 2 points off. I would rather you
fully finish a problem with some help from me and a couple points off than submitting partial
work or no work at all. I would not take points off for clarification questions.
• Err on the side of writing more details than fewer. You will receive partial credit for answers
that are partially correct, but you cannot receive credit for what you do not write down.
• You will submit your work as an R Markdown file which contains your code and a written
report which contains your answers, observations and the main outputs. Your written report
should be a PDF or Word document and it can be generated using the Knitr button. However,
if you decide to use Knitr than start a Work document from scratch, you need to heavily
edit the Word document Knitr generates before you submit it.
• Late tests will not be accepted. Please submit your work before it is due.
• Before starting the exam, please make sure that you re-download all the files that I shared with
you on Canvas (Chap3.Rmd, Chap3--SmallWorld.Rmd, Yeast.Rmd, Chap4.Rmd, Chap5.Rmd,
graph1.R, graph2.R).
• Also, I ask you to add the following statement to your written report:
Taking this assessment unsupervised during the allotted time, I hereby certify
that I have not communicated and will not communicate with anyone else other
than Prof. Barghi about the assessment. Also, I have not consulted and will not
consult any outside sources (books, articles, websites, classmates, friends etc.)
for this assessment. Following the Saint Michael’s Honor Code, I also certify that
I have not used any inappropriate means to complete this assessment.
Signature: Date and Time:
THE EXAM
Instructions:
1. Create an R Mardown (.Rmd) file: File > New File > R Markdown and select Word as the
default output format. Save this file as Final [your smcvt username].Rmd. For example, I
will name mine Final abarghi.Rmd.
2. With the exception of the first code chunk that contain code for Knitr, get rid of everything
below it.
3. Create a code chunk and load the following packages: igraph, ggplot2, dplyr, tidyr,
magrittr, tibble, ggraph, tidygraph, and e1071.
4. Make sure that for all chunks of code that requires a random process you use a random seed
generator: set.seed(42).
5. For the written report, please do not include your code or its output unless a question explicitly
ask for it.
6. If you are not using Knitr and starting a Word document from scratch, name this document
Final [your smcvt username].doc (or .docx or .rtf).
Questions:
Using Yeast.Rmd as a guide, load the immunoglobulin interaction network (immuno) that comes
with igraph (instead of the yeast network) and answer the following questions. You can read
more about this network here. If you are running Yeast.Rmd concurrently with this file to compare
results, you want to use a different short name than g for the immuno network, e.g. h.
1. What is the order of this network? What is the size of this network? How many components
does it have? Is the graph directed or undirected? Do the vertices have attributes? Do the
edges have attributes? Include the answer to these questions in your written report, but not
the code or its output.
2. Using ldl, mds, and drl layouts separately, what do you observe when you visualize this
network? Describe your observations for each of these layouts. Use at most 25 words for each
layout. Include your observations in your written report, but not the code or its output.
3. Create a tibble that contains eccentricity, betweenness, degree, transitivity, eigen centrality,
and hub score. You need to look up the documentation for the last two statistics in Help.
Note that both eigen centrality and hub score return three lists and you need to access
one of them, i.e., vector, before wrapping it in enframe. Make sure that you make the
appropriate changes to the code. Do not include your code or its output in your report.
4. Create a tibble that includes the average degree, maximum degree, diameter, average cluster-
ing coefficient, average betweenness, average eigen centrality, and average hub score. Include
the output in your report but not the code. Do you notice anything interesting in this tibble?
Is this observation you are making also true when you look at the tibble in the previous
part?
5. Find the average distance in this network and create the plot for the distribution of distance
in this network. What do you notice about this plot? Describe your observations in at most
50 words. Include your answer and the plot in your report, but not the code or other outputs.
6. Create the plot for the degree distribution in this network. What do you notice about this
plot? Describe your observations in at most 25 words. Include your answer and one plot in
your report, but not the code or other outputs.
7. Based on the previous part, do you think that the degree distribution follows a power law?
In other words, is this is a scale-free network? If so, find its degree exponent.
8. Create a plot (using dots rather histograms) containing both the degree distribution for this
network (use blue) and the Poisson distribution with the correct parameter (use red). Include
the plot in your report, but not the code.
9. Create a plot that visualizes the average of clustering coefficients based on the degree. Is the
average clustering coefficient matches what the Erdo˝s-Re´nyi model predicts? Include your
answer and one plot in your report, but not the code or other outputs.
10. Create a plot that visualizes the relationship between betweenness and degree in this network.
What do you notice about this plot? Describe your observations in at most 50 words. Include
your answer and the plot in your report, but not the code or other outputs.
11. Create a plot that visualizes the relationship between eccentricity and degree in this network.
What do you notice about this plot? Describe your observations in at most 50 words. Include
your answer and the plot in your report, but not the code or other outputs.
12. Create a plot that visualizes the relationship between clustering and degree in this network.
What do you notice about this plot? Describe your observations in at most 50 words. Include
your answer and the plot in your report, but not the code or other outputs.
13. Create a plot that visualizes the relationship between hub score and degree in this network.
What do you notice about this plot? Describe your observations in at most 50 words. Include
your answer and the plot in your report, but not the code or other outputs.