4
$\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$
9
  • $\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, 2018 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, 2018 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, 2018 at 21:07
  • 2
    $\begingroup$ @JasonB. I didn't originally notice that the OP wanted a complete graph with no self-loops, but some 0-weights. IGWeightedAdjacencyGraph exists because I find it extremely annoying that WeightedAdjacencyMatrix uses 0 to represent missing connections but WeightedAdjacencyGraph uses Infinity. Both 0 and Infinity make sense (in different cases), but at least these two should be exact inverses. IGWeightedAdjacencyGraph simply lets you choose what to use, and uses 0 by default. $\endgroup$
    – Szabolcs
    Jan 15, 2018 at 21:09
  • 1
    $\begingroup$ @halmir I would really love to see better support for weighted graphs in future versions. I hope you guys will consider that for the next version. I would rather use robust built-ins than having to implement (or interface to) stuff in IGraph/M ... $\endgroup$
    – Szabolcs
    Jan 15, 2018 at 21:16

1 Answer 1

6
$\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 and acknowledge you have read our privacy policy.

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