1
$\begingroup$

Consider the following:

Clear[edges, graph]
edges = {TX -> R1, R1 -> R3, R3 -> R5, R5 -> RX, TX -> R2, R2 -> R4, 
   R4 -> R6, R6 -> RX, R1 -> R2, R2 -> R3, R3 -> R4, R4 -> R5, 
   R5 -> R6, TX -> R7, TX -> R8, R7 -> R9, R9 -> R6, R9 -> RX, 
   R8 -> R6};
graph = Graph[edges, VertexLabels -> Automatic]
SortBy[{EdgeList[edges], 
   EdgeBetweennessCentrality[edges]}\[Transpose], N@*Last]

The output is

enter image description here

enter image description here

Can the results listed above for each vertex pair be broken out to include the {EdgeBetweennessCentrality, x, y}, where x is the total number of shortest paths that contain that specific vertex pair and y is the total number of shortest paths in the entire network? For example, a list {{R1->R2, 1.83333, x, y},...,{R3->R5, 6.33333, x, y}} would be produced with the x and y values specific to R1->R2, ..., R3->R5 and so forth.

Finally, the above is a directed graph. Can a similar analysis be done for an undirected graph?

ALL VERTEX PAIRS

Normal@AdjacencyMatrix@graph;
allVertexPairs = Permutations[VertexList@graph, {2}]
Length[%]
shortestPaths = FindShortestPath[graph, All, All] @@@ allVertexPairs
Length[%]
NonNullshortestPaths = Select[shortestPaths, UnsameQ[#, {}] &]
Length[%]
$\endgroup$
16
  • 1
    $\begingroup$ What exactly do you mean by total number of shortest paths in the entire network? Do you mean all 24 possible paths from TX to RX (FindPath[graph, TX, RX, All, All])? Or do you mean all possible shortest paths connecting any two vertices (Catenate@Catenate@Table[FindPath[graph, i, j, {GraphDistance[graph, i, j]}, All], {i, VertexList[graph]}, {j, VertexList[graph]}] /. {} -> Nothing) – there's 50 of them. $\endgroup$
    – Domen
    Oct 12, 2021 at 16:52
  • $\begingroup$ I'm referring to All Vertex Pairs, for example, this is the code that would generate All Vertex Pairs: $\endgroup$
    – user42700
    Oct 12, 2021 at 17:02
  • $\begingroup$ I just added code for All Vertex Pairs (see above) $\endgroup$
    – user42700
    Oct 12, 2021 at 17:03
  • $\begingroup$ Looking for all possible shortest paths that contain any two vertices; my code above found 38 of them, when the nulls {} are eliminated from the list. $\endgroup$
    – user42700
    Oct 12, 2021 at 17:07
  • 1
    $\begingroup$ @Domen That depends on what definition you take. This is not the usual definition that people use. In undirected graphs, we look at paths between unordered pairs. In directed graphs, between ordered pairs. Mathematica's way of calculating this is definitely the outlier here. Also, it's inconsistent with how it calculates vertex betweenness, where it takes unordered pairs. I consider this a bug, and I've reported it many years ago, but they didn't respond. $\endgroup$
    – Szabolcs
    Oct 14, 2021 at 8:34

1 Answer 1

4
$\begingroup$
edges = {TX -> R1, R1 -> R3, R3 -> R5, R5 -> RX, TX -> R2, R2 -> R4, 
   R4 -> R6, R6 -> RX, R1 -> R2, R2 -> R3, R3 -> R4, R4 -> R5, 
   R5 -> R6, TX -> R7, TX -> R8, R7 -> R9, R9 -> R6, R9 -> RX, 
   R8 -> R6};
graph = Graph[edges, VertexLabels -> Automatic];

allShortestPaths = 
  Flatten[Table[
     FindPath[graph, i, j, {GraphDistance[graph, i, j]}, All], {i, 
      VertexList[graph]}, {j, VertexList[graph]}] /. {} -> Nothing, 2];

SortBy[Transpose[{
    EdgeList[edges],
    EdgeBetweennessCentrality[edges],
    Length@Cases[allShortestPaths, {___, #[[1]], #[[2]], ___}] & /@ edges,
    ConstantArray[Length@allShortestPaths, Length@edges]
   }], #[[2]] &] // TableForm

enter image description here

$\endgroup$
3
  • $\begingroup$ Domen: This looks very nice. I very much appreciate your help!! I would have expected you to use your Catenate code but I see that the 50 is correct; last two questions: 1. Any insights into how the EdgeBetweenness Centrality column (e.g., R3->R5 with 6.33333) derives from the last two columns on the right (R3->R5 with 10, 50) and 2. What are you thoughts about this if the graph was UNDIRECTED? Again, many thanks! $\endgroup$
    – user42700
    Oct 12, 2021 at 23:34
  • $\begingroup$ Ahh, I see it now, you are actually interested in the definition of edge betweenness centrality! Let me just quickly resolve your troubles (I may edit the answer later). Look at the definition: $EB(e) = \sum_i \sum_j (\sigma_{ij}^{(e)}/\sigma_{ij})$. Although $\sum_i \sum_j 1/\sigma_{ij}$ is indeed constant, you cannot factorise this expression into $(\sum_i \sum_j \sigma_{ij}^{(e)})/(\sum_i \sum_j \sigma_{ij})$, which is what you are suggesting in your comment. Example: $(1/3)+(2/4)\neq(1+2)/(3+4)$. $\endgroup$
    – Domen
    Oct 13, 2021 at 14:01
  • $\begingroup$ I really like the values you show in the last two right-hand columns ... the second one in from the right is really the "stress" the path segment (link) is experiencing and that is a very helpful metric - one I feel is a good measure of edge betweenness. How Wolfram calculates their EdgeBetweenness centrality looks like it involves a normalization (it seems it is doing a 1/((n-1)(n-2))) normalization w/this being a directed graph. $\endgroup$
    – user42700
    Oct 13, 2021 at 14:27

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.