Critical Nodes Identification in Large Networks: The Inclined and Detached Models

In social networks, the departure of some users can lead to the dropout of others from the community in cascade. Therefore, the engagement of critical users can significantly influence the stability of a network. In the literature, the anchored/collapsed k-core problem is proposed, which aims to enlarge/collapse the community by anchoring/deleting certain nodes. While, in real social networks, nodes are usually associated with different preferences, such as close or conflict interest. Intuitively, a community will be more stable if more nodes share close interest and fewer of them carry conflict interest. However, most existing researches simply treat all users equally, and the inclination property is neglected. To fill the gap, in this paper, we propose two novel problems, named inclined anchored k-core (IAK) problem and minimum detached k-core (MDK) problem, to better characterize the real scenarios. We prove that both problems are NP-hard. To facilitate the computation, novel search strategies are proposed. Comprehensive experiments are conducted on 9 networks to demonstrate the effectiveness and efficiency of the proposed techniques.