III: Small: Characterizing and exploiting tree-like structure in large social and information networks

最近的技术进步导致了社会、生物和信息网络数据的爆炸式增长。这导致了广泛的度量，例如，度分布，聚类系数，同质度量等，以描述和提取真实网络的洞察力。希望这些指标将帮助领域科学家从这些网络中提取信息和可操作的见解。然而，这种热情尚未得到充分实现；一个持续的挑战是开发更精细的可操作指标来理解真实网络的属性。该项目将促进从大型遗传、医疗、互联网、金融、天文和其他科学网络数据集中提取知识的工具的开发，并将更广泛地加强跨学科教育。更详细地说，这个项目将研究在真实信息网络中描述和利用树状结构的方法。它将集中于图的两个相关但互补的树状概念；它将使用这些概念来开发工具，以表征真正的复杂网络是树状的方式；它将利用这一特征来开发工具，以改进对真实网络的分析。将特别注意这如何能够阐明实际网络中的中等规模结构，即不是非常小规模或地方性的结构，也不是非常大规模或全球性的结构；这个项目的结果将提供算法的实现，以确定如何以及在哪里可以更普遍地利用这种新的理解来进行特定领域的洞察。

Recent technological advances have led to an explosive growth of social, biological, and information network data. This has led to a wide range of metrics, e.g., degree distributions, clustering coefficients, homophily measures, and so on, to describe and extract insight from real networks. The hope is that these metrics will help domain scientists to extract information and actionable insight from these networks. This enthusiasm, however, has not yet been fully realized; and an ongoing challenge is to develop finer actionable metrics to understand the properties of real networks. This project will facilitate the development of tools for the extraction of knowledge from large genetic, medical, internet, financial, astronomical, and other scientific network data sets, and it will enhance interdisciplinary education more generally. In more detail, this project will investigate methods to characterize and exploit tree-like structure in real information networks. It will focus on two related but complementary notions of tree-like-ness for graphs; it will use these notions to develop tools to characterize the manner in which real complex networks are tree-like; and it will use this characterization to develop tools for improved analytics on real networks. Particular attention will be paid to how this can shed light on intermediate-scale, i.e., not very small-scale or local and not very large-scale or global, structure in real networks; and the results of this project will provide implementations of algorithms to determine how and where this new understanding can be exploited for domain-specific insight more generally.