Spectral and probabilistic methods for large sparse graphs

大型稀疏图的谱和概率方法

• 批准号: 0457215
• 负责人: Fan Chung Graham
• 金额: --
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-09-01 至 2008-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0457215&HistoricalAwards=false
• 关键词: Spectral; probabilistic; methods; large; sparse

The proposed research involves several interrelated areas inspectral graph theory, extremal graph theory and random graphs.A main goal is to deduce the fundamental properties and structures ofa graph from its graph spectrum (or from a short list of easilycomputable invariants). Various combinatorial, geometricand probabilistic techniques are being developed for examiningthe relations and behaviors of various graph invariants and properties. The proposed research project includes: (1) Research in spectral graph theory, including spectral Tur'an theorems,quasi-randomness, random walks in directed graphs, Cheeger's inequalityfor directed graphs, (2) Research in random graphs with emphasis on random graphs with given degree distributions,and examining various aspects including giant components, average distance, diameterand eigenvalues distributions,(3) Mathematical models for information networks that generaterandom power law graphs, including the growth-deletion models of preferentialattachments, generalizations of Polya urn's model, duplication models for biologic al networks and the development of tools such as generalizing martigale inequalities for rigorous probabilistic analysis of large networks.Although graph theory has more than 250 years of history, it is only been very recently observed that many realistic networks arising in numerous arenas haveastounding coherence --- similar shapes (power law degree distribution) andhaving the so-called "small world phenomenon" (small distances and clustering). Examples include WWW graphs, call graphs, biological networks and numeroussocial networks. The study of the graph models for various information networks has led to exciting new directions for research in graph theory. In the other direction,graph theory provides tools for analyzing and utilizing large complex networks.The primary objective of the proposed research is to advance our understanding of the intrinsic characteristics and underlying principles that govern large information networks. Such principles are quite effective and essential in dealing with problems in computation and communication involving massive information networks that arise in Internet computing and massive data sets.

这项研究涉及谱图论、极值图论和随机图几个相互关联的领域，主要目的是从图的谱(或从一小部分易于计算的不变量)推导出图的基本性质和结构。人们正在发展各种组合、几何和概率技术来研究各种图不变量和性质的关系和行为。(1)谱图论的研究，包括谱图论、准随机性、有向图中的随机游动、有向图的Cheeger不等式；(2)在随机图中的研究，重点是具有给定度分布的随机图，考察了巨大分量、平均距离、直径和特征值分布等方面；(3)产生随机幂定律图的信息网络的数学模型，包括优先附件的增长-删除模型，Polya‘s模型的推广，虽然图论已有250多年的历史，但直到最近才观察到，许多现实中出现在许多领域的网络具有惊人的一致性-相似的形状(幂定律程度分布)，并具有所谓的“小世界现象”(小距离和聚集)。例如WWW图、调用图、生物网络和众多社交网络。对各种信息网络的图模型的研究为图论的研究带来了令人振奋的新方向。另一方面，图论为分析和利用大型复杂网络提供了工具。拟议研究的主要目标是促进我们对管理大型信息网络的内在特征和潜在原理的理解。在处理互联网计算和海量数据集中出现的涉及海量信息网络的计算和通信问题时，这些原则是非常有效和必要的。