CAREER: Modeling and Analysis of Data from Massive Graphs

职业：海量图表数据的建模和分析

• 批准号: 0547744
• 负责人: Anna Gilbert
• 金额: $ 40万
• 依托单位: Regents of the University of Michigan - Ann Arbor
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-05-15 至 2012-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0547744&HistoricalAwards=false
• 关键词: CAREER; Modeling; Analysis; Data; Massive

This project defines a new approach to massive graphs that identifies three fundamental challenges common to many applications: scale, dynamism, and uncertainty. The project advances graph compression schemes that are universal and independent of the application to summarize massive graphs at large scales. These algorithms should be highly efficient, using a small amount of space and time to produce a compressed representation. Furthermore, these algorithms should be provably correct. In addition, the tools should be adapted to dynamic graph data. They should learn a model of the graph from historical data. Finally, this project will design tools that can infer graph properties from samples of a massive graph, since such a graph cannot be observed in its entirety. In applications where sampling schemes can be devised, we strive to do so as effectively and as efficiently as possible.brbrWe live in an information age. Behind many of our technological, scientific, and economic forces are large volumes of data. An increasingly important type of data is relational data or graph data. These data capture how entities are related to one another, how they interact with one another, or how objects are linked together. All forms of communication amongst entities give rise to graph data, including the communication of source and destination IP addresses via IP packets in the Internet, people sending email to one another, web pages referring to one another, or proteins interacting with one another in large biological systems. Many scientific, engineering, and medical applications depend on our abilities to model, to analyze, to process, and to synthesize this type of data quickly, in the face of changes to the data, and under imperfect information. Indeed, our security and the security of the Internet may hinge upon our understanding of how entities (be they people or IP addresses) interact with one another. Our current statistical and algorithmic tools for relational data are not adequate for massive graphs. They have not kept pace with our ability to collect enormous amounts of data and our need to accurately and efficiently analyze that data. We must be able to model, to compress, and to highlight the important features of graphs that are gigantic, that evolve over time (perhaps quickly), and that may capture a limited view of a larger graph. This project aims to develop robust, highly efficient, and provably correct methods for managing massive graphs.

该项目定义了一种处理海量图的新方法，它确定了许多应用程序常见的三个基本挑战：规模、动态和不确定性。 该项目提出了通用且独立于应用程序的图压缩方案，以大规模总结海量图。 这些算法应该非常高效，使用少量的空间和时间来生成压缩表示。 此外，这些算法应该被证明是正确的。 此外，这些工具应该适应动态图形数据。 他们应该从历史数据中学习图表模型。 最后，该项目将设计可以从大量图的样本中推断图属性的工具，因为这样的图无法被完整地观察到。 在可以设计采样方案的应用中，我们努力尽可能有效和高效地设计采样方案。brbr我们生活在信息时代。 我们许多技术、科学和经济力量的背后都是大量的数据。 越来越重要的数据类型是关系数据或图形数据。这些数据捕获实体如何相互关联、它们如何相互交互或对象如何链接在一起。 实体之间所有形式的通信都会产生图形数据，包括通过互联网中的 IP 数据包进行源 IP 地址和目标 IP 地址的通信、人们相互发送电子邮件、相互引用的网页或蛋白质在大范围内相互交互生物系统。 许多科学、工程和医学应用都依赖于我们在面对数据变化和不完善信息的情况下快速建模、分析、处理和合成此类数据的能力。 事实上，我们的安全和互联网的安全可能取决于我们对实体（无论是人还是 IP 地址）如何相互交互的理解。 我们当前的关系数据统计和算法工具不足以处理海量图表。 他们没有跟上我们收集大量数据的能力以及我们准确有效地分析这些数据的需求。 我们必须能够对巨大图的重要特征进行建模、压缩和突出显示，这些特征会随着时间的推移（也许很快）而演变，并且可能会捕获更大图的有限视图。 该项目旨在开发稳健、高效且可证明正确的方法来管理海量图。