2
$\begingroup$

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)?
$\endgroup$
  • $\begingroup$ I don't know enough about graph theory to know, but is the fact that IsomorphicGraphQ[G, CompleteGraph[5]] returns True a bug? If so, that might be the underlying issue. $\endgroup$ – Jason B. Jan 15 '18 at 20:58
  • $\begingroup$ @JasonB. The issue is that many builtins don't support weighted graphs. It was one of my primary motivations for starting IGraph/M. It's not related to IsomorhicGraphQ. $\endgroup$ – Szabolcs Jan 15 '18 at 21:05
  • $\begingroup$ @Szabolcs - I'm just noticing that graph constructed by WeightedAdjacencyGraph looks completely different from the IGWeightedAdjacencyGraph result. It looks exactly like the pentagram created by CompleteGraph[5]. Is that correct? $\endgroup$ – Jason B. Jan 15 '18 at 21:07
  • $\begingroup$ 0 in matrix considered as edge with weight 0. Op may means A /. {0 -> Infinity} for weighted adjacency matrix. Also DegreeCentrality is nothing to do with edge weights. $\endgroup$ – halmir Jan 15 '18 at 21:08
  • $\begingroup$ @Szabolcs - In your result, only the central vertex has four edges, the others only have 3. $\endgroup$ – Jason B. Jan 15 '18 at 21:08
1
$\begingroup$

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]

enter image description here

Visualize weight as edge colour:

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

enter image description here

Visualize weight as edge thichkness:

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

enter image description here

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]

enter image description here

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.

$\endgroup$

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.