Math 304 Handout:Linear algebra, graphs, and networks.December 1, 2006CONTENTS1. Graphs and adjacency matrices. 12. Word search 33. Ranking the web pages. 41. GRAPHS AND ADJACENCY MATRICES.Definition. A graph is a collection of vertices connected by edges. A directed graph is a graph allof whose edges have directions, usually indicated by arrows.123456FIGURE 1. A graph.FIGURE 2. A directed graph.Example.1• A DC electrical network is a directed graph.• An AC electrical network is a graph.• The Internet is a graph, with computers and servers as vertices and cables as edges.• The World Wide Web is a directed graph, with web pages as vertices and links as edges.• Towns connected by freeways form a graph.• Squares connected by one-way streets form a directed graph.Instead of drawing a graph, one can summarize it in a matrix. Label the vertices of a graph1, 2, 3, . . . , n. The adjacency matrix of a graph is the n × n matrix A such that aijis the numberof edges connecting the j’th and i’th vertices. Similarly, for a directed graph the adjacency matrixis the n × n matrix A such that aijis the number of edges going from the j’th to the i’th vertex.Example. The adjacency matrices for the graphs in Figures 1 and 2 areA =0 1 1 1 0 01 0 1 0 0 01 1 0 0 1 01 0 0 0 2 00 0 1 2 0 10 0 0 0 1 0andB =0 0 0 1 0 01 0 1 0 0 01 0 0 0 0 00 0 0 0 1 00 0 1 1 0 00 0 0 0 1 0For example, there is 1 edge connecting the 4th and the 1st vertex, 1 edge going from the 4th to the1st vertex, and no edges going from the 1st to the 4th vertex. Note that the adjacency matrix of agraph is always symmetric.Besides describing a graph as a bunch of numbers rather than as a picture, adjacency matrices haveother uses. To find out which vertices can be reached from the 1st vertex in one step, we look atthe entries of the 1st column of A. The non-zero entries are the 2nd, 3rd, and 4th, so those are thevertices that can be reached in one step. What about vertices that can be reached in two steps? It isnot hard to see that these correspond to the entries in the column of A2.A2=3 1 1 0 3 01 2 1 1 1 01 1 3 3 0 10 1 3 5 0 23 1 0 0 6 00 0 1 2 0 1.Thus in two steps, one can go from the 1st vertex back to itself in three ways (by visiting the 2nd,3rd, or 4th vertices first), one can get to the 2nd vertex in one way (by passing through the 3rdvertex), and one still cannot get to the 6th vertex. In a large network, one can use the adjacencymatrix to determine the distance between two vertices.Exercise. Describe how to interpret the entries of the powers of the adjacency matrix of a directedgraph.Exercise. Explain the 6 entry in the A2matrix above.2. WORD SEARCHHow do search engines work? The first issue is to find all the web pages; as far as I remember,the first efficient web crawler was Altavista in 1995. The second issue is to store, for all pages onthe web, all the words that they contain. Again, an efficient way to do this is using a (very, verylarge) matrix. Each column corresponds to a web page, each row to a word, and each entry is 1 if aparticular word occurs on a particular web page, and 0 otherwise.Example. Suppose that we have 5 web pages, the search words are linear, algebra, matrix, deter-minant, transformation, and the occurrences of each word on each page are given by the followingtable:P1 P2 P3 P4 P5linear 1 0 1 1 0algebra 1 1 1 0 1matrix 1 1 0 0 0determinant 1 1 1 0 0transformation 0 1 1 0 1The corresponding matrix isC =1 0 1 1 01 1 1 0 11 1 0 0 01 1 1 0 00 1 1 0 1If we want to find out which web pages contain the terms “linear algebra”, we form the corre-sponding vector x1= (1, 1, 0, 0, 0)Tand calculateCTx1=1 1 1 1 00 1 1 1 11 1 0 1 11 0 0 0 00 1 0 0 111000=21211.Exercise. Why do we take CT?We see that both words occur on the 1st and 3rd pages. Similarly, to find the pages containing theterms “determinant of a linear transformation”, we would calculate1 1 1 1 00 1 1 1 11 1 0 1 11 0 0 0 00 1 0 0 110011=22311,so that only the 3rd page contains all the terms.3. RANKING THE WEB PAGES.Once we know which web pages contain the desired words, how do we choose between these pages?An early approach was to return the pages that contain many occurrences of the search words. Thisidea is easily abused, since it is easy to put on a web page many repetitions of popular search wordsthat have nothing to do with the page content.A better approach is to use the graph structure of the Web. A page is “important” if many peoplethink it is, and so there are many links to it. This idea is also easily defeated: a company can createlots of “dummy” sites to point to its main site, thereby giving an appearance that that site is popular.Instead, say that a site is important if there are many important sites that point to it. This seemslike a circular definition, but one can make sense of it, and in 1999, Sergey Brin and Larry Page(following some ideas of Jon Kleinberg) based the Google search engine on it. Think of the Web asa giant Markov chain, where at every site a user randomly picks one of the links, goes on to the nextsite, again randomly picks a link, and continues in this manner. The matrix describing this Markovchain is almost the adjacency matrix of the directed graph, except that we want the matrix to bestochastic, and so normalize each column to have sum one. See the example below. The stationaryvector of this matrix will tell us what proportion of time, on average, will a used spend at each site,which shows how popular or important that site is.Example. Here is a network of 15 web pages and their links. The 5th site has many “naturally oc-curring” links pointing to it. The 14th site also has many links pointing to it, but they are “dummy”links since they all come from the 15th site. The stochastic matrix corresponding to this network is141432151167891312510FIGURE 3. A large network.D =0 0 0 0 0 0 0 0 0 0 0 0 0 0150 0 0 0 0 0 0 0 0 0 0 0 0 0150 0 0 0 0 0 0 0 0 0 0 0 0 0150 0 0 0 0 0 0 0 0 0 0 0 0 0150 0 0 0 0 1121 1 0 0 0 0 0 00 0 0 0 0 0120 0
View Full Document
Unlocking...