Spectral and probabilistic methods for large sparse graphs

点击翻译按钮获取中文摘要

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.