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.

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