CAREER: Scalable Algorithms for Spectral Analysis of Massive Networked Systems

互联网、社会网络和遗传网络是由通过复杂的相互作用网络连接的大量单元组成的大规模系统的例子。这一建议旨在提高我们对网络结构和网络动态过程性能之间的关系的理解，例如人类接触网络中疾病的传播，在线社交网络中的信息传播，以及机器人网络中的协调协议。从工程角度来看，这项工作的中心重点将是制定有效的战略，以设计安全和高效的关键网络基础设施。具体地，将探索使网络相对于特定动态过程有效和/或弹性的那些因素。例如，将研究以下问题：什么结构因素使通信网络在一组机器人代理的协调中有效？在人类接触网络中控制疾病传播时，哪些网络属性是有用的？由于网络在科学和工程中无处不在，开发有效的网络分析和设计工具对许多科学学科具有重要意义。拟议的研究计划将与宾夕法尼亚大学涵盖K-12、本科和研究生教育的全面教育议程相辅相成。在K-12教育层面，PI将教授为期三周的复杂网络工程强化课程，以鼓励高中生在STEM相关领域进一步深造。该项目还将支持和培训复杂网络领域的博士生；以及从事短期项目的本科生，重点是提高工程领域中未被充分代表的少数群体的留存率。在过去的十年中，网络科学已经成熟为一个成熟的研究领域，为复杂系统的建模和分析提供了大量工具。特别是，谱图理论领域在一系列强大的网络分析技术的开发中发挥了重要作用，例如谱图划分、社区检测和排名技术(包括Google PageRank)。此外，谱图的性质与许多网络过程的动态行为直接相关，例如振子的同步、多智能体的协调和病毒传播过程。这个项目的目标是开发一个新的计算框架，基于代数图论和实代数几何的最新结果，从局部结构信息推断动态相关的全局谱特性。这一提议中的理论进步将与大规模网络系统频谱分析的可扩展算法的开发齐头并进。此外，这项建议的一个重要部分将集中在开发有效的策略来设计安全和高效的网络动力系统。将考虑的具体设计问题的例子是有效拓扑的设计以促进多智能体机器人系统中的网络内协调，以及网络干预的设计以在人类接触网络中包含病毒过程。在这项建议的过程中，PI将解决一些基本的开放理论问题，并探索与特定领域的专家合作，将新开发的技术应用于各种网络控制问题。

The Internet, social networks, and genetic networks are examples of large-scale systems composed by a large number of units coupled through a complex network of interactions. This proposal aims to improve our understanding of the relationship between the structure of a network and the performance of networked dynamical processes, such as the spread of diseases in human contact networks, the propagation of information in online social networks, and coordination protocols in robotic networks. From an engineering perspective, a central focus of this work will be the development of efficient strategies to design secure and efficient critical networked infrastructures. In particular, those factors that make a network efficient and/or resilient with respect to a particular dynamical process will be explored. For example, the following questions will be studied: What structural factors make a communication network efficient in the coordination of a group of robotic agents? What network properties are useful while containing the spread of a disease in a human contact network? Since networks are ubiquitous across science and engineering, developing efficient tools for network analysis and design is of great relevance to many scientific disciplines. The proposed research program will be complemented with a comprehensive educational agenda spanning K-12, undergraduate, and graduate level education at the University of Pennsylvania. At the level of K-12 education, the PI will teach a three-week intense course about Engineering Complex Networks to encourage high-school students to further pursue an education in STEM-related fields. This project would also support and train doctorate students in the field of complex networks; as well as undergraduate students working on short-term projects, with an emphasis on increasing retention rates of under-represented minorities in engineering.During the last decade, Network Science has matured into an established research field, providing a plethora of tools for modeling and analyzing complex systems. In particular, the field of spectral graph theory has been instrumental in the development of a wide array of powerful network analysis techniques, such as spectral graph partitioning, community detection, and ranking techniques (including Google PageRank). Furthermore, spectral-graph properties are directly related to the dynamical behavior of many networked processes, such as synchronization of oscillators, multi-agent coordination, and viral spreading processes. The goal of this project is to develop a novel computational framework based on recent results from algebraic graph theory and real algebraic geometry to infer global spectral properties of dynamical relevance from local structural information. Theoretical advancements in this proposal will go hand-in-hand with the development of scalable algorithms for spectral analysis of massive networked systems. Furthermore, an important part of this proposal will be focused on developing efficient strategies to design secure and efficient networked dynamical systems. Examples of particular design problems that will be considered are the design of efficient topologies to facilitate in-network coordination in multi-agent robotic systems, as well as the design of network interventions to contain viral processes in human contact networks. During the course of this proposal, the PI will address a number of fundamental open theoretical problems, as well as explore the application of newly developed techniques to a diverse array of network control problems in collaborations with domain-specific experts.