Two Ways To Understand Reachable Matrix

Last week we have learned how to use adjacency matrix to represent a social network. One question is why the power of matrix can indicate the reachability of social networks. Actually, the matrix mentioned in the class is named reachable matrix.

Let's see how it works. Here, I assume all of us have known the way to do matrix multiplication.

1. The First Way
One simple way to calculate reachable matrix is to regard it as logical operations,(And, Or, Not). We regard 0 and 1 represents false and true respectively.(you can also understand in this way: 0 represents two nodes are not connected; 1 represents two nodes are connected)

Another thing that should be declared is that in logic algebra, numeric operations of multiplication x*y, addition x + y are equal to the respective logical operations of conjunction x∧y, disjunction x∨y. The relevant logic operation rules are shown as below:

Let's review the example, here is a matrix:

Graph below is generated by matrix above: 

The two steps matrix within logic calculation:(which means the reachability going through two steps)

We can see that in X, n6 and n3 are not connected but in X^2 they are. So let's analyze the elements m'63(i=6, j=3).(using m for the elements in X matrix; using m' for the elements in X^2 matrix)

• m'63
  
  m'63=(m61∧m13)∨(m62∧m23)∨(m63∧m33)∨(m64∧m43)∨(m65∧m53)∨(m66∧m63)
  We have know that n6 is not connected with n3 within one step, So if n6 is connected with n3 within two steps, there must be at least one node nx which connects n3 and is connected by n6.
  
  Now look at the calculation process. It means if n6 n1 are connected and at the same time n1 n3 are connected; OR n6 n2 are connected and at the same time n2 n3 are connected;OR....., then n6 n3 are connected.
  
  In this process, only (m62∧m23) is equal to 1, others are all zero. So the path should be 6->2->3.

The thinking way is the same with the situation of more steps.

2. The Second Way
Another way to think this is to multiple matrix in normal way. With the foundation above, we can deepen our understanding.

The two steps matrix within normal way calculation:

With the knowledge in FIRST PART, we have understood the meaning of non-zero elements. Now let's analyze the elements m'16 and m'22

• m'16
  m'16=m11*m16+m12*m26+m13*m36+m14*m46+m15*m56+m16*m66
  We can see that only :
  
  m12*m26 =1
  m15*m56 =1
  Others are all equal to zero. So 
  m'16=m12*m26+m15*m56=2
  And you must find that 2 represents that there are two paths which make n1 n6 connected. Obviously, the paths can be 1->2->6 and 1->5->6
  
  
• m'22
  It is easy to find that two paths are 2->3->2 and 2->6->2

The thinking way is the same with the situation of more steps.

If you have any question, pls feel free to discuss with me.

Hope you enjoy this!