NI-MLA: Node Importance based Multi-level Label Assignment strategy for community detection in sparse social graphs

Abstract

This research paper addresses the challenge of detecting communities in sparse social graphs and presents a novel approach that leverages node importance and label propagation. The proposed method consists of three phases: initialization, label assignment, and filtering. In the initialization phase, we carefully identify and designate key nodes using their local information and associate them with different labels. Subsequently, in the label assignment phase, the assigned labels are propagated to neighboring nodes, which are organized in a multilevel manner, taking into account their relevance and significance. Through the filtering phase, we effectively eliminate irrelevant labels, enhancing the accuracy of community assignments and resulting in an optimized community structure. To assess the effectiveness of our approach, we conducted experiments on both real-world networks and synthetic networks. A comparative analysis was performed against several established community detection techniques from existing literature. The results clearly demonstrate that our proposed algorithm surpasses existing methods in terms of accuracy and efficiency.