3

I am wondering given the type of directed graph A, how do I convert it into the type of directed graph B? Basically, in graph B, I want to ignore Node X and only retain the Node T.

Conceptually, I am not sure if there are any ways to construct the adjacency matrix. I want to implement it in R, so any similar examples and suggestions are highly appreciated. Thank you! enter image description here

edit:

To be more specific, In graph A, X represents “product", T represents "Country". For example, for T1 and X1, it means country T1 produces product X1; Similarly, for T4 and X2 on the right hand side, it means the product X2 is consumed by country T4.

The graph B right now is not the correct graph but just a ballpark, because I just want to illustrate I want to construct this type of graph where the X can be ignored while the relationship between T can be decribed. The edge means consumption direction. Simply speaking, I would like T1 to have a directed out going edge to T2 if T1 is producing product X1 and product X1 is imported by T2. enter image description here

Arya McCarthy
  • 6,390
  • 1
  • 16
  • 47
flashing sweep
  • 433
  • 2
  • 9

1 Answers1

2

In my answer, I assume that you already have an adjacency matrix for $A$. Your graph is bipartite (two sets: $T$ and $X$), so the adjacency matrix can be partitioned into four blocks:

$$ \begin{bmatrix} 0 & [T \to X] \\ [X \to T] & 0 \end{bmatrix} $$

For instance, in your graph $A$, the upper left $0$ is a $7$-by-$7$ submatrix.

Consider that an adjacency matrix counts the number of length-1 paths (i.e., edges) between two nodes. It's either 0 or 1. If you multiply the matrix by itself, this counts the number of length-2 paths.

Because the graph is bipartite, every length-2 path can only be from a $T$ node to a $T$ node or from an $X$ node to an $X$ node.

You only care about the $T \to T$ edges, so you can slice that block out of $A \times A$. It will give you the edges that you sought in graph $B$.

In R, the code looks like this:

class(A)  # Confirming that you and I are working with the same adjacency matrix.
# [1] "matrix" "array" 
B = (A %*% A)[1:7, 1:7]  # The T->T part was only the top left 7x7 submatrix
B
#      [,1] [,2] [,3] [,4] [,5] [,6] [,7]
# [1,]    0    1    0    0    0    0    0
# [2,]    0    0    0    1    0    0    0
# [3,]    0    0    0    1    0    0    0
# [4,]    0    0    0    0    0    0    0
# [5,]    0    0    1    0    0    0    0
# [6,]    0    0    0    0    0    0    1
# [7,]    0    0    0    0    0    0    1

If you use an alternative representation (e.g. adjacency list, incidence list), it's easy to update the procedure accordingly. For sparse graphs, an adjacency list would let you do sparse matrix multiplication. Big space efficiency gains there.

Arya McCarthy
  • 6,390
  • 1
  • 16
  • 47