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.

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