首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 93 毫秒
1.
Eigenvectors and eigenvalues of discrete Laplacians are often used for manifold learning and nonlinear dimensionality reduction. Graph Laplacian is one widely used discrete laplacian on point cloud. It was previously proved by Belkin and Niyogithat the eigenvectors and eigenvalues of the graph Laplacian converge to the eigenfunctions and eigenvalues of the Laplace-Beltrami operator of the manifold in the limit of infinitely many data points sampled independently from the uniform distribution over the manifold. Recently, we introduced Point Integral method (PIM) to solve elliptic equations and corresponding eigenvalue problem on point clouds. In this paper, we prove that the eigenvectors and eigenvalues obtained by PIM converge in the limit of infinitely many random samples. Moreover, estimation of the convergence rate is also given.  相似文献   

2.
A Frequency Assignment Problem (FAP) is the problem that arises when frequencies have to be assigned to a given set of transmitters so that spectrum is used efficiently and the interference between the transmitters is minimal. In this paper we see the frequency assignment problem as a generalised graph colouring problem, where transmitters are presented by vertices and interaction between two transmitters by a weighted edge. We generalise some properties of Laplacian matrices that hold for simple graphs. We investigate the use of Laplacian eigenvalues and eigenvectors as tools in the analysis of properties of a FAP and its generalised chromatic number (the so-called span).  相似文献   

3.
Laplacian matrices and their spectrum are of great importance in algebraic graph theory. There exist efficient formulations for eigensolutions of the Laplacian matrices associated with a special class of graphs called product graphs. In this paper, the problem of determining a few approximate smallest eigenvalues and eigenvectors of large scale product graphs modified through the addition or deletion of some nodes and/or members, is investigated. The eigenproblem associated with a modified graph model is reduced using the set of master eigenvectors and linear approximated slave eigenvectors from the original model. Implicitly restarted Lanczos method is employed to obtain the required eigenpairs of the reduced problem. Examples of large scale models are included to demonstrate the efficiency of the proposed method compared to the direct application of the IRL method.  相似文献   

4.
Laplacian matrices and their spectrum are of great importance in algebraic graph theory. There exist efficient formulations for eigensolutions of the Laplacian matrices associated with a special class of graphs called product graphs. In this paper, the problem of determining a few approximate smallest eigenvalues and eigenvectors of large scale product graphs modified through the addition or deletion of some nodes and/or members, is investigated. The eigenproblem associated with a modified graph model is reduced using the set of master eigenvectors and linear approximated slave eigenvectors from the original model. Implicitly restarted Lanczos method is employed to obtain the required eigenpairs of the reduced problem. Examples of large scale models are included to demonstrate the efficiency of the proposed method compared to the direct application of the IRL method.  相似文献   

5.
In this paper, closed-form formulae for the Kirchhoff index and resistance distances of the Cayley graphs over finite abelian groups are derived in terms of Laplacian eigenvalues and eigenvectors, respectively. In particular, formulae for the Kirchhoff index of the hexagonal torus network, the multidimensional torus and the t-dimensional cube are given, respectively. Formulae for the Kirchhoff index and resistance distances of the complete multipartite graph are obtained.  相似文献   

6.
The second smallest eigenvalue of the Laplace matrix of a graph and its eigenvectors, also known as Fiedler vectors in spectral graph partitioning, carry significant structural information regarding the connectivity of the graph. Using semidefinite programming duality, we offer a geometric interpretation of this eigenspace as optimal solution to a graph realization problem. A corresponding interpretation is also given for the eigenspace of the maximum eigenvalue of the Laplacian.  相似文献   

7.
In data science, data are often represented by using an undirected graph where vertices represent objects and edges describe a relationship between two objects. In many applications, there can be many relations arising from different sources and/or different types of models. Clustering of multiple undirected graphs over the same set of vertices can be studied. Existing clustering methods of multiple graphs involve costly optimization and/or tensor computation. In this paper, we study block spectral clustering methods for these multiple graphs. The main contribution of this paper is to propose and construct block Laplacian matrices for clustering of multiple graphs. We present a novel variant of the Laplacian matrix called the block intra‐normalized Laplacian and prove the conditions required for zero eigenvalues in this variant. We also show that eigenvectors of the constructed block Laplacian matrix can be shown to be solutions of the relaxation of multiple graphs cut problems, and the lower and upper bounds of the optimal solutions of multiple graphs cut problems can also be established. Experimental results are given to demonstrate that the clustering accuracy and the computational time of the proposed method are better than those of tested clustering methods for multiple graphs.  相似文献   

8.
It is well known that the resistance distance between two arbitrary vertices in an electrical network can be obtained in terms of the eigenvalues and eigenvectors of the combinatorial Laplacian matrix associated with the network. By studying this matrix, people have proved many properties of resistance distances. But in recent years, the other kind of matrix, named the normalized Laplacian, which is consistent with the matrix in spectral geometry and random walks [Chung, F.R.K., Spectral Graph Theory, American Mathematical Society: Providence, RI, 1997], has engendered people's attention. For many people think the quantities based on this matrix may more faithfully reflect the structure and properties of a graph. In this paper, we not only show the resistance distance can be naturally expressed in terms of the normalized Laplacian eigenvalues and eigenvectors of G, but also introduce a new index which is closely related to the spectrum of the normalized Laplacian. Finally we find a non-trivial relation between the well-known Kirchhoff index and the new index.  相似文献   

9.
We show that, in the graph spectrum of the normalized graph Laplacian on trees, the eigenvalue 1 and eigenvalues near 1 are strongly related to minimum vertex covers.In particular, for the eigenvalue 1, its multiplicity is related to the size of a minimum vertex cover, and zero entries of its eigenvectors correspond to vertices in minimum vertex covers; while for eigenvalues near 1, their distance to 1 can be estimated from minimum vertex covers; and for the largest eigenvalue smaller than 1, the sign graphs of its eigenvectors take vertices in a minimum vertex cover as representatives.  相似文献   

10.
The eigenvalues of graphs are related to many of its combinatorial properties. In his fundamental work, Fiedler showed the close connections between the Laplacian eigenvalues and eigenvectors of a graph and its vertex-connectivity and edge-connectivity.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号