In class, we saw the definitions of three of the most standard centrality metrics as in...

Transcribed Image Text:

In class, we saw the definitions of three of the most standard centrality metrics as in degree, closeness, betweenness, PageRank (eigenvector). While betweenness centrality is often very important as a global metric of centrality, it is also limited in the sense that it favors nodes that are the "center of stars". As an example, consider Figure 1, where nodes 5, 7 have the highest betweenness centrality, but node 6 appears to be the true "central" node given its integral position for allowing communications between the two star communities. Figure 1: An example where betweenness centrality would fail to find the arguably most critical node in the network. Nodes 5,7 have betweenness centrality equal to 3, while node 6 has betweenness centrality equal to 5. 2 3 4 5 6 8 9 10 11 A possible solution to this is to propose a new centrality metric which decomposes betweenness centrality for a node i in two components: (i) b(): shortest paths between two nodes k, l that are both not neighbors of i (i.e., k,l N(i)); (ii) b(): shortest paths between nodes k, l where at least one endpoint is a neighbor of i (i.e., k N(i) or l = N(i), or both k, l N(i)). For every node in the network, we may then report the betweenness centrality of a node i, b, as the summation of the two terms: b(i) = b() + 6(). (a) Write a code in networkx that calculates b(), 6() for every node in the Les Misrables graph. (b) For the same graph, calculate also the betweenness centrality b; for every node. Then, rank b; and b) in decreasing order (i.e., rank the nodes from highest to lowest value). Using this rankings, calculate Kendall's 7 correlation (also known as rank correlation). In class, we saw the definitions of three of the most standard centrality metrics as in degree, closeness, betweenness, PageRank (eigenvector). While betweenness centrality is often very important as a global metric of centrality, it is also limited in the sense that it favors nodes that are the "center of stars". As an example, consider Figure 1, where nodes 5, 7 have the highest betweenness centrality, but node 6 appears to be the true "central" node given its integral position for allowing communications between the two star communities. Figure 1: An example where betweenness centrality would fail to find the arguably most critical node in the network. Nodes 5,7 have betweenness centrality equal to 3, while node 6 has betweenness centrality equal to 5. 2 3 4 5 6 8 9 10 11 A possible solution to this is to propose a new centrality metric which decomposes betweenness centrality for a node i in two components: (i) b(): shortest paths between two nodes k, l that are both not neighbors of i (i.e., k,l N(i)); (ii) b(): shortest paths between nodes k, l where at least one endpoint is a neighbor of i (i.e., k N(i) or l = N(i), or both k, l N(i)). For every node in the network, we may then report the betweenness centrality of a node i, b, as the summation of the two terms: b(i) = b() + 6(). (a) Write a code in networkx that calculates b(), 6() for every node in the Les Misrables graph. (b) For the same graph, calculate also the betweenness centrality b; for every node. Then, rank b; and b) in decreasing order (i.e., rank the nodes from highest to lowest value). Using this rankings, calculate Kendall's 7 correlation (also known as rank correlation).