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

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.

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

项目成果

On Finding and Analyzing the Backbone of the k-Core Structure of a Graph

• DOI: 10.1109/icdm54844.2022.00124
• 发表时间: 2022-11
• 期刊: 2022 IEEE International Conference on Data Mining (ICDM)
• 作者: Ricky Laishram;S. Soundarajan

NetProtect: Network Perturbations to Protect Nodes against Entry-Point Attack

NetProtect：通过网络扰动保护节点免受入口点攻击

• DOI: 10.1145/3447535.3462500
• 发表时间: 2021
• 期刊: ACM Web Science Conference
• 作者: Laishram, Ricky;Hozhabrierdi, Pegah;Wendt, Jeremy;Soundarajan, Sucheta
• 通讯作者: Soundarajan, Sucheta

Fairness of Information Flow in Social Networks

• DOI: 10.1145/3578268
• 发表时间: 2022-12
• 期刊: ACM Transactions on Knowledge Discovery from Data
• 影响因子: 3.6
• 作者: Zeinab S. Jalali;Qilan Chen;S. M. Srikanta;Weixiang Wang;Myunghwan Kim;Hema Raghavan;S. Soundarajan