0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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]

Mathematica graphics

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.

$\endgroup$
1
$\begingroup$

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:

enter image description here

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The FindShortestTour Details section does not mention directed or undirected graphs. So, some experimentation may be necessary too. $\endgroup$ – Sjoerd C. de Vries Sep 21 '15 at 20:04

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.