Robust Resilience Blocks Detection Problem in Dynamic Social Networks

Finding a stable community in dynamically developing networks is crucial. In this study, we introduce an innovative concept of resilience, originally rooted in infrastructure networks, and merge it with the distinctive features of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</i>-core graphs to define a novel community structure in dynamic networks-referred to as the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</i>-block. Leveraging the Independent Cascade model, we evaluate communities based on their capacity to sustain activity under adversarial conditions, where an attack is characterized by the blocking of nodes responsible for information propagation. The proposed <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</i>-block demonstrates exceptional robustness against such disruptions. We develop a non-submodular resilience block identification model to identify these resilient communities. Addressing the computational complexity inherent in this task, we propose a groundbreaking two-stage greedy algorithm with a time complexity lower than <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i>(<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">V</i> · <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">E</i>). To validate the algorithm’s efficacy, we conduct extensive experiments on four real-world datasets. The results are meticulously analyzed to evaluate both the algorithm’s performance and its practical applicability. Our findings not only underscore the algorithm’s efficiency but also highlight its potential for real-world deployment in dynamic network analysis.