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.