The Multi-Label Propagation Algorithm (MLPA) identifies and reveals community structure by passing labels between network nodes, and is also suitable for dealing with complex networks with overlapping communities. Due to its flexibility and effectiveness, the algorithm has been successfully applied in a number of fields, including image segmentation, text classification, and bioinformatics. In today’s society where personal privacy protection is increasingly important, how to detect communities without revealing sensitive information has become a hot issue in the field of network analysis. Existing privacy-preserving multi-label propagation algorithms primarily rely on anonymization and homomorphic encryption techniques. While homomorphic encryption can protect privacy, the complex encryption and decryption processes incur significant computational costs, making it challenging to achieve efficient computation while ensuring accuracy and privacy. In this paper, we propose a Secure and Efficient Federated Multi-Label Propagation Algorithm (SEFMLPA) that combines an anonymization strategy with a secret sharing strategy, considering the attribute similarities between nodes to ensure privacy, accuracy, and efficiency. The experimental results indicate that SEFMLPA achieves an accuracy comparable to the latest algorithms and reduces runtime by 80%. These significant improvements validate the effectiveness and superiority of our approach.