Description
TASKS
Open the file m551lab04.m in the Matlab editor and the file global-cities.csv in Excel (or other spreadsheet application).
1. In the M-file, run the cell labeled “Load the Network Data.” This will load the adjacency matrix A and
print its dimension (3883 × 3883). Note that the code uses the function sparse to create the matrix.
Basically speaking, a sparse matrix is a matrix with many 0s. (We’ll see just how sparse A is in the
next step.) For general matrices, Matlab stores a matrix
A =
a11 a12 · · · a1n
a21 a22 · · · a2n
.
.
.
.
.
.
.
.
.
.
.
.
am1 am2 · · · amn
as a big block of numbers in memory:
a11 a21 a31 · · · am1 a12 a22 a32 · · · am2 · · · amn
2 Math 551
This is called column-major ordering, since the first column is stored in a contiguous block, followed
by the second column, and so on. So an m × n matrix requires mn blocks of memory for internal
storage. When many of these entries are 0, it can be much more efficient to store only the nonzero
matrix entries. Matlab’s internal representation of sparse matrices is beyond the scope of this lab, but
the essential idea is that we need to store just 3 pieces of information for each nonzero entry: the i and
j indices of the entry and the associated value aij . If the number of nonzero entries is much smaller
than mn, it is often more efficient to use Matlab’s sparse matrix functionality. You’ll practice some of
these functions in the next step. In fact, although Matlab is good at hiding this fact from you, you will
benefit from the sparse matrix structure throughout the lab. Many of the standard Matlab functions
have special optimized behavior for sparse matrices. So, when you square the matrix A later, you’ll be
taking advantage of this optimized code without even having to think about it.
2. At the bottom of the “Load the Network Data” cell use the functions numel and nnz to define the
variables numel A (the total number of entries in A) and nnz A (the number of nonzero entries in A).
(Remember, if you don’t know how to use a function, you can always use doc.) Also define the variable
frac nz A = nnz A/numel A, which is the fraction of nonzero entries in A. If you examine the value of
this variable, you should see that only about 0.19% of the entries of A are nonzero.
Variables: numel A, nnz A, frac nz A
3. In graph theory, the degree of a vertex refers to the number of edges connected to it. In the present
context, this is the number of different cities that can be reached from a particular city by a direct
flight. Since the value aij is 1 of there is a flight between i and j and 0 otherwise, it is possible to
compute the degree of city i as ai1 + ai2 + · · · + ain. In Matlab, we can do this with the sum command.
In the section of the M-file titled “Analyzing Degree,” you’ll see the assignment deg = sum(A,2). This
tells Matlab to sum the matrix A along the second index (j). In other words, the output is a column
vector whose ith entry is the sum of the ith row of A.
By looking in the spreadsheet, we can see that Kansas City is associated with index 1963. If you run
this cell in the M-file and examine the value of deg(1963) in the Matlab command window, you’ll see
that Kansas City is connected by direct flight to 59 other cities. The M-file cell also creates a vector
of sorted degrees and plots them (with a logarithmic scale on the vertical axis). Look at the plot and
notice the rapid growth at the tail. Most cities have few direct connections and few cities have many
connections.
At the bottom of the M-file cell, define the variables mhk ind and par ind to be the indices associated
with Manhattan, KS and with Paris, France respectively. (You’ll need to look at the spreadsheet.)
Then, use these two values to define the variables deg mhk and deg par as the number of directflight connections from each of these cities respectively. Manhattan has 2 connected cities, Paris has
hundreds.
Variables: mhk ind, par ind, deg mhk, deg par
4. Now, let’s use the interesting fact about the adjacency matrix A that its powers tell us about walks
between vertices. More specifically, as described in Section 2.4, the (i, j) entry of Ap
tells us the
number of different ways of moving from i to j in p “hops.” In the current context, the (i, j) entry
of A gives the number of edges (either 0 or 1) between cities i and j. The (i, j) entry of A2
counts
the number of cities k for which there is a direct connection between i and k and a direct connection
between k and j. The (i, j) entry of A3
counts the number of pairs (k, l) for which there exist direct
flights i → k → l → j, and so on.
3 Math 551
Move to the M-file cell titled “Reachable Cities” and define the variables A2 and A3 as the powers
A2 and A3
respectively. (Note: Since you are already computing A2
it is more efficient to think of
A3 = AA2
than to simply cube A.)
Variables: A2, A3
5. In the Matlab command window, enter the following commands
>> nnz(A(mhk_ind,:))
ans =
2
>> nnz(A2(mhk_ind,:))
ans =
60
>> B = A+A2; nnz(B(mhk_ind,:))
ans =
60
Think about why the following statements are true.
• The first command counts the number of cities reachable from Manhattan by direct flight.
• The second command counts the number of cities reachable from Manhattan using exactly two
flights. (Note that Manhattan itself is included in this list.)
• The third command counts the number of cities reachable from Manhattan using at most two
flights.
At the end of the M-file, define the variables mhk 3 hop and par 3 hop to be the number of cities
reachable using at most three flights from Manhattan and from Paris respectively. You’ll need to
define a new matrix B and then use the nnz function. If you get it right, the second variable should be
about 4.9151 times as large as the first.
Variables: mhk 3 hop, par 3 hop
4 Math 551
