Overlapping Community Detection in Directed and Undirected Attributed Networks Using a Multiobjective Evolutionary Algorithm

In many real-world networks, the structural connections of networks and the attributes about each node are always available. We typically call such graphs attributed networks, in which attributes always play the same important role in community detection as the topological structure. It is shown that the very existence of overlapping communities is one of the most important characteristics of various complex networks, while the majority of the existing community detection methods was designed for detecting separated communities in attributed networks. Therefore, it is quite challenging to detect meaningful overlapping structures with the combination of node attributes and topological structures. Therefore, in this article, we propose a multiobjective evolutionary algorithm based on the similarity attribute for overlapping community detection in attributed networks (MOEA-SA(OV)). In MOEA-SA(OV), a modified extended modularity EQOV, dealing with both directed and undirected networks, is well designed as the first objective. Another objective employed is the attribute similarity SA. Then, a novel encoding and decoding strategy is designed to realize the goal of representing overlapping communities efficiently. MOEA-SA(OV) runs under the framework of the nondominated sorting genetic algorithm II (NSGA-II) and can automatically determine the number of communities. In the experiments, the performance of MOEA-SA(OV) is validated on both synthetic and real-world networks, and the experimental results demonstrate that our method can effectively find Pareto fronts about overlapping community structures with practical significance in both directed and undirected attributed networks.

Automated summary

Detecting overlapping communities in attributed networks is challenging. In this article, a multiobjective evolutionary algorithm based on attribute similarity was proposed to effectively find overlapping community structures with practical significance.