SOCI 111 Social Networks Questions

W23 SOCI 111: Social NetworksHomework 1
DUE: 1/25/20; 61 points
Instructions: These problems give you an opportunity to use the concepts and
techniques we’ve learned so far to analyze some toy social systems. They also test your
understanding of basic definitions and procedures. Think of them like exercises; they
help build your network muscles!
I encourage you to work in groups (of no more than 5), though this is not a
requirement. Each student should prepare their own solutions, along with a note at the
top of your assignment crediting other members of the working group. Please make
sure you truly understand the solution to a problem, and please: DO NOT COPY
SOLUTIONS. We will figure it out. In particular, do not go to the testbank at SAC, do not
go to Course Hero, do not use ChatGPT, and do not get solutions from friends who
have taken the course in the past. Likewise, do not create a class-wide GroupMe and
discuss the homework. All of this will impede your learning, and I will treat it as
academic misconduct.
In general, you should show your work rather than just writing down a number. This
makes it easier for us to see that you know what you are doing, and easier for you to
see when you’ve made a trivial mistake. On the other hand, don’t just throw everything
vaguely relevant at the wall and hope that something sticks. You need to be judicious!
Please submit your solutions to your TA at the beginning of class. Your submission
should be neat and legible: you can type it up or write it out by hand, but we aren’t
going to engage in decipherment here. That said, I strongly encourage you to write it out
by hand, as this will prepare you for the midterm and final (which will be handwritten).
Practicing Network Representations
Q1.
Let’s say we wanted to make a network representing the flow of people around
the country during the holiday season. We want to keep track of each leg of travel; not
everyone makes a round trip, and some folks make trips with multiple stops. We care
about movement at the town/city level, so the nodes represent cities. Should this be an
undirected network, or a directed network? Explain your answer. (3 points)
Q2.
Imagine that Zoom kept track of every time two people were on a Zoom call
together. Let’s say we want to create a network where we draw an edge between two
people if, in the past three years, they have been on at least one Zoom call together.
Should this be an undirected or a directed network? Explain your answer. (3 points)
Degree Distributions and Eulerian Paths
Questions Q3 – Q6 refer to the following graph:
Q3.
Plot the degree distribution for this graph. Recall that the degree of a node is
the number of neighbors it has. The degree distribution of a network shows the fraction
of nodes in the network that have degree 0, degree 1, degree 2, degree 3, etc. The
degree distribution is usually plotted with degree on the x-axis (starting at zero and
counting up) and fraction of nodes having degree k, often denoted p(k) on the y-axis.
Hint: Ask yourself how many nodes in this network have 0 neighbors? How many have 1
neighbor? How many have 2 neighbors? Etc. (3 points)
Q4.
From the degree distribution and the total number of nodes in the network, I can
figure out the degree count; from the degree count, I know that it is not possible to find
a path on this graph that crosses every edge, and crosses each edge only once. (Recall:
this is technically called an “Eulerian path”). Why can you be sure that an Eulerian path
is impossible? (3 points)
Q5.
This graph currently has a single component. By deleting one of two possible
edges, I can assure that the resulting graph has two components. Please say what edge
to delete, and explain why the resulting graph has two components. (3 points)
Q6.
Name a path, a simple path, and a cycle on this network! Each one should have
at least four nodes. (3 points)
More fun with adjacency matrices!
Q7.
Consider the following adjacency matrix. Is this network directed or undirected?
How do you know (without drawing the network)? (3 points)
A
0
1
1
0
0
[0
B C
1 1
0 1
1 0
0 1
1 1
1 1
D
0
0
1
0
0
0
E
0
1
1
0
0
1
F
0
1
1
0
1
0]
Q8.
How many nodes are in this network? How many links? Note: You can answer
these questions without drawing the network. (3 points)
Q9.
Now draw the network corresponding to the adjacency matrix in Q7. (3 points)
Q10-Q12 concern the following network:
Q10.
Write down the adjacency matrix for this network. (3 points)
Q11. The in-degree of a node is the number of other nodes that point to it; hence the
in-degree of B is 1. The out-degree of a node is the number of other nodes that it points
to; hence the out-degree of B is 3. Write down the in- and out-degrees of all the other
nodes in the network. (3 points)
Q12. Now we will explore some interesting properties of the adjacency matrix. What
happens when you add up all the entries in a given row (e.g., what happens when you
add up all the entries in the first/top row, row A)? What happens when you add up all
the entries in a given column (e.g., what happens when you add up all the entries in the
first/left-most column, column A)? Compare these answers to your answers in Question
11. Do you notice anything interesting? Can you guess a general rule that relates the
row or column sums of an adjacency matrix to the in-degrees or out-degrees? (3 points)
Q13. Write down the formula for the maximum number of edges in an undirected
network with n nodes. How would you change this to express the maximum number of
edges in a directed network with n nodes? Explain your reasoning. (3 points)
Clustering and collaboration
Q14-Q15 concern the following network of scientists. Each link represents a
collaboration:
Q14. The diameter is the largest distance in the graph. What is the diameter of this
graph? Show a breadth first-search illustrating this longest path. (3 points)
Q15.
What is the clustering coefficient of node C? Please show your work. (3 points)
Q16. Explain, in your own words, one reason why triadic closure occurs. Give an
example. (3 points)
Q17. Explain, in your own words, a second reason why triadic closure occurs. Give an
example. (3 points)
Extreme Erdős
Q18. As you will soon find out, I have an Erdős number of 4. Let’s say that I collaborate
with someone who has an Erdős number of 5. Would this make my Erdős number
lower? How about if I collaborate with someone who has an Erdős number of 2? Is there
any way I could get an Erdős number of 1? Make sure to explain your answer. (5 points)
vs.
Q19. Remember Stranger Things? Consider two actors from this 80’s nostalgia-fest:
Winona Ryder (Joyce Byers, left), who has been in many movies/TV shows, and Millie
Bobby Brown (Eleven, right) who has been in only a few. Which do you think is larger:
The average “Ryder-number” or the average “Brown-number,” where both are defined
like the Bacon number or the Erdős number? Explain your answer. (5 points)