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.
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
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.
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
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
= (-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.
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