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 ad- jacency 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. (Well see just how sparse A is in the next step.) For general matrices, Matlab stores a matrix A = 2 6 6 6 4 a 11 a 12 a 1n a 21 a 22 a 2n ... ... . . . ... a m1 a m2 a mn 3 7 7 7 5 as a big block of numbers in memory: a 11 a 21 a 31 a m1 a 12 a 22 a 32 a m2 a mn 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 mn matrix requires mn blocks of memory for internal storage. When many of these entries are 0, it can be much more ecient to store only the nonzero matrix entries. Matlabs 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 a ij . If the number of nonzero entries is much smaller than mn, it is often more ecient to use Matlabs sparse matrix functionality. Youll 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, youll 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 dont 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

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 dierent cities that can be reached from a particular city by a direct flight. Since the value a ij 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 a i1 +a i2 + +a in . In Matlab, we can do this with the sum command. In the section of the M-file titled Analyzing Degree, youll 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, youll 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. (Youll need to look at the spreadsheet.) Then, use these two values to define the variables deg mhk and deg par as the number of direct-flight 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, lets use the interesting fact about the adjacency matrix A that its powers tell us about walks between vertices. 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 A 2 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 A 3 counts the number of pairs (k, l) for which there exist direct flights i ! k ! l ! j, and so on. This fact can be appreciated using the entrywise formula for matrix multiplication. For simplicity, lets look at the case of 2 hops. Fix cities i and j. Then, A 2 (i, j) is computed by taking the dot product of the row A(i, :) with column A(:, j). So we can use a counter k ranging over all the cities and write: A2 (i, j) = X k A(i, k)A(k, j) Now for every city k the expression A(i, k)A(k, j) is one if and only if city k is connected to both cities i and j, and otherwise it is zero. Thats why A 2 (i, j) counts all the ways to fly from i to j with exactly one layover. 4

Move to the M-file cell titled Reachable Cities and define the variables A2 and A3 as the powers A 2 and A 3 respectively. (Note: Since you are already computing A 2 it is more ecient to think of A 3 = AA 2 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. Youll 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