BIGDATA: Small: DA: Mining large graphs through subgraph sampling

BIGDATA：小：DA：通过子图采样挖掘大图

• 批准号: 1250786
• 负责人: Harish Sethu
• 金额: $ 54.84万
• 依托单位: Drexel University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-10-01 至 2018-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1250786&HistoricalAwards=false
• 关键词: BIGDATA; Small; DA; Mining; large

The size and complexity of these "Big Data" graphs have always posed significant challenges, limiting the scope of their analysis and thus also limiting the implications that one can draw from them. Mining data from large real-world graphs typically poses two challenges: one of computational resources and another of incomplete information. A comprehensive analysis of these graphs has usually required access to large distributed computing platforms and sophisticated software. This project aims to address a portion of these challenges by investigating a new method, based in statistics and spectral graph theory, to infer essential properties of the full graph through extracting a representative sample of small subgraphs from the full graph. The goal is to reduce the computational burden on researchers interested in large graphs and thus broaden participation in "Big Data" activities. As is now well-understood, the analysis of large graphs has many applications in a variety of fields including business, economics, public policy development, law enforcement, public health, sociology and, of course, computer science. This breadth of applicability and the proposed curriculum development activities have the potential to draw and retain a greater diversity of students into computer science and engineering and increasing the participation by under-represented groups.Many of the principal properties of a graph can be inferred from the graph spectrum (eigenvalues of its adjacency or the normalized Laplacian matrix). In particular, a rich set of interlacing results in spectral graph theory allows one to bound the eigenvalues of the full graph using the eigenvalues of its subgraphs. This project will develop new algorithms for generating subgraph samples, and then use basic estimation theory from statistics and the interlacing results from spectral graph theory to discern properties of a large graph. The new method based on subgraph sampling (as opposed to node or edge sampling) uses results from spectral graph theory and statistics to estimate the spectrum (eigenvalues) of the graph based on the spectrum of the sampled subgraphs. The goal is to allow a meaningful analysis of extremely large graphs without the use of anything beyond a typical desktop computer. The data collected and the algorithms developed as part of this project will be made available to the larger research community through a data repository hosted by Drexel University. The project will also make contributions to open-source software.

这些"大数据"图表的规模和复杂性一直构成重大挑战，限制了其分析范围，从而也限制了人们可以从中得出的影响。从大型真实世界图中挖掘数据通常会带来两个挑战：一个是计算资源，另一个是不完整的信息。 对这些图的全面分析通常需要访问大型分布式计算平台和复杂的软件。该项目旨在通过研究一种基于统计和谱图理论的新方法来解决这些挑战的一部分，通过从全图中提取具有代表性的小子图样本来推断全图的基本属性。其目标是减少对大型图感兴趣的研究人员的计算负担，从而扩大对"大数据"活动的参与。 正如现在所理解的，大型图的分析在各种领域中有许多应用，包括商业，经济学，公共政策制定，执法，公共卫生，社会学，当然还有计算机科学。这种广泛的适用性和拟议的课程开发活动有可能吸引和保留更多的学生进入计算机科学和工程，并增加代表性不足的群体的参与。特别是，谱图理论中丰富的交织结果集允许人们使用其子图的特征值来绑定完整图的特征值。本计画将发展新的演算法来产生子图样本，然后利用统计学的基本估计理论和频谱图理论的交错结果来辨识大型图的性质。 基于子图采样（与节点或边采样相反）的新方法使用谱图理论和统计学的结果，根据采样子图的谱来估计图的谱（特征值）。其目标是允许对非常大的图形进行有意义的分析，而无需使用典型的台式计算机之外的任何东西。作为该项目的一部分，收集的数据和开发的算法将通过德雷克塞尔大学托管的数据存储库提供给更大的研究社区。该项目还将为开源软件做出贡献。