## Description

Question 1

11 (15%, 10%) Does the anonymized personal Facebook network, described with Personal-May8-

12 Anonymous.gephi, which could be downloaded from Connex → Resource, exhibit homophily with

13 respect to gender? Write a simple java code for homophily test. Note you need to ignore the nodes

14 that do not have the gender information.

15 Problem 2

16 In the last question of Assignment 1 (i.e., Problem 4 of Assignment 1), you already know that the

17 network is structurally unbalanced, implying that there are latent incentives for some farmers to

18 change their social environment. In the same geographical setting, we still assume each farmer is

19 friends with all the other farmers that live at most 20 miles from him or her. But for each farmer

20 (say A), A is allowed to make friends with another farmer, who lives more than 20 miles away

21 from A and by default is an enemy of A, with a cost proportional to the distance between the two

22 farmers. Clearly, there is a simple scheme to enforce the structural balance if each farmer is willing

23 to invest enough to “fix” the problem, e.g., making friends to every other farmer. But this may be

24 too costly.

25 1. (15%, 15%) Is there a cheaper way to make the network structural balanced? If yes, provide

26 your solution. If not, explain your reason.

27 2. (0%, 20%) Assume that we use the third generalization of structural balance (i.e., approxi28 mately structural balance) by requiring that at least 85% of triangles are balanced. For ease

29 analysis, assume that the cost to introduce friendship between two farmers who live x miles

1

30 (x > 20) away is x dollars. Assume that this is an undirected network and that the x dollars

31 will be equally shared by the two endpoints involved. To make the network approximately

32 structural balanced, what is the minimum total cost for the farmers?

33 You can write a program to solve the problem. You will get an extra bonus of 10%, if you

34 could provide an analytical solution.

35 Problem 3

36 Assume that we have a group of n + 1 people sitting around a round table. Assume that there is

37 a token circulated along the round table, and a person can speak only if he/she obtain the token.

38 We assume that the time that a person can hold the token, once receiving it, is exponentially

39 distributed with the mean value of λ seconds. At the end of this time, the token then has to be

40 passed in the clockwise or counterclockwise direction with the same probability (i.e., 50%) to the

41 neighboring person. Assume that every people always have something to speak. Assume that the

42 token is initially at person 0.

43 1. (20%, 15%) What is the probability that person i,(i = 1, 2, …, n) is the last person that start

44 speaking?

45 2. (15%, 10%) What is the expected time required such that person i,(i = 1, 2, …, n) can speak

46 the first time?

47 Problem 4

48 We will consider the information cascades model introduced in class with specic values for the

49 probabilities. Lets suppose that the probability that Accept is a good idea is p = 1/2; and the

50 probability of a High signal if Good is true (as well as the probability of a Low signal if Bad is true)

51 is q = 3/4. Finally, lets assume that Good is actually true.

52 1. (10%, 10%) What is the probability that the rst person to decide will choose Accept; whats

53 the probability that this person will choose Reject?

54 2. (10%, 10%) What is the probability of observing each of the four possible pairs of choices by

55 the rst two people: (A,A), (A,R), (R,A), and (R,R)? [A pair of choices such as (A,R) means

56 that the rst person chose Accept and second person chose Reject.]

57 3. (15%, 10%) What is the probability of an Accept or a Reject cascade emerging with the

58 decision by the third person to choose? Explain why a cascade emerges with this probability.

2