III: Small: Collaborative Research: Resilience Analysis for Core Decomposition in Real-World Networks

网络的恢复力通常被定义为在遭受故障和攻击时继续良好运行的能力。设计和开发对丢失数据、不完整的网络观察或数据收集中的错误具有健壮性的图形分析算法在许多真实世界的应用程序中是必不可少的。图分析方法的一个基本和重要的类别是那些在给定网络中寻找密集区域的方法。这些方法在生物信息学、社会网络分析、路由器网络监控、可视化等领域都有应用。核分解是一种寻找稠密子图的有效算法，已被证明在理解来自不同领域的复杂网络结构方面非常有用。然而，众所周知，它对网络结构的微小变化缺乏健壮性。本项目将探索和表征核心分解过程的健壮性，并开发攻击(和相应的防御)策略来操纵网络以阻碍核心分解分析。这项研究的结果将允许增加对真实世界网络上的精确度核心分解分析的理解，并提出对噪声或丢失数据更稳健的新的、相关的分解。该项目将分三个部分执行：1)探索和表征核心分解的稳健性以开发各种技术和度量来量化其稳健性；2)开发图形修改攻击策略以通过添加/删除节点或边来篡改网络的核心结构--该项目考虑了三种类型的攻击：以节点的核心编号为目标的攻击、由核心分解引起的子图以及由核心分解引起的层级攻击3)针对网络核心结构的攻击，制定相应的防御策略。鉴于核心分解的广泛应用空间，该项目将增加描述网络分层结构、检测中心节点、发现异常以及加快其他任务(如社区检测)算法的健壮性。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

The resilience of a network is generally defined as its ability to continue performing well when it is subject to failures and attacks. Designing and developing graph analysis algorithms that are robust against missing data, incomplete network observation, or errors in data collection is essential in many real-world applications. One fundamental and important class of graph analysis methods are those that find the dense regions in a given network. These methods have applications in bioinformatics, social network analysis, router network monitoring, visualization, and other areas. Core decomposition, a powerful and efficient algorithm for finding dense subgraphs, has been proven to be extremely useful in understanding the structure of complex networks from a variety of domain. However, it is notoriously non-robust against small changes in the network structure. This project will explore and characterize the robustness of core decomposition process and develop attack (and corresponding defense) strategies to manipulate the network to hinder the core decomposition analysis. The outcome of this research will allow for increased understanding of the accuracy core decomposition analyses on real-world networks, and propose new, related decompositions that are more robust against noise or missing data.The project will be performed in three parts: 1) Exploring and characterizing the robustness of core decomposition to develop a variety of techniques and metrics to quantify the robustness, 2) Developing graph modification 'attack' strategies to tamper with a network's core structure by adding/deleting nodes or edges -- the project considers three types of attacks: those targeting nodes' core numbers, the subgraphs induced by the core decomposition, and the hierarchy induced by the core decomposition, 3) Developing corresponding strategies to defend against the attacks on a network's core structure. Given the wide application space of core decomposition, this project will increase the robustness of algorithms for describing the hierarchical structure of a network, detecting central nodes, spotting the anomalies, and speeding up algorithms for other tasks, like community detection.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.