The proposed 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. 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 inequality for 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, diameter and eigenvalues distributions, (3) Mathematical models for information networks that generate random power law graphs, including the growth-deletion models of preferential attachments, 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 have astounding coherence --- similar shapes (power law degree distribution) and having the so-called "small world phenomenon" (small distances and clustering). Examples include WWW graphs, call graphs, biological networks and numerous social 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.
