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

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

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.