Spectral, Extremal & Probabilistic Methods in Graph Theory with Applications to Information Technology

光谱，极值

• 批准号: 0100472
• 负责人: Fan Chung Graham
• 金额: $ 11.83万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-07-01 至 2004-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0100472&HistoricalAwards=false
• 关键词: Spectral; Extremal; & Probabilistic; Methods

The planned research involves several interrelated areas in spectral graph theory, extremal graph theory and random graphs. A main goal is to deduce the fundamental properties and structures of a graph from its graph spectrum (or from a short list of easily computable invariants). Various combinatorial, geometric and probabilistic techniques are being developed for examining the relations and behaviors of various graph invariants and properties. Although the primary objective is to advance our understanding of the intrinsic characteristics and underlying principles that govern discrete structures, such principles are quite effective and essential in dealing with problems involving massive graphs that arise in Internet computing and massive data sets.A number of combinatorial problems on Internet infrastructures are examined, including the modeling and scaling of massive graphs using probabilistic analysis. Of particular interest is the study of graphs with power law distributions that offer good approximations for realistic networks. The evolution process of large dynamic graphs with only partial information is being analyzed and this has led to challenging problems and new research directions.

计划的研究涉及谱图理论、极值图理论和随机图几个相互关联的领域。其主要目标是从图谱（或从易于计算的不变量的短列表）中推断出图的基本性质和结构。各种组合的、几何的和概率的技术被用来研究各种图的不变量和性质的关系和行为。虽然主要目标是提高我们对控制离散结构的内在特征和基本原则的理解，但这些原则在处理涉及互联网计算和大量数据集中出现的大量图形的问题时非常有效和必要。研究了互联网基础设施上的许多组合问题，包括使用概率分析的海量图的建模和缩放。特别感兴趣的是研究具有幂律分布的图，它为现实网络提供了很好的近似。对仅部分信息的大型动态图的演化过程进行了分析，提出了具有挑战性的问题和新的研究方向。