In order to determine the Closeness Centrality for a vertex u in a graph, you compute the shortest path between u and all other vertices in the graph. The centrality is then given by:

$C(u) = \frac{1}{\sum_v{d(u, v)}}$ where $d(u, v)$ is the distance (= number of edges) between $u$ and $v$.

I understand this for graphs that are unweighted, however not for weighted graphs. When determining the shortest path you need to take the weights into account. Therefore there might be a path between $u$ and $v$ that contains of 3 edges (weights 1, 1 and 2). However, there might also be a second path consisting only of one edge with weight 10. Of course, the shortest path is the one with the three edges, as 4 is less than 10. But for the closeness centrality, all that matter is the number of edges on this shortest path which is three. This seems counterintuitive, since there exists another path with only a single edge.

So my question is: Is this just the way it is or would you have to change the definition of $d(u, v)$ for weighted graphs, such that it is not the number of edges but the actual distance based on the weights?


Unfortunately I cannot provide a paper or other proof, but I talked with a colleague who works a lot with the closeness centrality and he said, for weighted graphs you only use the "real" path length i.e. you do not take the number of edges but the sum of weights on the shortest path for the distance.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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