Spectral and probabilistic methods for large sparse graphs

该研究涉及到检查图理论、极值图理论和随机图等几个相互关联的领域，其主要目标是从图的谱（或从一系列容易计算的不变量）中推导出图的基本性质和结构。各种各样的组合、几何和概率技术正在被开发出来，以检验各种图不变量和性质的关系和行为。拟议的研究项目包括：（1）谱图理论的研究，包括谱图定理，拟随机性，有向图中的随机游动，有向图的Cheeger不等式，（2）随机图的研究，重点是具有给定度分布的随机图，并检查各个方面，包括巨分支，平均距离，直径和特征值分布，（3）生成随机幂律图的信息网络数学模型，包括偏好连接的增长-删除模型，Polya urn模型的推广，生物学网络的复制模型和工具的发展，如推广大型网络的严格概率分析的矩阵不等式。250年的历史，直到最近才观察到，许多现实网络出现在许多领域具有惊人的一致性-相似的形状（幂律度分布）和所谓的“小世界现象”（小距离和聚类）。 例子包括万维网图，调用图，生物网络和大量的社会网络。对各种信息网络的图模型的研究为图论的研究带来了令人兴奋的新方向。在另一个方向上，图论提供了分析和利用大型复杂网络的工具，提出的研究的主要目标是提高我们对管理大型信息网络的内在特征和基本原理的理解。 这些原则在处理涉及互联网计算和海量数据集中出现的海量信息网络的计算和通信问题时非常有效和必要。

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.