Quantifying Node-based Core Resilience
Quantifying Node-based Core Resilience
复制标题
DOI：
10.48550/arxiv.2306.12038
复制
发表时间：
2023-06
期刊：
影响因子：
--
通讯作者：
Jakir Hossain;S. Soundarajan;Ahmet Erdem Sarıyüce
中科院分区：
文献类型：
--
作者：
Jakir Hossain;S. Soundarajan;Ahmet Erdem Sarıyüce
核心分解是各种图分析任务的有效构建块，例如密集子图发现和识别有影响力的节点。核心分解的一个关键弱点是它对图表中的变化非常敏感：插入或删除几条边可能会极大地改变图表的核心结构。因此，必须对给定图表的核心结构进行表征、量化，并在可能的情况下提高其在全球和地方各级的复原力。以往的工作大多考虑整个图或图中重要子图的核心弹性。在这项工作中，我们研究了基于节点的边缘删除和插入时的核心弹性度量。我们首先展示了先前提出的度量核心强度的方法，它不能正确地捕捉边缘去除时节点的核心弹性。接下来，我们引入依赖图的概念来捕捉邻居节点(用于边去除)和可能的未来邻居节点(用于边插入)对给定节点的核数的影响。相应地，我们定义了移除强度和插入强度度量，以分别捕捉单个节点在移除和插入边时的弹性。由于这些测量的天真计算代价高昂，我们提供了基于对核心结构的关键观察而建立的高效启发式方法。我们考虑了两个关键应用，寻找关键边缘和识别有影响力的传播者，以展示我们的新措施在各种现实世界网络和几个基线上的有效性。我们还证明了我们的启发式算法比朴素的方法更有效。
Core decomposition is an efficient building block for various graph analysis tasks such as dense subgraph discovery and identifying influential nodes. One crucial weakness of the core decomposition is its sensitivity to changes in the graph: inserting or removing a few edges can drastically change the core structure of a graph. Hence, it is essential to characterize, quantify, and, if possible, improve the resilience of the core structure of a given graph in global and local levels. Previous works mostly considered the core resilience of the entire graph or important subgraphs in it. In this work, we study node-based core resilience measures upon edge removals and insertions. We first show that a previously proposed measure, Core Strength, does not correctly capture the core resilience of a node upon edge removals. Next, we introduce the concept of dependency graph to capture the impact of neighbor nodes (for edge removal) and probable future neighbor nodes (for edge insertion) on the core number of a given node. Accordingly, we define Removal Strength and Insertion Strength measures to capture the resilience of an individual node upon removing and inserting an edge, respectively. As naive computation of those measures is costly, we provide efficient heuristics built on key observations about the core structure. We consider two key applications, finding critical edges and identifying influential spreaders, to demonstrate the usefulness of our new measures on various real-world networks and against several baselines. We also show that our heuristic algorithms are more efficient than the naive approaches.