1) Closeness centrality. Consider an undirected tree of n vertices. A particular
ID: 3845259 • Letter: 1
Question
1) Closeness centrality. Consider an undirected tree of n vertices. A particular edge joins vertices 1 and
2 and divides the tree into two disjoint regions of n1 and n2 vertices respectively; see Fig. 1.
1) Closeness centrality. Consider an undirected tree of n vertices. A particular edge joins vertices 1 and 2 and divides the tree into two disjoint regions of n1 and n2 vertices respectively; see Fig. 1. Fig. 1. An undirected tree of n vertices. Show that the closeness centralities cc (1) and ccu(2) of these two vertices satisfy the following identity CClExplanation / Answer
In a connected graph, the closeness centrality of a node is a measure of centrality in a network, calculated as the inverse of the sum of the length of the shortest paths between the node and all other nodes in the graph.
For the node 1 :-
Number of vertices that are in lenght 1 is = 4
Number of vertices that are in lenght 2 is = 5
Number of vertices that are in lenght 3 is = 6
Number of vertices that are in lenght 4 is = 3
Number of vertices that are in lenght 5 is = 1
Hence the closeness centrality of the vertix 1 is = inverse of (4*1 + 5*2 + 6*3 + 3*4 + 1*5) = 1/49
Hence CCl(1) = 1/49.
For the node 2 :-
Number of vertices that are in lenght 1 is = 3
Number of vertices that are in lenght 2 is = 8
Number of vertices that are in lenght 3 is = 6
Number of vertices that are in lenght 4 is = 2
Hence the closeness centrality of the vertix 2 is = inverse of (3*1 + 8*2 + 6*3 + 2*4) = 1/45
Hence CCl(2) = 1/45.
Here number of vertices in 1st region is = n1 = 8
number of vertices in 2nd region is = n2 = 12
now consider 1/CCl(1) + n1 = 1/(1/49) + 8 = 49 +8 =57 and
1/CCl(2) + n2 = 1/(1/45) + 12 = 45 +12 =57
Hence,
1/CCl(1) + n1 = 1/CCl(2) + n2
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.