SITE MAP SEARCH! LIBRARY E & B GEOG RESOURCES A-Z INDEX
ESSENTIALS GLOSSARY 207 PAGE CALENDAR ECON NEWS PORTFOLIO


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

Network Diameter = 4



Direct Connectivity Matrix (C)

N1 N2 N3 N4 N5 N6 Nodal
Degree
S
N1 010000 = 1
N2 101000 = 2
N3 010110 = 3
N4 001000 = 1
N5 001001 = 2
N6 000010 = 1


Accessibility Matrix (A)

C

+
C2

+
C3

+
C4

N1 N2 N3 N4 N5 N6
N1 010000
N2 101000
N3 010110
N4 001000
N5 001001
N6 000010
+
N1 N2 N3 N4 N5 N6
N1 101000
N2 020110
N3 103001
N4 010110
N5 010120
N6 001001
+
N1 N2 N3 N4 N5 N6
N1 020110
N2 204001
N3 040340
N4 103001
N5 104002
N6 010120
+
N1 N2 N3 N4 N5 N6
N1 204001
N2 060450
N3 4011004
N4 040340
N5 050460
N6 104002


.
A

.
=

N1 N2 N3 N4 N5 N6 Accessibility
of a Node
S
N1| 335111 = 14
N2| 385561 = 28
N3| 5514455 = 38
N4| 154451 = 20
N5| 165583 = 28
N6| 115133 = 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 C2 includes all the connections between two nodes which require two links, matrixC3 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 C4. 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.


  1. 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 C2 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)

  2. 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
  1. N1 and N4; and
  2. 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


Return to Geog 207
2003 [econgeog@u.washington.edu]