0
$\begingroup$

i would like to know if the closeness centrality value for a node has any sort of relation with other possible data we know such as the degree of the node, the density of the graph, the diameter and the radius.

I'm asking this question since I need to find, (if exists) a linear formula to find the closeness centrality of a node.

Thanks!

1 Answers 1

2

I don't believe that there are any simple relations that you can use to determine the exact answer. The computation for determining the closeness centrality for each vertex $v_i$, requires determining all of the vertices that are reachable from $v_i$ and then summing the shortest path to each of those vertices.

If you consider only connected components and know the diameter and radius of the graph you could construct an bounds on the closeness centrality for each vertex:

$\frac{(n-1)radius}{n-1}\le C_c(v_i)\gt\frac{(n-1)diameter}{n-1}$.

If you consider only connected components and know the eccentricity of each vertex then you can create a better upper bound: $ C_c(v_i) \le \frac{(n-1)eccentricity(v_i)}{n-1}$.

In the first case the lower bound is only achieved for $K_n, the same is true of the upper bound in the second case.

  • 0
    $C_c$ is the functional notation for denoting the closeness centrality value. The $(n-1)$ figure in the numerator denotes the best (or worse) case number of edges that you would have to travel from $v_i$ to reach every other vertex, one at a time.2011-08-25