Methods and Models for Sparse Random Graphs

知识价值。提出的研究将处理与稀疏随机图有关的数学问题。其中包括开发具有特定度序列的随机图的基本问题的解决方案，开发数学理论以支持作为随机图的现实世界网络的复杂建模，以及研究和关联稀疏随机图的模型。许多大型的、现实世界的结构都可以建模为图，在社会科学和自然科学的广泛领域中，需要为一个特定的现实世界的图确定关键属性和设计客户算法。大规模图结构出现在社会学中，作为人类互动的社会网络；在流行病学中，作为疾病在人群中传播的模型；在生物学中，包括代谢途径、神经网络和生态系统的食物网在内的各种现象；以及在电话数据库和地理信息系统（GIS）中的通信中。互联网的互连网络和万维网的超链接景观（网络图）是海量现实世界图的另外两个突出例子。现实世界的图表很少是根据精确的全局设计创建的；相反，它们会根据基本随机的过程随着时间的推移而增长和变化。这些图也非常大，无论是否连通，它们几乎总是有少量的边。因此，大多数现实世界的图都可以看作是大量的稀疏随机图。从概率的角度来看，网络和其他大型图形的结构已经得到了很多研究，迄今为止已知的最著名的结果是它们的度序列遵循幂律，也就是说，对于一个合适的常数_，d度的顶点数与1=d_成正比。相比之下，在过去50年里，大多数关于随机图的广泛研究（从Erdos和Renyi的开创性工作开始）都是关于经典随机图模型Gn；p和Gn；M，它与在实际图中观察到的具有幂律和相关度序列的图几乎没有相似之处。由于幂律度序列是一种特殊情况，我们建议研究具有_xed度序列的稀疏随机图的结构和算法问题。我们还建议研究一些与随机图建模有关的更多技术问题，并建议研究稀疏随机图中的聚类。由于大多数真实世界的图都是聚类的，而大多数随机图则不是，因此聚类是建模海量图的一个重要前沿。拟议中的研究在很大程度上是理论性的，但其动机是发展一门严谨的实证科学，研究现实世界中发生的大规模网络。由于真实世界的图通常是巨大的，我们建议使用的渐近方法应该产生适用于实践的结果。事实上，理论和应用目标是相当一致的，因为随机图理论的有用应用的进展几乎肯定需要理论前沿的实质性进展。更广泛的影响。提出的研究中描述的基本问题对进一步理解现实世界的海量图的结构和性质具有广泛的意义。因此，拟议的研究有望在科学和社会领域产生广泛影响。PI坚定地致力于鼓励和包括妇女和少数民族，她将积极鼓励这些人参与拟议的研究。她将在学术期刊和会议上传播拟议工作的研究成果，并将在她的网页上发布描述研究的论文。

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.