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

Abstract

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<inline-formula> <tex-math notation="LaTeX">$_{OV}$ </tex-math></inline-formula>). In MOEA-SA<inline-formula> <tex-math notation="LaTeX">$_{OV}$ </tex-math></inline-formula>, a modified extended modularity <inline-formula> <tex-math notation="LaTeX">$EQ_{OV}$ </tex-math></inline-formula>, dealing with both directed and undirected networks, is well designed as the first objective. Another objective employed is the attribute similarity <inline-formula> <tex-math notation="LaTeX">$S_{A}$ </tex-math></inline-formula>. Then, a novel encoding and decoding strategy is designed to realize the goal of representing overlapping communities efficiently. MOEA-SA<inline-formula> <tex-math notation="LaTeX">$_{OV}$ </tex-math></inline-formula> runs under the framework of the nondominated sorting genetic <xref ref-type="algorithm" rid="alg2">algorithm II</xref> (NSGA-II) and can automatically determine the number of communities. In the experiments, the performance of MOEA-SA<inline-formula> <tex-math notation="LaTeX">$_{OV}$ </tex-math></inline-formula> 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.