<p>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.</p>

CC BY-SA 3.0
2018-04-03T12:21:55.147Z
2018-04-03T12:21:55.147Z
JustABit
<p>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:</p>

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

<p>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.</p>

<p>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?</p>

<graph-theory><graph-algorithms>
Closeness Centrality for Weighted Graphs
JustABit
# Closeness Centrality for Weighted Graphs

(Asked by: username_0 on 2018-04-01)

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?

**Tags:** graph-theory, graph-algorithms


---

## 1 answers

### Answer by username_0 on 2018-04-03. Score: 0 | Accepted answer

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.


---

