Critical Nodes Detection: Node Merging Approach
Publication Name
WWW 2024 Companion - Companion Proceedings of the ACM Web Conference
Abstract
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.
Open Access Status
This publication may be available as open access
First Page
863
Last Page
866
Funding Number
DP230101445
Funding Sponsor
Australian Research Council