Networks: Fall 2013 Homework 1David Easley and´Eva Tardos Due at 11:15am, Friday, September 13, 2012As noted on the course home page, homework solutions must be submi t te d by upload tocourse’s Blackboard site. T h e file you upload must be in PDF format. It is fine to write thehomework in another format such as Word; from Word, you can save the file out as PDF foruploading. You can choose type ”pdf” when you save the file, or print it and choose ”Adobepdf” as your printer. (Changing the file extension from doc, or docx to pdf does not changethe forma t, only makes the file unreadable)Blackboard will stop accepting homework uploads after the posted due date. We cann otaccept late homewor k except for University-approved excuses (which include illness, a familyemergency, or travel as part of a University sports team or other University activity).Reading: The questions below are primarily based on the material in Chapters 2, 3, and 5of the b ook.(1) (8 points) Consider the small social network depicted in Figure 1, with dark edgesrepresenting strong ties, and dashed edges representing weak ties.(a) Which nodes violate the Strong Triadic Closure Property from Chapter 3, and whichsatisfy it? (Recall that unless a node violates the property, following the definition from thebook, it is said to satisfy it.)(b) List the minimal set of the edges do you have to add to the network to make allnodes satisfy triadic closure.A G F E D C B H Figure 1: Friendship in a small social network1(2) (8 points) Suppose a group of college students worked for a very large comp any lastsummer as interns. To h el p the students learn more about the company, each student wasassigned to a couple of projects for the summer, Figure 2 shows the projects they were doing.Amanda Daniel Evan Flavio Yang Project A Project C Project D Project F Figure 2: Interns and the projects they were assi gn ed to.Now, let’s build a social netwo rk on these students, connecting two of them with an edgerepresenting a strong tie if they were assigned to the same project. If they didn’t shareprojects at all, then we don’t connect them with an edge.(a) Using this way of constructing the social network, draw the network on the fivestudents.(b) Which students in the resulting network satisfy the Strong Triadic Closure Property,and which do not?(3) (8 points) Consider the social network depicted in Figure 3, with each edge labeledas either a friend or enemy relation. Is this network structurally balanced or not?If you think it is bal an ced , describe how you could divide the nodes into two sets X andY ,asinlectureandthebook,soeveryoneinX is friends with each other, everyone in Y isfriends with each other, and everyone in X is an enemy of everyone in Y .Ifyouthinkitisnot balanced, name a triangle in the network that does not satisfy the property of structuralbalance.(4) (8 points) Together with a child-development researcher, you are studying the socialnetwork in a sm al l middle schoo l consisting of grades 6, 7 and 8. The school has at least2A B C D E - - + + + - - + - - Figure 3: Friend and enemy relati o n in a small group.10 students in each grade. From their observations, they have identified the following factsabout the social ties, all of which we assume to be symmetric. (We’ll simplify for the sakeof asking a cleaner question.)They obser ved that all st u dents have strong ties to all oth er students in t h ei r own grade,and weak ties to students in neig hboring grades, but 6th graders typically don’t have any tiesto 8th graders. They found one exc ep t i on to this rule: siblin gs have strong ties no matte rwhat grades they attend.(a) Suppose the scho ol has a single pair of siblings consisting of one child in grade 7 andone child in grade 8. Does the resulting social network satisfy the Strong Triadic ClosureProperty? Give a brief explanation for your answer.(b) Would your answer change if the single pair of siblings was in grades 6 and 8,respectively? Give a brief explanation for your answer.(5) (10 points) Suppose you’re consulting for a large social-networking company, helpingthem design the part of their 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 theoverall social network, and try to automatically recommend based on the pattern of linksthe name of one other user to wh o m X is not currently connected, but who X might wantto connect to. If Y is chosen by the system as the recommendation for X,thenX receives aprompt on his/her screen asking if X would like to add Y as a friend. The recommendationis viewed as successful if X accepts th e suggestion a n d adds Y .You’ve been attending me et i n gs in which the team in charge o f the recommendationsystem shows the results of the system on various real-li fe examples, and then you suggestwhether you think the sy st em made the right recommendation. In this way, t h e recommen-dation team can try identifying deficiencies in their metho ds.3E X D C B A F I H G J Figure 4: The neighborhood of node X in the social graph.(a) In one example, the team shows you Figure 4, consisti n g of the user X and all nodesin the system who are at a distance of either 1 o r 2 from X in the social network. In thisexample, the system recommended u ser A to X.Doyouthinkthiswasthebestchoice?Ifso, explain why; if not, say what you think would be a better choice, and again explain why.In either case, relate your expl an at i on to princi pl es from class.(b) Currently the recommendation system is based on looking at small portions of thesocial network like the one in Figure 4. The r eco m m en d a t i on team asks whether you thinkit would be useful to incorporate other forms of information in deciding which node torecommend to X. (Although the current recomm en d a ti o n sy st em i s on l y u si n g n odes andedges, as in the figure, the social-networking system itself is recording all the actions takenby all its users (such as when X tags Y in a photo, or when X and Y are tagged inaphototogether,etc. withtime-stampsonalltheseactions,sotherearemanysourcesofinformation that could potentially be incorporated.) Describe one or more additional sourcesof information that you think the recommendation system might benefit from looking at,and give an explanation for your answer. Again, try to relate your expl a n at i o n to princ i p l esfrom class.(c) Recommendations based on