Social and Economic Networks Fall 2023 Homework 1
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Social and Economic Networks
Fall 2023
Homework 1
Submit your answers on Canvas by 5 pm on Wednesday, November 8, 2023. All answers should be your own work. You can talk to me, or send me an email, if you have questions about the homework.
Typeset your answers using LaTeX or Microsoft Word. You can also scan very neatly written answers (in ink). Answer each question completely and succinctly. Show all steps in your calculations.
1. (15 points)
(a) (5 points) Draw the graph associated with the following adjacency matrix.
(b) (5 points) Use the adjacency matrix to calculate the number of walks of length two starting from each vertex.
(c) (5 points) Use breadth-first search (BFS) to find the shortest path from vertex A all other vertices.
2. (15 points)
(a) (5 points) Write the adjacency matrix associated with the following directed graph.
(b) (10 points) Use Dijkstra’s algorithm to find the shortest path from A to each other node in the graph (Note: the only difference from using the algorithm for an undirected graph is that you can only visit nodes in the direction of the arcs) .
3. (20 points) Consider an undirected graph with n = 1,000 vertices and m = 1,250 edges. Let each vertex represent and individual and each edge friendship between a pair of individuals.
(a) (5 points) What is the average number of friends per person (average degree of a vertex)?
(b) (10 points) Suppose that 8.2% of the individuals have no friends, 20.5% have one friend each, and 25.7% have two friends each. Are these percentages consistent with the hypothesis that this friendship graph is a random graph? Show all calculations and carefully explain each step in your reasoning.
(c) (5 points) Is it possible to determine the number of large components in this graph without any additional information , assuming it is a random graph? Explain.
4. (25 points) The following graph shows friendships between individuals.
Open the file “friendship_network.csv” , which contains data on these friendships, as an undirected graph in Gephi. Perform the following analyses using Gephi:
(i) Use “Statistics” (“Community Detection/Modularity”) to identify communities.
(ii) Use “Filters/Topology” to identify the K-core (and infer the K-shell) for each individual.
(iii) Run the various programs under “Statistics” to obtain the degree, betweenness, closeness and eigenvector centrality for each individual.
(a) (5 points) Complete the following table (round off the centralities to two decimal places).
(b) (5 points) Which two or three individuals are the most important and the least important in this network? Why?
(c) (15 points) Compare and explain the reasons for the similarities and differences in the
centralities for the following five pairs of individuals: (1) d and j, (2) i and j, (3) d and l, (4) o and p and (5) m and n.
5. (25 points) Consider the following network of six web pages. Use its adjacency matrix to answer the following questions.
(a) (10 points) Explicitly show the first step of the PageRank calculation (in matrix form). Use ε = 0.15 in your calculations. Use Excel to iterate the calculations for 15 steps. Check if the solution becomes stable. Report the final answer.
(b) (5 points) Use any program with which you are familiar (e.g., Python, Mathematica, or
Wolfram Alpha (online)) to calculate the eigenvalues of the matrix you used to calculate PageRank. Verify that the largest eigenvalue is one. Select the eigenvector associated with
an eigenvalue of one. Normalize this eigenvector by dividing each of its elements by the
sum of all its elements. What is the relation between the PageRank solution and the
normalized eigenvector? (Note: You might get eigenvalues in the form a + 0i. This is the
same as a value of a --- the 0i means that the imaginary part of the solution is zero).
(c) (10 points) Explicitly show one step of the hubs and authorities (HITS) algorithm (in matrix
form). Then use Excel to generalize the calculations. Iterate until you obtain a stable solution. Report only the final answer.
2023-11-07