Higher Order Local Search Assisted Community Detection in Signed Networks

Community detection in signed networks reveals mesoscale structures and sign characteristics, facilitating accurate and realistic understanding of real-life signed networks. Given the complexity of signed community structures and the NP-hard challenge of achieving optimal partitions, modularity optimization using memetic algorithms has emerged as a promising approach. However, the identified signed partitions still face challenges in modularity quality and precision, with many misassigned nodes or being stuck at local optima, particularly in ambiguous and complex structures. To address this issue, this article introduces a new concept: central-node signed motif, a higher order local topological feature that effectively identifies signed communities, providing richer and more efficient topological information. Furthermore, we utilize these central-node signed motifs to improve community detection through a framework named higher order local search assisted memetic modularity (HLSMM). In HLSMM, we design a central-node signed motif-based local search strategy to optimize node assignments and improve modularity quality and structural balance of optimized signed communities. Experimental results from synthetic and real-world datasets demonstrate the effectiveness of the local search strategy in enhancing accuracy and modularity quality. HLSMM exhibits a general advantage in modularity quality over currently representative methods on real-world datasets, particularly in ambiguous and complex community structures.