Computationally tractable graph clustering algorithms for reducing large scale dynamic network models

用于减少大规模动态网络模型的计算易于处理的图聚类算法

• 批准号: 1509302
• 负责人: Carolyn Beck
• 金额: $ 30万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-08-01 至 2019-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1509302&HistoricalAwards=false
• 关键词: Computationally; tractable; graph; clustering; algorithms

The world today is replete with examples of engineering systems, health care systems, scientific results and biomedical problems that can be described using graphs; examples include network routing, image processing, statistical learning, networked dynamic systems, modeling of human contact networks, bioinformatics for the interpretation of microarray gene expression data, and neuroscience studies of functional relationships in the brain. Such graphs frequently have complex structures and may be time-varying. Combined with recent rapid advances in data-collection technology, such as in cyber networks, data search engines, geo-positioning and wireless sensor networks, geographic information systems, and bioinformatics, this has resulted in the need for the development of a comprehensive and systematic framework that allows for the simple analysis and use of such large graph models. As graph-based models for these systems are typically complex and high dimensional, the resulting analysis of their fundamental system behavior is often intractable. We propose an algorithmic framework that addresses a common requirement in the study of these systems - to find simplified graph models that are representative of the original graphs. In parallel with the technical research efforts, educational programs will be developed having a unique interdisciplinary nature with a computational core as the unifying thread. Undergraduates will be involved in simulations that will introduce them to the underlying research fields in a natural and intuitive manner. Targeted activities focused on the emerging prevalence of computational data analysis and optimization in physical and health sciences will be included, with one goal being to attract students from underrepresented groups. This research program addresses the need for reducing the complexity of graph models by uniting concepts from information and optimization theories, network analysis, control and dynamic system theory, and graph theory. The development and application of a general computational framework addressing network and graph-centric aggregation problems will be undertaken. This framework will incorporate domain-specific constraints on network structure; variability in interactions, interdependencies and cost functions; and allow for dynamics in constituent elements and network topologies. The resulting algorithms will be scalable and capable of handling exceptionally large data sets. Conceptually, the proposed framework is based on a stochastic approach where a probability density function is ascribed on the space of decision variables such that the most probable value for the decision variable is an approximate solution to the combinatorial problem under the given constraints. This probability density function is derived using the maximum entropy principle, which is motivated by the law of minimum free energy in physical chemistry; a similar mechanism is employed by nature in solving analogous combinatorial problems. In this project, we will develop a maximum entropy framework that will transcend standard approaches to large-scale graph-reduction problems derived from varied application domains, while exploiting their commonalities. The immediate application domains include neuroscience and epidemic control, with expected long-range potential impacts in biological, chemical and health sciences. The work in this proposal will be apt for the analysis and simplification of human contact networks that lead toward advanced epidemic analysis and control, and projects that incorporate networks of generative models, such as classification of brain-activity data from brain machine interfaces to predict motor intent for the purpose of guiding prosthetic devices. The proposed framework facilitates the inclusion of information and constraints that are unique to these applications and not adequately covered in existing methods.

当今世界充满了可以用图形描述的工程系统、医疗保健系统、科学成果和生物医学问题的例子;例子包括网络路由、图像处理、统计学习、网络动态系统、人类接触网络建模、用于解释微阵列基因表达数据的生物信息学以及大脑功能关系的神经科学研究。 这样的图通常具有复杂的结构，并且可能是时变的。再加上最近在数据收集技术方面的迅速进展，例如在计算机网络、数据搜索引擎、地理定位和无线传感器网络、地理信息系统和生物信息学方面的进展，这就需要开发一个全面和系统的框架，以便能够简单地分析和使用这种大型图形模型。 由于这些系统的基于图的模型通常是复杂和高维的，因此对其基本系统行为的分析通常是棘手的。 我们提出了一个算法框架，解决了这些系统的研究中的一个共同的要求-找到简化的图形模型，是原始图形的代表。 在技术研究工作的同时，将开发具有独特的跨学科性质的教育计划，以计算核心为统一的线程。本科生将参与模拟，这将以自然和直观的方式向他们介绍基础研究领域。将包括针对物理和健康科学中计算数据分析和优化的新兴流行的有针对性的活动，其目标之一是吸引来自代表性不足群体的学生。该研究计划解决了通过统一信息和优化理论，网络分析，控制和动态系统理论以及图论的概念来降低图形模型复杂性的需求。 一个通用的计算框架解决网络和图形为中心的聚合问题的发展和应用将进行。 这一框架将纳入对网络结构的特定领域限制;相互作用、相互依存和成本函数的可变性;并考虑到构成要素和网络拓扑结构的动态性。由此产生的算法将是可扩展的，并能够处理非常大的数据集。从概念上讲，所提出的框架是基于一个随机的方法，其中的概率密度函数是归因于空间的决策变量，使决策变量的最可能的值是一个近似的解决方案，在给定的约束条件下的组合问题。这个概率密度函数是使用最大熵原理导出的，这是由物理化学中的最小自由能定律激发的;在解决类似的组合问题时，自然界也采用了类似的机制。在这个项目中，我们将开发一个最大熵框架，它将超越标准方法来解决来自不同应用领域的大规模图约简问题，同时利用它们的共性。直接应用领域包括神经科学和流行病控制，预计在生物、化学和健康科学方面具有长期潜在影响。该提案中的工作将适用于分析和简化人类接触网络，从而实现先进的流行病分析和控制，以及结合生成模型网络的项目，例如对来自脑机接口的脑活动数据进行分类，以预测运动意图，从而指导假肢设备。 拟议的框架有助于纳入这些应用程序所特有的信息和限制，而现有方法没有充分涵盖这些信息和限制。