Methods and Models for Sparse Random Graphs

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

Intellectual Merit. The proposed research will deal with mathematical problems relating to sparse random graphs. These include developing solutions for basic problems on random graphs with a speci_ed degree sequence, developing a mathematical theory to support complex modeling of real-world networks as random graphs, and studying and relating models for sparse random graphs.Many large, real-world structures can be modeled as graphs, and the need to determine key properties and design e_cient algorithms for a particular real-world graph arises in a wide range of social and natural sciences. Massive graph structures occur in sociology as social networks representing human interactions, in epidemiology as models of disease transmission through a population, in biology in diverse phenomena including metabolic pathways, neural networks and food webs of ecosystems, and in communications in phone-call databases and geographic information systems (GIS). The interconnection network of the internet and the hyperlinked landscape of theWorld Wide Web (the web graph) are two other prominent examples of massive real-world graphs.Real-world graphs are rarely created according to a precise global design; rather, they grow and change over time according to processes which are fundamentally random. These graphs are also very large, and whether connected or not, they almost always have a small number of edges. Thus, most real-world graphs can be viewed as massive sparse random graphs.The structure of the web and other massive graphs has been a matter of much study from a probabilistic point of view, and the most celebrated result known to date is that their degree sequence obeys a power law, in the sense that the number of vertices of degree d is proportional to 1=d_ for a suitable constant _. In contrast, most of the extensive research on random graphs over the past _fty years (starting with the seminal work of Erdos and Renyi) has been on the classical random graph models Gn;p and Gn;m, which bear little resemblance to the graphs with power-law and related degree sequences that have been observed in real-world graphs.We propose to study structural and algorithmic problems that remain unresolved for sparse random graphs with a _xed degree sequence, since the power-law degree sequence is a special case of a _xed degree sequence. We also propose to investigate some more technical problems involved with modeling random graphs, and we propose to study clustering in sparse random graphs. Since most real world graphs are clustered and most random graphs are not, clustering is an important frontier in modeling massive graphs.The proposed research is largely theoretical, but its motivation is the development of a rigorous empirical science of massive networks that occur in the real world. Since real-world graphs are typically massive, the asymptotic approach we propose to use should yield results applicable in practice. In fact, the theoretical and applied objectives are fairly well-aligned, since progress towards useful applications of the theory of random graphs will almost certainly require substantial advancements on the theoretical front.Broader Impact. The basic problems described in the proposed research have broad implications to furthering the understanding of the structure and properties of real-world massive graphs. Hence the proposed research holds the promise of broad impact across science and society.The PI has a strong commitment to encouraging and including women and minorities, and she will actively encourage such individuals to participate in the proposed research. She will disseminate research results from the proposed work in scholarly journals and conferences, and will post papers describing the research on her webpage.