Q1.

Fig. 1

In this question, you will make some centrality calculations.

i. Consider Figure 1. For all the nodes in the Figure except the peripheral (leaf) nodes, calculate the betweenness centrality of the node by hand. Show all workings.

ii. Now, assume that Node 4 is in a fully percolated state (one) and all other nodes are fully unpercolated (zero). Write down the list of nodes which will have a non-zero value for Percolation Centrality, and compute the Percolation Centrality for each of these nodes.

iii. Now, assume that the percolation states change, so that only Node 2 is in a fully percolated state (one) and all other nodes are fully unpercolated (zero). Again, write down the list of nodes which will have a non-zero value for Percolation Centrality, and compute the Percolation Centrality for each of these nodes.

iv. Provide an intuitive comparison or explanation which justifies your results comparatively between parts ii and iii.

Q.2

Pagerank algorithm can be used as an effective centrality measure particularly for directed networks.

Fig.2

i. Now let us compute some ‘pagerank' values for this network. Assume alpha = 0.8, and all nodes have a value of (1/N) to begin with, where N is the size of the network. Prepare an Excel spreadsheet, which dynamically updates the pagerank value of each node based on the values of relevant nodes in the previous timestep. Based on your spreadsheet, prepare a sorted list of pagerank values for all nodes after 100 iterations.

ii. Verify that the pagerank values still add up to 1.

iii. How does the pagerank of Node 6 and Node 9 compare? Do you think this makes sense? Please explain how.

iv. If all the edges are now considered bidirectional (except the ones between Node 6 and Node 7, which together already make a bidirectional edge), how would it affect the relative rank of Node 6? Predict and justify your answer without re-computing the pagerank values of the whole network.

Q.3

Consider an Iterated Stag Hunt (ISH) played in a networked system. The networked system on which the game is played is given by Fig.1. The pay-off metric for stag-hunt is given by Fig. 4. The nodes at each iteration play a round of SH with each of their nearest neighbours. Thus, M games are played per iteration, where M is the number of edges. The nodes use the simple strategies of coordination C or defection D. Your overall objective is to maximise the system utility (total payoff for the system).

Fig. 4

i. What is the pay-off for the system from a D-C link, a C-C link, and a D-D link, respectively? Consequently, which types of links do you need to maximise to increase system pay-off? Which are the second-best type of links?

ii. If there is a constraint that the number of players playing C must equal the number of players playing D, come up with a scheme which ensures highest public utility per iteration. In your answer, denote what pure strategy each node must play, and the corresponding total pay-off per iteration.

iii. Now assume that each node plays tit-for-tat in an iterated game, and the pure strategies that you have assigned are simply the initial pure strategies for iteration one. Will the system pay-off change in the second iteration? By how much? Justify the answer.

iv. If all nodes play tit-for-tat, what is the average system pay-off per iteration according to your initial configuration?

v. Could you have increased this average system pay-off per iteration by beginning with a different initial configuration, given that initially you still you need to assign equal number of C and D nodes? Justify your answer.

Q.4

Consider Fig.1 again. In this question. You will calculate the robustness coefficient R of this network, by using different centrality measures.

i. Rank the nodes according to degree, and compute R based on degree according to this ranking.

ii. Now, re-compute R again by using ‘dynamic degree'. That is, rather than using the degree of each node which is pre-computed at the start, use the ‘new degree' which is obtained after node removals which might be different from the original degree, to rank nodes at each step. Does this make any difference in the value of R?

iii. Now compute the R value of this network, based on betweenness centrality. Use the values computed in Q.1 for this purpose. You can use ‘static' betweenness values (that is, you need not recompute betweenness after each step).

iv. Compute R value of the network given in Fig.2 , based on pagerank centrality. Use the values obtained after 100 iterations. Again, you need not recompute after each node removal.

v. Comparing Fig. 1 and Fig. 2, based on the R values you obtained, which network seems more robust? Do you think this is a fair comparison? Justify your answer.