Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
Thanks very much for your answer, all of the graphs taken in consideration are connected. Could you please explain variable Cc ? In the first equation (n-1) is time radius isn't it? –  graphtheory92 Aug 25 '11 at 8:13
    
$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. –  user12998 Aug 25 '11 at 15:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.