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

III：小型：描述和利用大型社交和信息网络中的树状结构

• 批准号: 1423621
• 负责人: Michael Mahoney
• 金额: $ 50万
• 依托单位: International Computer Science Institute
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-09-15 至 2017-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1423621&HistoricalAwards=false
• 关键词: III; Small; Characterizing; exploiting; tree

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.

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