[SOLVED] Csc 485b/578b: assignment 2

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