Background

This is an alternate way to study networks or graphs. If you haven't done Lab 7 you should do it first or at least read it.

Math

Given a graph of n vertices with 2-way edges (for example representing roads between cities or flights between airports) we can construct the vertex (adjacency) matrix M as in Lab 7. Since all the edges are 2-way the matrix is symmetric and thus it has n linearly independent eigenvectors. Theory also tells us that there is a single largest eigenvalue. Call this the dominant eigenvalue.
The Gould Index is a way of measuring the accessibility of each vertex of a network and it sort of a limit driven version of the calculations we did in Lab 7. For the Gould Index, we take an eigenvector v corresponding to the dominant eigenvalue and adjust it by dividing each entry by the sum of all the entries (so for the new vector the sum of the entries is 1). Then the Gould Index for each vertex is its value in this new vector.

MATLAB example

Consider a simple 4 vertex network with adjacency matrix

M = [0 1 0 0; 1 0 1 1; 0 1 0 1; 0 1 1 0];

We can then find the eigenvectors and eigenvalues of M using

[V,D] = eig(M)

where the columns of V are the eigenvectors corresponding to the eigenvalues which are the diagonal elements of D. In this case we get

V = 0.5059   -0.0000    0.8152   -0.2818
   -0.7494    0.0000    0.2536   -0.6116
    0.3020   -0.7071   -0.3682   -0.5227
    0.3020    0.7071   -0.3682   -0.5227
and
D =-1.4812         0         0         0
         0   -1.0000         0         0
         0         0    0.3111         0
         0         0         0    2.1701

We see that 2.1701 is the dominant eigenvalue, so v = (-0.2818, -0.6116, -0.5227, -0.5227). We then divide by the sum to get the Gould Index vector:

v = V(:,4);    % get the 4th column
gi = v/sum(v);  % divide by sum

We get gi = (0.1454, 0.3154, 0.2696, 0.2696). Thus vertex 2 has the highest Gould Index and thus has the highest accessibility.

Exercise

Just one exercise. Below is a graph representing the trade routes of medieval Russia. There is a theory that Moscow (#35) became the dominant city because of its strategic position on the trade routes. Compute the Gould Index Vector for this network and determine if this theory is valid or not.

Turn in the complete Gould Index Vector and your arguments for or against this theory.

Suggestion: Since there are so few edges, one way to build the adjacency matrix is to first set it to all zeros M = zeros(39) and then for each edge set the two values to 1, for example for the edge between #1 and #2 you'd use M(1,2) = 1; M(2,1) = 1. Put all these into an M-file and when you run it, you'll create your adjacency matrix.