Eigenvectors of random graphs: Nodal Domains
Eigenvectors of random graphs: Nodal Domains
复制标题
随机图的特征向量：节点域
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
N. Linial
中科院分区：
文献类型：
--
作者：
Y. Dekel;James R. Lee;N. Linial
本文对随机图的特征向量进行了系统的研究。尽管关于图的特征值以及它们如何反映底层图的属性已经知道很多，但关于相应的特征向量却知之甚少。我们在这篇文章中的主要重点是与不同的本征函数的节点域。在黎曼流形的拉普拉斯类似的领域，节点域已经被深入研究了一百多年。图形节点域原来有有趣的和意想不到的性质。我们的主要定理断言，有一个常数c，使得几乎每个图G，G的每个特征函数有最多两个大的节点域，此外，在这些主要领域之外的最多c个例外顶点。我们还讨论了这些问题的变化，并简要报告了一些数值实验，特别是，建议几乎肯定有两个节点域，没有例外的顶点。© 2010 Wiley Periodicals，Inc.随机结构算法，39、39-58、2011
We initiate a systematic study of eigenvectors of random graphs. Whereas much is known about eigenvalues of graphs and how they reflect properties of the underlying graph, relatively little is known about the corresponding eigenvectors. Our main focus in this article is on the nodal domains associated with the different eigenfunctions. In the analogous realm of Laplacians of Riemannian manifolds, nodal domains have been the subject of intensive research for well over a hundred years. Graphical nodal domains turn out to have interesting and unexpected properties. Our main theorem asserts that there is a constant c such that for almost every graph G, each eigenfunction of G has at most two large nodal domains, and in addition at most c exceptional vertices outside these primary domains. We also discuss variations of these questions and briefly report on some numerical experiments which, in particular, suggest that almost surely there are just two nodal domains and no exceptional vertices. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 39, 39–58, 2011
DOI：
10.1073/pnas.0500334102
发表时间：
2005-05-24
影响因子：
11.1
作者：
Coifman, RR;Lafon, S;Zucker, SW
通讯作者：
Zucker, SW