Chapter 17 Graphs and Graph Laplacians

1 Chapter 17 Graphs and Graph Directed Graphs , Undirected Graphs , IncidenceMatrices, Adjacency Matrices, Weighted GraphsDefinition graphis a pairG=(V, E),whereV={v1,..,vm}is a set ofnodesorvertices,andE V Vis a set of ordered pairs of distinct nodes (thatis, pairs (u, v)2V Vwithu6=v), edgee=(u, v), we lets(e)=ube thesourceofeandt(e)=vbe :Since an edge is a pair (u, v)withu6=v,self-loops are not , there is at most one edge from a nodeuto a 17. Graphs AND Graph LAPLACIANS1v4v5v1v2v3e1e7e2e3e4e5e6 Figure : every nodev2V,thedegreed(v)ofvis the numberof edges leaving or enteringv:d(v)=|{u2V|(v, u)2 Eor (u, v)2E}|.We abbreviated(vi) matrixD(G), isthe diagonal matrixD(G)=diag(d1,..,dm).For example, for confusion arises, we writeDinstead ofD(G). DIRECTED Graphs , UNDIRECTED Graphs , WEIGHTED GRAPHS735 Definition a directed graphG=(V, E),for any two nodesu, v2V,apath fromutovis asequence of nodes (v0,v1.)

2 ,vk)suchthatv0=u,vk=v,and(vi,vi+1)isaned geinEfor alliwith 0 i k 1. The integerkis thelengthof the path. A pathisclosedifu= connectediffor any two distinct nodeu, v2V,thereisapathfromutovand there is a path :The terminologywalkis often used instead ofpath,thewordpathbeingreservedtothecase wherethenodesviare all distinct, except thatv0=vkwhen thepath is binary relation onV Vdefined so thatuandvarerelated i there is a path fromutovand there is a pathfromvtouis an equivalence relation whose equivalenceclasses are called thestrongly connected 17. Graphs AND Graph LAPLACIANSD efinition a directed graphG=(V, E),withV={v1,..,vm},ifE={e1,..,en},thent heincidence matrixB(G)ofGis them nmatrix whoseentriesbijare given bybij=8> <>:+1 ifs(ej)=vi 1ift(ej)= is the incidence matrix of the graphG1:B=0 BBBB@1100000 10 1 11 0 00 11 0 0 0 100010 1 10000 11 , unless confusion arises, we writeBinstead ofB(G).

3 Remark:Some authors adopt the opposite conventionof sign in defining the incidence matrix, which means thattheir incidence matrix is DIRECTED Graphs , UNDIRECTED Graphs , WEIGHTED GRAPHS7371v4v5v1v2v3agbcdefFigure : The undirected Graphs are obtained from directed Graphs byforgetting the orientation of the (orundirected Graph )isapairG=(V, E), whereV={v1,..,vm}is a set ofnodesorvertices,andEis a set of two-element subsetsofV(that is, subsets{u, v},withu, v2 Vandu6=v), :Since an edge is a set{u, v},wehaveu6=v,so self-loops are not allowed. Also, for every set of nodes{u, v}, in the case of directed Graphs , such Graphs are some-times calledsimple 17. Graphs AND Graph LAPLACIANSFor every nodev2V,thedegreed(v)ofvis the numberof edges incident tov:d(v)=|{u2V|{u, v}2E}|.The degree matrixDis defined as a (undirected) graphG=(V, E),for any two nodesu, v2V,apath fromutovis a se-quence of nodes (v0,v1.)

