Matrix Analysis of Networks & Exercise
(http://faculty.washington.edu/krumme/207/exercises/networkA.html)
Supporting & Related Pages:
Network (Graph)
N1 
N2 
N3 
N5 
N6 


.

.

.

.

.

.

N4 



N1 
N2 
N3 
N4 
N5 
N6 
Nodal Degree S 
N1 
0  1  0  0  0  0 
= 1 
N2 
1  0  1  0  0  0 
= 2 
N3 
0  1  0  1  1  0 
= 3 
N4 
0  0  1  0  0  0 
= 1 
N5 
0  0  1  0  0  1 
= 2 
N6 
0  0  0  0  1  0 
= 1 
C

+ 
C^{2}

+ 
C^{3}

+ 
C^{4}


N1 
N2 
N3 
N4 
N5 
N6 
N1 
0  1  0  0  0  0 
N2 
1  0  1  0  0  0 
N3 
0  1  0  1  1  0 
N4 
0  0  1  0  0  0 
N5 
0  0  1  0  0  1 
N6 
0  0  0  0  1  0 

+ 

N1 
N2 
N3 
N4 
N5 
N6 
N1 
1  0  1  0  0  0 
N2 
0  2  0  1  1  0 
N3 
1  0  3  0  0  1 
N4 
0  1  0  1  1  0 
N5 
0  1  0  1  2  0 
N6 
0  0  1  0  0  1 

+ 

N1 
N2 
N3 
N4 
N5 
N6 
N1 
0  2  0  1  1  0 
N2 
2  0  4  0  0  1 
N3 
0  4  0  3  4  0 
N4 
1  0  3  0  0  1 
N5 
1  0  4  0  0  2 
N6 
0  1  0  1  2  0 

+ 

N1 
N2 
N3 
N4 
N5 
N6 
N1 
2  0  4  0  0  1 
N2 
0  6  0  4  5  0 
N3 
4  0  11  0  0  4 
N4 
0  4  0  3  4  0 
N5 
0  5  0  4  6  0 
N6 
1  0  4  0  0  2 

. A 






. = 







N1 
N2 
N3 
N4 
N5 
N6 
Accessibility
of a Node
S

N1 
3  3  5  1  1  1 
= 14 
N2 
3  8  5  5  6  1 
= 28 
N3 
5  5  14  4  5  5 
= 38 
N4 
1  5  4  4  5  1 
= 20 
N5 
1  6  5  5  8  3 
= 28 
N6 
1  1  5  1  3  3 
= 14 

The Matrix A represents the sum of the earlier direct and indirect
connectivity matrices, summed up to the one which was raised to the power
of the
diameter of the underlying network. Matrix C identifies the
direct links, matrix C^{2} includes all the connections between
two nodes which require two links, matrixC^{3} identify
connections between any two nodes which require 3 links. etc.
In the example above, the diameter is "4". Thus, we stop with the
matrix C^{4}. In the exercise, the changes to
the network result in a different diameter.
Using the diameter as the power of the last connectivity matrix assures
that A is a matrix without any zeroes: All nodes are now connected to all
other nodes either directly or indirectly. The numbers in the matrix
signify in how many different ways two nodes are connected. Thus, the sum
of the numbers in the rows (or columns) represents the total direct
and
indirect network accessibility of the underlying node (to all other
nodes).
The idea behind multiplying these matrices and then adding them up to the
Accessibility Matrix is that each of the matrices add another link to the
linkage chain until those points which are furthest apart from each
other are connected. With each multiplication, an additional direct link
is added to the already established linkage possibilities.
 Matrix Multiplications:
"Squaring the C Matrix":
We multiply the first row vector (of the first matrix C) by the first
column vector (of the second matrix C). We multiply the corresponding
values by each other and then add these products. The resulting value will
be entered in the box in the left upper corner (the "intersection" of the
row and column vectors)
Thus:
0x0=0; 1x1=1; 0x0=0; 0x0=0; 0x0=0; 0x0=0;
The sum of these products is 1, the first value for our C^{2}
matrix. Node 1 is
connected to itself once via two links: there is a direct link from 1 to 2
(part of the row of the first matrix C) and a direct (return) link from 2
to 1 (part of the column of the second matrix C)
 Matric Additions:
Matrices are added by adding the numbers in the corresponding cells.
EXERCISE TASK:
Q = 
How does the accessibility of the 6 nodes change as a result of the
introduction of two new (direct) links, namely between
 N1 and N4; and
 N4 and N6
Recalculate the
A matrix and briefly interpret
the changes in the direct and indirect accessibility of various
nodes.


Source: Taaffee & Gauthier, Geography of Transportation