Q4- It's election season and two candidates, Candidate A and Candidate B, are in a hotly...

Transcribed Image Text:

Q4- It's election season and two candidates, Candidate A and Candidate B, are in a hotly contested city council race in rainy Eastmoreland. You are a strategic advisor for Candidate A in charge of election forecasting and voter acquisition tactics. Based on careful modeling, you've created one possible version of the social graph of voters. Your graph has 10,000 nodes, where nodes are denoted by an integer ID between 0 and 9999. The edge lists of the graphs are provided in the homework bundle. Both graphs are undirected. Given the hyper-partisan political climate of Eastmoreland, most voters have already made up their minds: 40% know they will vote for A, 40% know they will vote for B, and the remaining 20% are undecided. Each voter's support is determined by the last digit of their node id. If the last digit is 0-3, the node supports A. If the last digit is 4-7, the node supports B. And if the last digit is 8 or 9, the node is undecided. The undecided voters will go through a 10-day decision period where they choose a candidate each day based on the majority of their friends. The decision period works as follows: 1. The graphs are initialized with every voter's initial state (A, B, or undecided). 2. In each iteration, every undecided voter decides on a candidate. Voters are processed in increasing order of node ID. For every undecided voter, if the majority of their friends support A, they now support A. If the majority of their friends support B, they now support B. "Majority" for A means that strictly more of their friends support A than the number of their friends supporting B, and vice versa for B (ignoring undecided friends). 3. If a voter has an equal number of friends supporting A and B, we assign support for A or B in alternating fashion, starting with A. In other words, as the voters are being processed in increasing order of node ID, the first tie leads to support for A, the second tie leads to support for B, the third for A, the fourth for B, and so on. This alternating assignment happens at a global level for the whole network, across all rounds. (Keep a single global variable that keeps track of whether the current alternating vote is A or B, and initialize it to A in the first round. Then as you iterate over nodes in order of increasing ID, whenever you assign a vote using this alternating variable, change its value afterwards.) 4. When processing the updates, use the values from the current iteration. For example, when updating the votes for node 10, you should use the updated votes for nodes 0-9 from the current iteration, and nodes 11 and onwards from the previous iteration. 5. There are 10 iterations of the process described above. 6. On the 11th day, it's election day, and the votes are counted. Note that only the undecided voters go through the decision process. The decision process does not change the loyalties of those yoters who have already made up their minds. Voters who are initially undecided may change their mind on each iteration of this process. You assign the initial vote configurations to the social graph of voters you have created. After performing 10 iterations of the voting process, you find that your candidate, candidate A wins. Can you describe some properties of your social graph that enable A to achieve this outcome. Q4- It's election season and two candidates, Candidate A and Candidate B, are in a hotly contested city council race in rainy Eastmoreland. You are a strategic advisor for Candidate A in charge of election forecasting and voter acquisition tactics. Based on careful modeling, you've created one possible version of the social graph of voters. Your graph has 10,000 nodes, where nodes are denoted by an integer ID between 0 and 9999. The edge lists of the graphs are provided in the homework bundle. Both graphs are undirected. Given the hyper-partisan political climate of Eastmoreland, most voters have already made up their minds: 40% know they will vote for A, 40% know they will vote for B, and the remaining 20% are undecided. Each voter's support is determined by the last digit of their node id. If the last digit is 0-3, the node supports A. If the last digit is 4-7, the node supports B. And if the last digit is 8 or 9, the node is undecided. The undecided voters will go through a 10-day decision period where they choose a candidate each day based on the majority of their friends. The decision period works as follows: 1. The graphs are initialized with every voter's initial state (A, B, or undecided). 2. In each iteration, every undecided voter decides on a candidate. Voters are processed in increasing order of node ID. For every undecided voter, if the majority of their friends support A, they now support A. If the majority of their friends support B, they now support B. "Majority" for A means that strictly more of their friends support A than the number of their friends supporting B, and vice versa for B (ignoring undecided friends). 3. If a voter has an equal number of friends supporting A and B, we assign support for A or B in alternating fashion, starting with A. In other words, as the voters are being processed in increasing order of node ID, the first tie leads to support for A, the second tie leads to support for B, the third for A, the fourth for B, and so on. This alternating assignment happens at a global level for the whole network, across all rounds. (Keep a single global variable that keeps track of whether the current alternating vote is A or B, and initialize it to A in the first round. Then as you iterate over nodes in order of increasing ID, whenever you assign a vote using this alternating variable, change its value afterwards.) 4. When processing the updates, use the values from the current iteration. For example, when updating the votes for node 10, you should use the updated votes for nodes 0-9 from the current iteration, and nodes 11 and onwards from the previous iteration. 5. There are 10 iterations of the process described above. 6. On the 11th day, it's election day, and the votes are counted. Note that only the undecided voters go through the decision process. The decision process does not change the loyalties of those yoters who have already made up their minds. Voters who are initially undecided may change their mind on each iteration of this process. You assign the initial vote configurations to the social graph of voters you have created. After performing 10 iterations of the voting process, you find that your candidate, candidate A wins. Can you describe some properties of your social graph that enable A to achieve this outcome.