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

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

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.