Collaborative Research: SHF: Medium: NetSplicer: Scalable Decoupling-based Algorithms for Multilayer Network Analysis

多层网络是对社会、经济、生物和技术系统进行建模和分析的强大且富有表现力的数学工具。非正式地说，多层网络是相关图形的集合。多层网络的应用包括了解社交网络、经济系统、在线市场，以及检测网络物理系统中的漏洞。虽然这一研究领域正在迅速增长，但缺乏用于分析来自不同应用的大规模网络的计算工具。该项目将开发在现代计算系统上分析超大型多层网络的理论基础和软件基础设施，从而使其能够在不同的应用中广泛使用。该项目将开发用于多层网络分析的一组可扩展的高性能算法NetSplier。NetSplier中的方法将基于一种名为网络解耦的分而治之的技术。通过解耦，多层网络可以细分为多个组件，每个组件都可以使用已知的图算法进行潜在分析。网络分离寻求解决对多层分析至关重要的问题，例如减少信息损失和保留结构和语义信息。有效应用网络解耦的挑战包括确定最优解耦策略、保留具有多个顶点和边类型的多层网络的结构和内容，以及开发适用于网络不同层的架构感知可扩展算法。该项目将为多个研究社区提供新的能力，并将为多层网络建立一个储存库。与学术界和工业界领域科学家的计划合作，以及课程开发和推广活动，将塑造项目开发努力，以最大限度地发挥影响。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

A multilayer network is a powerful and expressive mathematical tool for modeling and analyzing social, economic, biological, and technological systems. Informally, a multilayer network is a collection of related graphs. Applications of multilayer networks include understanding social networks, economic systems, online marketplaces, and detecting vulnerabilities in cyber-physical systems. While this research area is rapidly growing, there is a dearth of computational tools for analyzing large-scale networks from diverse applications. This project will develop the theoretical foundations and software infrastructure for analyzing very large multilayer networks on modern computing systems, thereby enabling their widespread use in diverse applications.This project will develop NetSplicer, a collection of scalable high-performance algorithms for multilayer-network analysis. The approaches in NetSplicer will be based on a divide-and-conquer-like technique called network decoupling. Using decoupling, the multilayer network can be subdivided into multiple components, each of which could be potentially analyzed using known graph algorithms. Network decoupling seeks to address issues that are critical for multilayer analysis, such as reducing information loss and preserving structural and semantic information. The challenges in efficiently applying network decoupling include determining optimal decoupling strategies, preserving the structure and content of multilayer networks that have multiple vertex and edge types, and developing architecture-aware scalable algorithms that apply across different layers of a network. This project will provide a new capability for multiple research communities and will build a repository for multilayer networks. The planned collaborations with domain scientists from academia and industry, as well as curriculum development and outreach activities, will shape project development efforts to maximize impact.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.