Distributed Detection of Critical Nodes in Wireless Sensor Networks Using Maximum Independent Set

Identifying key nodes in a network is crucial for practical applications, especially when it comes to accurately detecting cut vertices, which play a vital role in maintaining network stability. As network complexity increases, relying on a single method to identify key nodes often fails to provide a comprehensive assessment of node importance in real-world scenarios. To address this, this paper proposes a novel framework for cut vertex identification that evaluates node importance from three perspectives: weighted fusion centrality metrics, the spanning tree algorithm, and topology graph properties. Additionally, existing methods based on centrality metrics often struggle with low accuracy in identifying cut vertices. To overcome this limitation, we have devised a method, termed the MIS-CV algorithm, that enables the accurate identification of network cut vertices by solely evaluating the intersection of node neighborhoods within the maximum independent set. We validated our proposed algorithm through simulation analysis on the Barabasi-Albert scale-free network. The results demonstrate that the MIS-CV key nodes identification algorithm surpasses traditional search tree algorithms in terms of both accuracy and operational efficiency. This proves that the MIS-CV algorithm has higher recognition accuracy without increasing computational complexity.