EAGER: Towards New Scalable Stochastic Flow Algorithms

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

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/