Centralities in Weighted Networks

Question

I have a weighted, undirected network with five nodes, whose adjacency matrix is given by

A = {{0, 3, 7, 0, 0}, {3, 0, 6, 0, 0}, {7, 6, 0, 2, 1}, {0, 0, 2, 0, 
4}, {0, 0, 1, 4, 0}};

I've created a weighted graph using A as follows:

G = WeightedAdjacencyGraph[ReplacePart[A, {j_, j_} -> \[Infinity]], 
  VertexLabels -> "Name", VertexSize -> Automatic, 
  VertexLabelStyle -> Large]

I'm interested in computing various centrality measures, specifically degree, closeness, and betweenness. For the first, I entered

DegreeCentrality[G]

The result was {4, 4, 4, 4, 4}, which is incorrect given my positive, integer-valued weights, and instead corresponds to the degree centrality of a complete graph on five vertices.

1. I'm curious to know how I should go about computing the degree centrality for this graph.
2. Also, can the ClosenessCentrality and BetweennessCentrality commands be used for weighted graphs, and, if so, what basic approach do they take. For example, is betweenness based upon shortest distances (as described in Social Networks, v13, 1991,141-154), where we use the reciprocals of the edge weights)?

Answer 1

If you are working with weighted graphs, I highly recommend my package IGraph/M, which makes this much easier in many situations. (Apologies to everyone else for bringing this up yet again.)

Here's a little demo:

A = {{0, 3, 7, 0, 0}, {3, 0, 6, 0, 0}, {7, 6, 0, 2, 1}, {0, 0, 2, 0, 4}, {0, 0, 1, 4, 0}};

Annoyed about having to replace zeros with infinities? Use IGWeightedAdjacencyGraph. It can use any matrix element as the notation for a missing connection. The default is 0 (or 0.).

Let's also thicken those edges at the same time.

g = IGWeightedAdjacencyGraph[A, EdgeStyle -> Thick]

Visualize weight as edge colour:

Legended[
 IGEdgeMap[ColorData["SolarColors"], EdgeStyle -> Rescale@*IGEdgeProp[EdgeWeight], g],
 BarLegend[{"SolarColors", MinMax@IGEdgeProp[EdgeWeight][g]}]
]

Visualize weight as edge thichkness:

IGEdgeMap[AbsoluteThickness, EdgeStyle -> IGEdgeProp[EdgeWeight], g]

I assume that when you mentioned DegreeCentrality, you wanted the strength of each vertex, i.e. the sum of edge weights for their incident edges. IGraph/M has that:

IGVertexStrength[g]
(* {10, 9, 16, 6, 5} *)

Want to scale vertices accordingly?

IGVertexMap[0.03 # &, VertexSize -> IGVertexStrength, g]

The built-in ClosenessCentrality does support weights, but BetweennessCentrality does not. IGraph/M has both, with weights support (based on the igraph library).

IGCloseness[g]
(* {0.037037, 0.0416667, 0.0625, 0.0454545, 0.0526316} *)

IGBetweenness[g]
(* {0., 0., 5., 0., 0.} *)

In both these functions (as well as in the built-in ClosenessCentrality), the edge weights are used directly in the shortest path calculations as the length of an edge. They are not transformed (e.g. inverted) in any way.

If you want to construct a new graph with inverted edge weights, a simple way is

IGEdgeMap[1/# &, EdgeWeight, g]

Verify the result:

IGEdgeProp[EdgeWeight][%]
(* {1/3, 1/7, 1/6, 1/2, 1, 1/4} *)

If you want to remove weights, you can use IGUnweighted. To test if a graph is edge-weighted, use IGEdgeWeightedQ (and note that the builtin WeightedGraphQ would return True for a non-edge weighted vertex weighted graph).

There are several other functions in IGraph/M which are useful with weighted graphs, or provide some advantage over the built-in equivalent when weights are present. E.g. IGReverseGraph correctly preserves edge weights while ReverseGraph does not.

I also accept suggestions for new features/functions, especially as they relate to weighted graphs, which I use myself extensively.