4 ,vk)suchthatv0=u,vk=v,and{vi,vi+1}is an edge inEfor alliwith 0 i k integerkis thelengthof the path. A path isclosedifu= for any two distinctnodeu, v2V, :The terminologywalkorchainis often usedinstead ofpath,thewordpathbeingreservedtothecase where the nodesviare all distinct, except thatv0=vkwhen the path is binary relation onV Vdefined so thatuandvarerelated i there is a path fromutovis an equivalence re-lation whose equivalence classes are called DIRECTED Graphs , UNDIRECTED Graphs , WEIGHTED GRAPHS739 The notion of incidence matrix for an undirected graphis not as useful as in the case of directed graphsDefinition a graphG=(V, E), withV={v1,..,vm},ifE={e1,..,en},thenthei ncidencematrixB(G)ofGis them nmatrix whose entriesbijare given bybij=(+1 ifej={vi,vk}for the case of directed Graphs , the entries in theincidence matrix of a Graph (undirected) are usually writeBinstead ofB(G).

5 The notion of adjacency matrix is basically the same fordirected or undirected 17. Graphs AND Graph LAPLACIANSD efinition a directed or undirected graphG=(V, E), withV={v1,..,vm},theadjacency ma-trixA(G)ofGis the symmetricm mmatrix (aij)such that(1)IfGis directed, thenaij=8> <>:1ifthereissomeedge(vi,vj)2 Eor some edge (vj,vi)2E0otherwise.(2)Else ifGis undirected, thenaij=(1ifthereissomeedge{vi,vj} usual, unless confusion arises, we writeAinstead ofA(G).Here is the adjacency matrix of both DIRECTED Graphs , UNDIRECTED Graphs , WEIGHTED GRAPHS741 IfG=(V, E)isadirectedoranundirectedgraph,givenan odeu2V,anynodev2 Vsuch that there is an edge(u, v)inthedirectedcaseor{u, v}in the undirected caseis calledadjacent tov,andweoftenusethenotationu that the binary relation is symmetric whenGis an undirected Graph , but in general it is not symmetricwhenGis a directed (V, E)isanundirectedgraph,theadjacencyma-tri xAofGcan be viewed as a linear map fromRVtoRV,suchthatforallx2Rm,wehave(Ax) i=Xj ixj;that is, the value ofAxatviis the sum of the values ofxat the nodesvjadjacent 17.)

6 Graphs AND Graph LAPLACIANSThe adjacency matrix can be viewed as adi usion observation yields a geometric interpretation of whatit means for a vectorx2 Rmto be an eigenvector ofAassociated with some eigenvalue ;wemusthave xi=Xj ixj,i=1,..,m,which means that the the sum of the values ofxassignedto the nodesvjadjacent toviis equal to times the any undirected graphG=(V, E),anorientationofGis a function :E!V Vassign-ing a source and a target to every edge inE,whichmeansthat for every edge{u, v}2E,either ({u, v})=(u, v)or ({u, v})=(v, u). Theoriented graphG obtainedfromGby applying the orientation is the directed graphG =(V, E ), withE = (E). DIRECTED Graphs , UNDIRECTED Graphs , WEIGHTED GRAPHS743 Proposition (V, E)be any undirectedgraph withmvertices,nedges, andcconnected com-ponents. For any orientation ofG, ifBis the in-cidence matrix of the oriented graphG , thenc=dim(Ker (B>)), andBhas rankm c.

7 Furthermore,the nullspace ofB>has a basis consisting of indica-tor vectors of the connected components ofG; that is,vectors(z1,..,zm)such thatzj=1i vjis in theithcomponentKiofG, andzj= common practice, we denote by1the (column)vector whose components are all equal to 1. Observe thatB>1= to Proposition , the graphGis connectedi Bhas rankm 1i thenullspaceofB>is the one-dimensional space spanned many applications, the notion of Graph needs to begeneralized to capture the intuitive idea that two nodesuandvare linked with a degree of certainty (or strength).744 Chapter 17. Graphs AND Graph LAPLACIANSThus, we assign a nonnegative weightwijto an edge{vi,vj};thesmallerwijis, the weaker is the link (orsimilarity) betweenviandvj,andthegreaterwijis, thestronger is the link (or similarity) graphis a pairG=(V, W),whereV={v1,..,vm}is a set ofnodesorvertices,andWis a symmetric matrix called theweight matrix,suchthatwij 0foralli, j2{1.}

8 ,m},andwii=0fori=1,.., {vi,vj}is an edge i wij>0. The corresponding (undirected) Graph (V, E)withE={{vi,vj}|wij>0}, :Sincewii=0, can think of the matrixWas a generalized adjacencymatrix. The case wherewij2{0,1}is equivalent to thenotion of a Graph as in Definition can think of the weightwijof an edge{vi,vj}as adegree of similarity (or a nity) in an image, or a cost example of a weighted Graph is shown in Figure thickness of an edge corresponds to the magnitudeof its DIRECTED Graphs , UNDIRECTED Graphs , WEIGHTED GRAPHS74515 Encode Pairwise Relationships as a Weighted GraphFigure : A weighted every nodevi2V,thedegreed(vi)ofviis the sumof the weights of the edges adjacent tovi:d(vi)=mXj= that in the above sum, only nodesvjsuch that thereis an edge{vi,vj}have a nonzero contribution. Suchnodes are said to beadjacenttovi,andwewritevi degree matrixDis defined as before, namely byD=diag(d(v1).)

9 ,d(vm)).746 Chapter 17. Graphs AND Graph LAPLACIANSThe weight matrixWcan be viewed as a linear map fromRVto itself. For allx2Rm,wehave(Wx)i=Xj iwijxj;that is, the value ofWxatviis the weighted sum of thevalues ofxat the nodesvjadjacent thatW1is the (column) vector (d(v1),..,d(vm))consisting of the degrees of the nodes of the DIRECTED Graphs , UNDIRECTED Graphs , WEIGHTED GRAPHS747 Given any subset of nodesA V,wedefinethevolumevol(A)ofAas the sum of the weights of all edges adjacentto nodes inA:vol(A)=Xvi2Ad(vi)=Xvi2 AmXj= of a node:di= jWi,jDegree matrix:Dii= jWi,j19 Volume of a setvol(A) = i AdiFigure : Degree and that vol(A)=0ifAconsists of isolated vertices,that is, ifwij= ,itisbesttoassume thatGdoes not have isolated 17. Graphs AND Graph LAPLACIANSG iven any two subsetA, B V(not necessarily dis-tinct), we define links(A, B)bylinks(A, B)=Xvi2A, the matrixWis symmetric, we havelinks(A, B)=links(B, A),and observe that vol(A)=links(A, V).

10 The quantity links(A,A)=links(A, A), whereA=V Adenotes the complement ofAinV,measureshowmany links escape fromA(andA), and the quantitylinks(A, A)measureshow many links stay DIRECTED Graphs , UNDIRECTED Graphs , WEIGHTED GRAPHS749 The quantitycut(A)=links(A,A)is often called thecutofA,andthequantityassoc(A)=links(A , A)is often called ,cut(A)+assoc(A)=vol(A).20 Weight of a cut:cut(A,B) = i A, j BWi,jFigure : A Cut involving the set of nodes in the center and the nodes on the now define the most important concept of these notes:The Laplacian matrix of a Graph . Actually, as we will see,it comes in several 17. Graphs AND Graph Laplacian Matrices of GraphsLet us begin with directed Graphs , although as we willsee, Graph Laplacians are fundamentally associated withundirected key proposition below shows howBB>relates to theadjacency [15] (see also Godsil and Royle [17]).