I. Read Chapters 2-5 in the text. II. Check out the PPTX presentation for this week: GraphTheoryAndSN.pptx III. Answer the questions below. Use whole sentences and correct grammar for explanations. Submit your answers in a .pdf or Word format document on Canvas, in a document labeled with your last name, eg: Dugas_HW3.pdf. All text must be typed and diagrams must be electronically produced. (PowerPoint is a good tool for that, although there are others). No handwritten work of any kind will be accepted. Diagrams must be included in the text along with the problem they refer to. Do not submit them in a separate document. Introduction: Graph theory is a good modeling tool for social networks because it allows us to formalize properties of large systems using the language of graphs, and then systematically explore their consequences. Consider the concept of a pivotal node. Recall that a shortest path between two nodes is a path of the minimum possible length. We say that a node X is pivotal for a pair of distinct nodes Y and Z if X lies on every shortest path between Y and Z (and X is not equal to either Y or Z). For example, in the graph to the right, node B is pivotal for two pairs: the pair consisting of A and C, and the pair consisting of A and D. (Notice that B is not pivotal for the pair consisting of D and E since there are two different shortest paths connecting D and E, one of which (using C and F) doesn't pass through B. So B is not on every shortest path between D and E.) On the other hand, node D is not pivotal for any pairs. Consider the concept of a gatekeeper node. We say that a node X is a gatekeeper if for some other two nodes Y and Z, every path from Y to Z passes through X. For example, in the graph to the right, node A is a gatekeeper, since it lies for example on every path from B to E. (It also lies on every path between other pairs of nodes - for example, the pair D and E.) A more "local" version of this definition involves only looking at the neighbors of a node. We say that a node X is a local gatekeeper if there are two neighbors of X, say Y and Z, that are not connected by an edge. (That is, for X to be a local gatekeeper, there should be two nodes Y and Z so that Y and Z each have edges to X, but not to each other.) So for example, in the graph to the right, node A is a local gatekeeper as well as being a gatekeeper; node D, on the other hand, is a local gatekeeper but not a gatekeeper. (Node D has neighbors B and C that are not connected by an edge; however, every pair of nodes - including B and C - can be connected by a path that does not go through D.) QUESTIONS: 1. 2. 3. (continued on next page) 4. 5. 6. 7. 8. 9. 10. CS 581 - Assignment 3- Graph Theory and Social Networks a. Draw a diagram of an example of a graph having at least four nodes in which there is a single node X that is pivotal for every pair of nodes (not counting pairs that include X). b. Explain your answer. 11. a. Draw a diagram of an example of a graph in which every node is pivotal for at least one pair of nodes. b. Explain your answer. Figure 1 a. Which node or nodes in Figure 1 are gatekeepers? b. Explain your answer. a. Which node or nodes in Figure 1 are pivotal? b. Explain your answer. a. SRI b. UCLA a. Which node or nodes in Figure 2 are NOT pivotal? b. Explain your answer. a. Which node or nodes in Figure 1 are NOT local gatekeepers? b. Explain your answer a. STAN b. You will notice that there are no gatekeepers in Figure 2 (Darpanet). Explain why the network was purposely designed that way. UTAH RAND (continued on next page) SDC Figure 2 Consider the graph to the right, in which every edge but one is labeled as a strong tie (S) or weak tie (W). W According to the theory of strong and weak ties, with the strong triadic closure assumption, how must the edge connecting b and c be labeled (W or S)? Explain your answer. Consider the graph to the right, in which every edge is labeled as a strong tie (S) or weak tie (W). In your own words: In 2-3 sentences, explain what triadic closure is, and how it plays a role in the formation of social networks. You can draw a schematic picture in case this is useful. b. C. Explain your answer. According to the theory of strong and weak ties, with the strong triadic closure assumption, which other link or links would you expect to form over time, assuming that the links formed have strong ties? (consider more than one iteration over time and identify all links that should form) Explain your answer. 12. Consider the affiliation network to the right, with six people labeled A-F, and three foci labeled X, Y, and Z. a. Draw the derived network on just the six, joining two people when they share a focus. The derived network should have just the 6 nodes A-F and their interconnections showing shared focus. 13. For the graph to the right, where each edge is labeled as a positive or negative relationship: b. In the resulting network on people, can you identify a sense in which the triangle on the nodes A, C, and E has a qualitatively different meaning than the other triangles that appear in the network? Explain your answer. a. Identify the four 3-node cliques (triangles) and indicate if each is balanced or unbalanced. Is the entire graph balanced or unbalanced? MIT W BBN B a. Write a paragraph addressing the reason "friends of friends" are often a better source of job leads than your closer friends. Describe your reasoning in terms of strong and weak ties and local bridges. b. What has been your experience, or what have you observed in others, regarding the source of job leads? 000000 LINC HARV W X 00 S CASE a. According to the definitions in chapter 5, is this network on 90 people balanced? b. Explain your answer. C. Is the network weakly balanced? d. Explain answer e. Would your answer to (a.) change if there were only two villages of 30 each? How? f. Explain your answer. CARN 14. Ateam of anthropologists is studying a set of three small villages that neighbor one another. Each village has 30 people. Everyone in each village knows all the people in their own village, as well as the people in the other villages. When the anthropologists build the social network on the people in all three villages taken together, they find that each person is friends with all the other people in their own village, and enemies with everyone in the two other villages. This gives them a network of 90 people (i.e., 30 in each village), with positive and negative signs on its edges.