An Evolutionary and Local Refinement Approach for Community Detection in Signed Networks

摘要

An approach to detect communities in signed networks that combines Genetic Algorithms and local search is proposed. The method optimizes the concepts of modularity and frustration in order to find network divisions far from random partitions, and having positive and dense intra-connections, while sparse and negative inter-connections. A local search strategy to improve the network division is performed by moving nodes having positive connections with nodes of other communities, to neighboring communities, provided that there is an increase in signed modularity. An extensive experimental evaluation on randomly generated networks for which the ground-truth division is known proves that the method is competitive with a state-of-art approach, and it is capable to find accurate solutions. Moreover, a comparison on a real life signed network shows that our approach obtains communities that minimize the positive inter-connections and maximize the negative intra-connections better than the contestant methods.