Spectral and probabilistic methods for large sparse graphs

本文的研究涉及到检验图论、极值图论和随机图的几个相互关联的领域。其主要目标是从图谱（或从一组易于计算的不变量）中推断出图的基本性质和结构。各种组合的、几何的和概率的技术被用来研究各种图的不变量和性质的关系和行为。建议的研究项目包括：(1)谱图理论的研究，包括谱图的图尔安定理、拟随机性、有向图中的随机行走、有向图的Cheeger不等式；(2)对随机图的研究，重点研究具有给定度分布的随机图，从巨分量、平均距离、直径和特征值分布等方面进行研究；(3)生成随机幂律图的信息网络数学模型；包括优先附件的生长-删除模型，Polya urn模型的推广，生物网络的复制模型，以及用于大型网络严格概率分析的一般化鞅不等式等工具的开发。尽管图论已有250多年的历史，但直到最近才观察到，在许多领域出现的许多现实网络具有惊人的一致性——相似的形状（幂律度分布），并具有所谓的“小世界现象”（小距离和聚类）。例子包括WWW图、呼叫图、生物网络和众多的社交网络。对各种信息网络图模型的研究为图论的研究开辟了令人兴奋的新方向。在另一个方向上，图论提供了分析和利用大型复杂网络的工具。本研究的主要目的是促进我们对管理大型信息网络的内在特征和基本原则的理解。在处理互联网计算和海量数据中出现的涉及海量信息网络的计算和通信问题时，这些原理是非常有效和必要的。

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.