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

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

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.