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.