Networks: Fall 2013 Problem Set 1 SolutionsDavid Easley and´Eva Tardos1a) In the table below, each node is marked as either violating (7) or satisfying (3) theStrong Triadic Closure Property (STCP), and if node X violates the STCP then theedges whose absence causes it to do so are listed.Node STCP Missing edgesA 3B 7 (A, C)C 7 (B, D)D 7 (C, H)E 7 (A, F )F 7 (E, G), (B, D), (D, E), (B, G)G 3H 31b) We can make this network satisfy the Strong Triadic Closure Property by adding in allthe missing edges listed above. Note that by making these new edges weak connectionswe avoid creating more situations where the STCP is violated.2a) Labelling each node by the first letter of the name of the intern it represents, the graphrepresenting this network isYDFEA2b) All the nodes fail to satisfy the Strong Triadic Closure Property.Node STCP Missing edgesA 7 (E, Y )D 7 (E, Y )E 7 (A, F ), (D, F )F 7 (E, Y )Y 7 (A, F ), (D, F )13) The network is structurally balanced because all the triangles in the graph have eitherone or three positive edges. X consists of nodes A, D, and C and Y consists of E andB.4a) Yes, the resulting network satisfies the Strong Triadic Closure Property.Every triangle of three people in the same grade consists of three strong edges, so theonly way a node can violate the STCP is through a strong tie between two people indifferent grades. We are told that the only strong tie across grades is between the twosiblings, one in 7th grade and the other in 8th grade. For clarity, call the siblings Aand B.Now, there are no strong ties between A and the rest of B’s grade, and no strong tiesbetween A and the 6th grade. But strong ties exist between A and B and between Aand C, where C is any other person in A’s grade. It follows that the only way A canviolate the STCP is if there is no connection between B and C for some C in A’s grade.But since every pair of [non-sibling] people in adjacent grades have weak ties and Aand B are in adjacent grades, there is a weak tie between B and every C in A’sgrade. Hence, A satisfies the STCP. The same argument works to show that the othersibling B also satisfies the STCP.4b) The fact that A and B are in adjacent grades is crucial to the above argument. If Aand B are in 6th and 8th grade instead, the resulting network violates the STCP.Strong edges exist between A and B and A and C, where C is anyone in A’s grade. IfA and B are two grades apart, then B and C are two grades apart, and by assumptionthere is no connection between B and C. So A violates the STCP.5a) In this graph, the only nodes X is not yet friends with are A, D, G, and H. X has threefriends in common with G, whereas A, D, and H each have only one friend in commonwith X.As discussed in class, it has been observed that two people with a friend in commonare more likely to become friends themselves (triadic closure). If we suppose thathaving more friends in common increases this effect, then it may be more sensible torecommend G to X than to recommend A to X.5b) The company may want to assess the strength of the interaction between two people byhow often they send messages to each other, how often they appear in photos together,etc. If the link between X and B is much stronger than the links (X,E), (X,F), and(X,I), say, then maybe X would like to be friends with A more than with G.5c) There are many possible answers. Here is one reasonable answer.After some time of using the site, the structure of the user’s neighborhood in thisnetwork may suggest that the user knows someone he/she hasn’t added as a friend yet.See, for example, the situation discussed in this problem, where it seems likely that Xknows G. It makes a lot of sense for the company to recommend G to X, but if G andX haven’t become friends on the site by now they may have particular reasons for notadding each other as friends.26) Recall that it is assumed that Y shared the link L, and that condition (i) is the eventthat this appeared on X’s News Feed. We can consider the lift to be a measure of theimportance of condition (i) in whether X shares the link L.For coherence, we can write what the lift is more explicitly. Again keeping in mindthat we assume Y has shared the link L, let P(i)(Y ) be the probability that X sharesthe link L given (i) and let P(ii)(Y ) be the probability that X shares the link L given(ii) (that the story that Y shared the link L did not appear on X’s News Feed). Then,we can write the lift aslift(Y ) =P(i)(Y )P(ii)(Y ).In this form, we can see that both probabilities, in the numerator and the denominator,can each separately affect lift.As discussed in class, close friends often share the same sources of information. There-fore, if X and Y are close friends then X is likely to find out about the link L evenwithout (i) happening. For example, X and Y may have found out about the link Ltogether, Y may have told X about it in person, or X may have seen it during one ofhis frequent visits to Y ’s Facebook page. On the other hand, if Y is a distant friendof X then X may hardly ever interact with Y except by seeing some of Y ’s activityon the News Feed. In terms of the equation for the lift, we are saying that if Y is aclose friend of X then the probability P(ii)(Y ) of X sharing the link L is higher thanit would be if Y was a distant friend of X.Simultaneously, it’s clear that if X and Y are distant friends then X is more likely tobe unaware of the link L until X sees on the News Feed that Y has shared it, whichwould influence P(i)(Y ) to be higher when Y is a distant friend rather than a closefriend of X. In addition, if Y is a close friend then Y may be part of X’s circle ofclosest friends (in terms of strong ties), in which case X may suspect that most ofhis closest friends already know about the link L (either for the reasons we discussedor because many of his closest friends have already commented on the story that Yshared L). Due to this, X may be less interested in sharing the link L himself, sinceit would be redundant and perhaps even irritating to his closest friends. These factsinfluence P(i)(Y ) to be lower if Y is a close friend of X rather than a distant friend ofX.All the influences on P(i)(Y ) that we have discussed cause P(i)(Y ) to be higher if Y isa distant friend and lower if Y is a close friend. We also concluded P(ii)(Y ) is higherif Y is a close friend and lower if …