EAGER: Towards New Scalable Stochastic Flow Algorithms

EAGER：迈向新的可扩展随机流算法

• 批准号: 1141828
• 负责人: Srinivasan Parthasarathy
• 金额: $ 15万
• 依托单位: Ohio State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-08-01 至 2012-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1141828&HistoricalAwards=false
• 关键词: EAGER; Towards; New; Scalable; Stochastic

The process of clustering or partitioning of nodes within a graph is a fundamental task with applications in many areas ranging from social network analysis to chip design and from biological network analysis to the analysis of intelligence networks. This project seeks to explore and develop a new class of algorithms for graph clustering based on the principle of stochastic flows. Such algorithms have been used effectively on small scale biological networks and have been shown to be robust to noise effects. However, widespread utilization has been limited due to the lack of scalability of the algorithm and its inability, in its current form, to accommodate domain-specific constraints on clustering.This exploratory project seeks to address these two limitations: First, it seeks to develop a novel approach for supporting flexible clustering in the context of stochastic flow clustering, allowing users to control the skew of the resulting clustering arrangement (e.g., to ensure balanced clusters), and allowing the nodes of a graph to participate in multiple clusters (so as to allow clusters to overlap). Second, it seeks to develop solutions that can scale to very large graphs (e.g. social networks, web graphs) through the innovative applications of graph sparsification and novel parallel algorithms on high performance systems. Open source implementation of the resulting a proof-of-concept solution will be distributed to the broader scientific community. The scientific impact of this exploratory research agenda include the following: First, if one is successful in scaling up stochastic flow algorithms to web-scale datasets while retaining its many advantages, this would open up a viable robust and improved alternative to the current state-of-the art. Second, one can also employ stochastic flow clustering algorithms in a manner analogous to spectral methods on more traditional data sources (non-graphical), enabling more wide-spread use of flow clustering algorithms. The broader impacts of the project include increased research-based training opportunities for undergraduate and graduate students in data analytics. Additional information about the project can be found at: http://www.cse.ohio-state.edu/~srini/EAGER11/

图中节点的聚类或划分过程是一项基本任务，在许多领域都有应用，从社会网络分析到芯片设计，从生物网络分析到智能网络分析。本项目旨在探索和开发一类基于随机流原理的图聚类新算法。这种算法已被有效地用于小规模的生物网络，并已被证明是强大的噪声影响。然而，由于算法缺乏可扩展性，并且在当前形式下无法适应特定于域的聚类约束，因此广泛使用受到限制。这个探索性项目旨在解决这两个限制：首先，它旨在开发一种新的方法，支持灵活的集群的背景下，随机流聚类，从而允许用户控制所得到的群集布置的偏斜（例如，以确保平衡的集群），以及允许图的节点参与多个集群（以便允许集群重叠）。其次，它寻求开发解决方案，可以扩展到非常大的图形（例如社交网络，网络图），通过创新的应用程序的图形稀疏化和新的并行算法的高性能系统。由此产生的概念验证解决方案的开源实施将分发给更广泛的科学界。 这一探索性研究议程的科学影响包括：首先，如果一个人成功地将随机流算法扩展到网络规模的数据集，同时保留其许多优点，这将为当前最先进的技术开辟一个可行的鲁棒和改进的替代方案。还可以以类似于谱方法的方式对更传统的数据源采用随机流聚类算法（非图形化），使得能够更广泛地使用流聚类算法。该项目更广泛的影响包括为本科生和研究生提供更多的数据分析研究培训机会。有关该项目的更多信息，请访问：http://www.cse.ohio-state.edu/~srini/EAGER11/