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

III：小：协作研究：现实世界网络中核心分解的弹性分析

• 批准号: 1908048
• 负责人: Sucheta Soundarajan
• 金额: $ 25万
• 依托单位: Syracuse University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-10-01 至 2024-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1908048&HistoricalAwards=false
• 关键词: III; Small; Collaborative; Research; Resilience; III; Small; Collaborative; Research; Resilience

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.

网络的弹性通常被定义为在受到故障和攻击的情况下，其继续表现良好的能力。在许多现实世界应用中，设计和开发图形分析算法对丢失数据，不完整的网络观察或数据收集错误都是可靠的。一种基本和重要的图形分析方法是那些在给定网络中找到密集区域的方法。 这些方法在生物信息学，社交网络分析，路由器网络监控，可视化和其他领域中具有应用。核心分解是一种用于查找密集子图的强大而有效的算法，已被证明在理解各种领域的复杂网络的结构方面非常有用。但是，众所周知，它对网络结构的微小变化是不可能的。该项目将探索并表征核心分解过程的鲁棒性，并制定攻击（以及相应的防御）策略，以操纵网络以阻碍核心分解分析。 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通过添加/删除节点或边缘 - 项目考虑三种类型的攻击：针对节点的核心数字的攻击，核心分解引起的子图以及核心分解引起的层次结构，3）制定相应的策略来防御网络核心结构的攻击。鉴于核心分解的广泛应用空间，该项目将增加算法的鲁棒性来描述网络的层次结构，检测中心节点，发现异常，并加快其他任务的算法加快算法，例如社区侦查，例如NSF的法定任务和审查范围的范围。