图的拉普拉斯矩阵.doc

此文档收集于网络，如有侵权请联系网站删除内容来自wikipedia链接为/wiki/Laplacian_matrix图的拉普拉斯矩阵 1. In themathematicalfield ofgraph theory, theLaplacian matrix, sometimes calledadmittance matrix,Kirchhoff matrixordiscrete Laplacian, is amatrixrepresentation of agraph. Together withKirchhoffs theorem, it can be used to calculate the number ofspanning treesfor a given graph. The Laplacian matrix can be used to find many other properties of the graph.Cheegers inequalityfromRiemannian geometryhas a discrete analogue involving the Laplacian matrix; this is perhaps the most important theorem inspectral graph theoryand one of the most useful facts in algorithmic applications. It approximates the sparsest cut of a graph through the second eigenvalue of its Laplacian.2. 定义 Given asimple graphGwithnvertices, its Laplacian matrixis defined as:，whereDis thedegree matrixandAis theadjacency matrixof the graph. In the case ofdirected graphs, either theindegree or outdegreemight be used, depending on the application.The elements ofare given bywhere deg(vi) is degree of the vertexi.Thesymmetric normalized Laplacian matrixis defined as:The elements ofare given byTherandom-walk normalized Laplacian matrixis defined as:The elements ofare given by3. 例子 Here is a simple example of a labeled graph and its Laplacian matrix.Labeled graphDegree matrix Adjacency matrix Laplacian matrix4. 性质For an (undirected) graphGand its Laplacian matrixLwitheigenvalues Lis symmetric. Lispositive-semidefinite(that isfor alli). This is verified in theincidence matrixsection (below). This can also be seen from the fact that the Laplacian is symmetric anddiagonally dominant. Lis anM-matrix(its off-diagonal entries are nonpositive, yet the real parts of its eigenvalues are nonnegative). Every row sum and column sum ofLis zero. Indeed, in the sum, the degree of the vertex is summed with a -1 for each neighbor Inconsequenc, because the vectorsatisfies The number of times 0 appears as an eigenvalue in the Laplacian is the number ofconnected componentsin the graph. The smallest non-zero eigenvalue ofLis called thespectral gap. The second smallest eigenvalue ofLis thealgebraic connectivity(orFiedler value) ofG. When G is k-regular, the normalized Laplacian is:, where A is the adjacency matrix and I is an identity matrix.5. 关联矩阵Define anorientedincidence matrixMwith elementMevfor edgee(connecting vertexiandj, withij) and vertexvgiven byThen the Laplacian matrixLsatisfieswhereis thematrix transposeofNow consider an eigendecomposition of,with unit-norm eigenvectorsand corresponding eigenvaluesBecausecan be written as the inner product of the vectorwith itself, this shows thatand so the eigenvalues ofare all non-negative6. 变形的拉普拉斯Thedeformed Laplacianis commonly defined aswhereIis the unit matrix,Ais the adjacency matrix, andDis the degree matrix, andsis a (complex-valued) number. Note that the standard Laplacian is just.7.对称的正规拉普拉斯矩阵The(symmetric) normalized Laplacianis defined aswhereLis the (unnormalized) Laplacian,Ais the adjacency matrix andDis the degree matrix. Since the degree matrixDis diagonal and positive, its reciprocal square rootis just the diagonal matrix whose diagonal entries are the reciprocals of the positive square roots of the diagonal entries ofD. The symmetric normalized Laplacian is a symmetric matrix.One has:where S is the matrix whose rows are indexed by the vertices and whose columns are indexed by the edges of G such that each column corresponding to an edge e = u, v has an entry，in the row corresponding to u, an entry.in the row corresponding to v, and has 0 entries elsewhere. (Note:denotes the transpose of S).All eigenvalues of the normalized Laplacian are real and non-negative. We can see this as follows. Sinceis symmetric, its eigenvalues are real. They are also non-negative: consider an eigenvector g of with eigenvalue and suppose. (We can consider g and f as real functions on the vertices v.) Then:where we use the inner product a sum over all vertices v, and denotes the sum over all unordered pairs of adjacent vertices u,v. The quantityis called theDirichlet sumof f, whereas the expressionis called theRayleigh quotientof g. Let1be the function which assumes the value 1 on each vertex. Thenis an eigenfunction ofwith eigenvalue 0.In fact, the eigenvalues of the normalized symmetric Laplacian satisfy 0 = 0. n-1 2. These eigenvalues (known as the spectrum of the normalized Laplacian) relate well to other graph invariants for general graphs.47.8. get the hang of 熟悉；掌握；理解解释离散拉普拉斯算子weakness n. 缺点；虚弱；弱点The Laplacian matrix can be interpreted as a matrix representation of a particular case of thediscrete Laplace operator. Such an interpretation allows one, e.g., to generalise the Laplacian matrix to the case of graphs with an infinite number of vertices and edges, leading to a Laplacian matrix of an infinite size.n.钻；钻机To expand upon this, we can describethe change of some element(with some constantk) asIn matrix-vector notation,vt. 怀疑；不信which givesNotice that this equation takes the same form as theheat equation, where the matrixLis replacing the Laplacian operator; hence, the graph Laplacian.（英国发明家，蒸汽机的发明人）To find a solution to this differential equation, apply standard techniques for solving a first-ordermatrix differential equation. That is, writeas a linear combination of eigenvectorsofL(so that), with time-dependentsimilarity n. 想像性；相似点Plugging into the original expression (note that we will use the fact that becauseLis a symmetric matrix, its unit-norm eigenvectorsare orthogonal):absorb vt. 吸收；吸引；使专心whose solution is（南非东南部一地区）As shown before, the eigenvaluesofLare non-negative, showing that the solution to the diffusion equation approaches an equ