Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Social and Economic Networks

Fall 2022

Homework 1 (100 points)

Answers must be typeset (for example, in TeX or Word) or written very neatly and scanned. Make sure you answer each part of each question completely. Give clear and concise answers.

Show your work. You can discuss concepts that might be useful for answering the questions with other students, but the answers themselves must be your own work.

1. (15 points) Chapter 2, exercise 2 in Easley and Kleinberg. 

2. (15 points) Let  denote an undirected graph representing friendships between seven individuals, where  is the set of vertices representing the individuals and ,,,,,,is the set of edges representing friendships between pair of individuals. Show the calculations for the first step of the Girvan Newman algorithm. Interpret the result.

3. (15 points) The following graph describes friendships among nine members of a large social network.

Your job is to help design the part of the system that recommends new friendships to their members (i.e., to the users of the system). The idea is to look at the position of a member X in the overall social network, and try to automatically recommend, based on the pattern of links, the name of one other user to whom X is not currently connected, but to whom X might want to connect. If Y is chosen by the system as the recommendation for X, then X receives a screen prompt asking if X would like to add Y as a friend. The recommendation is viewed as successful if X accepts the suggestion and adds Y. You have been attending meetings in which the team in charge of the recommendation system shows examples of real-life situations, and asks you, based on your knowledge of networks, what the system should recommend. They seek your feedback to fine-tune the behavior of the system. Which node do you think is the best choice to recommend to X? Explain your answer.

4. (25 points) The following figure shows the communication graph for Game of Thrones: A Storm of Swords.

Different centrality measures are given below for fourteen characters appearing in the show. Interpret and intuitively explain patterns in these centrality measures. (Note: Weighted degree centrality is equal to the total number of interactions a character had with others in the network.

Centrality measures for the network.

5. (30 points) Consider the following network of six web pages. Use its adjacency matrix to answer the following questions.

a) (10 points) Show the first step of the PageRank calculation (in matrix form). Use Excel to generalize the calculations. Iterate until you obtain a stable solution. Report the final answer.

b) (10 points) Use Excel to implement personalized PageRank for web page A (use ). How different are the standard and personalized PageRank solutions?

c) (10 points) Use any program with which you are familiar (e.g., Python, or the online Wolfram Alpha) to calculate the eigenvalues and eigenvectors of the matrix you used to calculate personalized PageRank. Which eigenvector is related to the personalized PageRank solution you obtained in part (b)? What is the relation?