Eigenvectors of random graphs & diffusions on simplices

随机图的特征向量

• 批准号: 1007563
• 负责人: Soumik Pal
• 金额: $ 14.74万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-07-01 至 2014-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1007563&HistoricalAwards=false
• 关键词: Eigenvectors; random; graphs; diffusions; simplices

The PI proposes two long term directions in his research in Probability theory. The first one involves study of spectral and eigenvectors properties of sparse random graphs. This is a joint work with Ioana Dumitriu. Eigenvectors of graph adjacency or laplacian matrices have natural significance as solutions of combinatorial optimization problems. However, very little theoretical results are known about eigenvectors of random graphs. Our ongoing investigation combines methods and intuition from the Random Matrix Theory with graph combinatorics. We have so far succeeded in obtaining interesting results for random regular graphs where we show that, when the degree grows poly-logarithmically with the order, the adjacency matrix displays some of the properties of the Gaussian Orthogonal Ensembles. Eventually we plan to study ``real world'' graphs, particularly the ones with a given degree distribution. The second direction is the construction and study of a diffusion on the space of continuum trees whose reversible measure is the Brownian CRT, as conjectured by David Aldous. This appears as a limit of natural discrete Markov chains on finite phylogenetic trees. Continuum trees are of great significance as they appear as the limiting state space of several families of random trees and random planar maps (via Schaeffer bijection). It appears from our ongoing study that this limiting diffusion is a new kind of measure-valued process on the space of such trees, reminiscent of the classical Fleming-Viot model. The proposed method is a continuation of ideas developed by the PI in related recent work.Random graphs and networks are popular in diverse areas such as social networks, models for the internet, computer vision, and number theory. Several natural optimization problems on graphs (e.g., figuring out clusters, or ranking algorithms such as Google PageRank) involve what are called eigenvectors of the graph. If the network grows randomly, its eigenvectors are random, and it is of interest to study its properties. A study of such properties is listed as one of our main research areas. The other main area involves the structure of phylogenetic (or evolutionary) trees. A lot of recent interest in Biology and related mathematics is in the structure of the collection of all possible evolutionary trees. This is an enormous space very different from the usual Euclidean (say, three dimension) space. One way to explore this set is to let a Markov chain jump around from tree to tree randomly in a ``nice'' way. A few such models have been proposed in the literature. We take up the study of one of them which is related to other areas of Probability. The analysis and results are expected to be quite novel in the subject area.

PI在概率论研究中提出了两个长期方向。第一个是稀疏随机图的谱和特征向量性质的研究。这是与Ioana Dumitriu的合作作品。图的邻接矩阵或拉普拉斯矩阵的特征向量作为组合优化问题的解有着天然的意义。然而，关于随机图的特征向量的理论结果知之甚少。我们正在进行的研究结合了随机矩阵理论与图组合学的方法和直觉。到目前为止，我们已经成功地获得有趣的结果，随机正则图，我们表明，当度的增长poly-ethnically与顺序，邻接矩阵显示的高斯正交系综的一些属性。最终，我们计划研究“真实的世界”图，特别是具有给定度分布的图。第二个方向是构造和研究连续树空间上的扩散，其可逆测度是布朗CRT，如大卫奥尔德斯所述。这似乎是有限系统发育树上的自然离散马尔可夫链的一个极限。连续统树是非常重要的，因为它们作为几个随机树族和随机平面映射（通过Schaeffer双射）的极限状态空间出现。从我们正在进行的研究中可以看出，这种极限扩散是这种树的空间上的一种新的测度值过程，让人想起经典的Fleming-Viot模型。随机图和网络在社交网络、互联网模型、计算机视觉和数论等不同领域都很受欢迎。图上的几个自然优化问题（例如，计算出聚类，或排名算法，如Google PageRank）涉及所谓的图的特征向量。如果网络是随机增长的，那么它的特征向量也是随机的，因此研究它的性质是很有意义的。这类性质的研究被列为我们的主要研究领域之一。另一个主要领域涉及系统发育（或进化）树的结构。最近生物学和相关数学中的很多兴趣都集中在所有可能的进化树的集合的结构上。这是一个巨大的空间，与通常的欧几里德（比如三维）空间非常不同。探索这个集合的一种方法是让马尔可夫链以一种“好”的方式随机地从一棵树跳到另一棵树。在文献中已经提出了一些这样的模型。我们开始研究其中之一，这与其他领域的概率。分析和结果预计将是相当新颖的主题领域。