Weighted and directed network computation in Mathematica

Question

Is there any set of commands in Mathematica to compute mean shortest path, global clustering coefficient, diameter and radius of the network, etc. for weighted and/or directed graphs? There indeed exists commands which work for undirected and unweighted graphs but not sure for the above graphs.

Answer 1

That does not seem to be possible. I just tried FindShortestTour:

Undirected case:

g = Graph[{UndirectedEdge[1, 2]}];

FindShortestTour[g]
(* {2, {1, 2, 1}} *)

Directed case:

g = Graph[{1 -> 2}];

FindShortestTour[g]

Fail! Perhaps working around this using the DistanceFunction option? The idea would be to provide directions using ans asymmetric adjacency matrix:

h = (AdjacencyMatrix[g] // Normal) /. 0 -> Infinity
(* {{∞, 1}, {∞, ∞}} *)

FindShortestTour[Range@Length@h, DistanceFunction -> (h[[#1, #2]] &)]

During evaluation of FindShortestTour::asymdi: The distance function must be symmetric. >>

(* {} *)

This clearly shows that FindShortestTour expects only undirected graphs.

Answer 2

Yes. Most of the commands for graphs should be expected to work on directed graphs.

Below is some example code.

Generate a graph:

cgr = ButterflyGraph[2]

Make a directed graph with weighted edges:

arules = Most[ArrayRules[AdjacencyMatrix[cgr]]];
arules[[All, 2]] = RandomReal[{0, 1}, Length[arules]];
arules[[RandomChoice[Range[Length[arules]], 
    Floor[0.3*Length[arules]]], 2]] = 0;

wgrMat = SparseArray[
   Append[Select[arules, #[[2]] > 0 &], {_, _} -> \[Infinity]]];
wgr = WeightedAdjacencyGraph[wgrMat];

Find shortest path:

FindShortestPath[wgr, 1, 6]

(* Out[266]= {1, 8, 12, 11, 4, 5, 6} *)

Find different parameters of the graph:

Through[{GraphDiameter, GraphRadius, GraphCenter}[wgr]]

(* Out[267]= {3.55888, 1.81135, {11}} *)

Find distances between nodes:

GraphDistanceMatrix[wgr] // MatrixForm

The results above are for this graph:

Answer 3

For almost any graph-related function, check the documentation, and open the Details section. At the bottom you'll find something like:

EdgeBetweennessCentrality works with undirected graphs, directed graphs, weighted graphs, multigraphs, and mixed graphs.

So the answer is: you have to look this up individually for every function.