Methods and Models for Sparse Random Graphs

智力上的功绩。拟议的研究将处理与稀疏随机图相关的数学问题。这些工作包括开发具有特定度序列的随机图的基本问题的解决方案，开发支持将现实世界网络复杂建模为随机图的数学理论，以及研究和关联稀疏随机图的模型。许多大型的真实世界结构可以被建模为图，并且在广泛的社会科学和自然科学中出现了为特定的真实世界图确定关键属性和设计有效算法的需求。大量的图形结构在社会学中作为代表人类互动的社会网络出现，在流行病学中作为疾病通过人口传播的模型出现，在生物学中出现在包括代谢途径、神经网络和生态系统的食物网在内的各种现象中，在电话数据库和地理信息系统中的通信中出现。互联网的互连网络和万维网的超链接景观(网络图形)是另外两个大规模真实世界图形的突出例子。真实世界图形很少根据精确的全球设计创建；相反，它们根据基本上随机的过程而增长和变化。这些图也很大，无论是否相连，它们几乎总是有少量的边。因此，大多数现实世界的图都可以看作是大量的稀疏随机图。从概率的角度来看，网络和其他大量图的结构一直是一个值得研究的问题，到目前为止最著名的结果是它们的度序列服从幂定律，在这个意义上，d度的顶点数与1=d_成正比。相比之下，过去几年对随机图的广泛研究(从Erdos和Renyi的开创性工作开始)大多集中在经典的随机图模型Gn；p和Gn；m上，这些模型与现实世界图中观察到的具有幂规律和相关度序列的图几乎没有相似之处。由于幂规律度序列是a_x度序列的特例，因此我们建议研究具有a_x度序列的稀疏图的结构和算法问题。我们还建议研究与随机图建模有关的更多技术问题，并建议研究稀疏随机图中的聚类。由于大多数现实世界的图是聚集的，而大多数随机图不是，聚类是海量图建模的一个重要前沿。所提出的研究主要是理论上的，但其动机是发展一门关于现实世界中发生的大规模网络的严格的经验科学。由于真实世界的图形通常是巨大的，我们建议使用的渐近方法应该会产生适用于实践的结果。事实上，理论和应用的目标是相当一致的，因为随机图理论的有效应用的进展几乎肯定需要在理论方面取得实质性的进步。所提出的研究中所描述的基本问题对于进一步理解真实世界巨型图的结构和性质具有广泛的意义。因此，这项拟议的研究有望对整个科学和社会产生广泛的影响。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.