Critical Nodes Detection: Node Merging Approach

Various cohesive models are widely employed for the analysis of social networks to identify critical users or key relationships, with the k-core being a particularly popular approach. Existing works, such as the anchor k-core problem, aim to maximize k-core by anchoring nodes (the degree of anchor nodes are set as infinity). However, we find that node merging can also enlarge the k-core size. Different from anchoring nodes, nodes merging can cause both degree increase and decrease which brings more challenges. In this paper, we study the core maximization by node merging problem (CMNM) and prove its hardness. A greedy framework is first presented due to its hardness. To scale for large networks, we categorize potentially influential nodes and provide a detailed analysis of all node merging pairs. Then, based on these analyses, a fast and effective algorithm is developed. Finally, we conduct comprehensive experiments on real-world networks to evaluate the effectiveness and efficiency of the proposed method.