Approximate Anchored Densest Subgraph Search on Large Static and Dynamic Graphs

Download PDF

Abstract

Densest subgraph search, aiming to identify a subgraph with max-Densest subgraph search, aiming to identify a subgraph with maximum edge density, faces limitations as the edge density inade-imum edge density, faces limitations as the edge density inadequately reflects biases towards a given vertex set 𝑅 . To address this, the 𝑅 -subgraph density was introduced, refining the doubled edge density by penalizing vertices in a subgraph but not in 𝑅 , us-edge density by penalizing vertices in a subgraph but not in 𝑅 , using the degree as a penalty factor. This advancement leads to the Anchored Densest Subgraph (ADS) search problem, which finds the subgraph 𝑆 ˆ with the highest 𝑅 -subgraph density for a given set 𝑅 . Nonetheless, current algorithms for ADS search face signifi-set 𝑅 . Nonetheless, current algorithms for ADS search face significant inefficiencies in handling large-scale graphs or the sizable 𝑅 set. Furthermore, these algorithms require re-computing the ADS whenever the graph is updated, complicating the efficient main-whenever the graph is updated, complicating the efficient maintenance within dynamic graphs. To tackle these challenges, we propose the concept of integer 𝑅 -subgraph density and study the problem of finding a subgraph 𝑆 ∗ ⊆ 𝑉 with the highest integer 𝑅 -subgraph density. We reveal that the 𝑅 -subgraph density of 𝑆 ∗ provides an additive approximation to that of ADS with a difference of less than 1, and hence 𝑆 ∗ is termed the Approximate Anchored Densest Subgraph (AADS). For searching the AADS, we present an efficient global algorithm incorporating the re-orientation network flow technique and binary search, operating in a time polynomial to the graph’s size. Additionally, we propose a novel local algorithm using shortest-path-based methods for the max-flow computation from 𝑠 to 𝑡 around 𝑅 , markedly boosting performance in scenarios with larger 𝑅 sets. For dynamic graphs, both basic and improved algorithms are developed to efficiently maintain the AADS when an edge is updated. Extensive experiments and a case study demon-an edge is updated. Extensive experiments and a case study demonstrate the efficiency, scalability, and effectiveness of our solutions.