A Multiobjective Evolutionary Algorithm Based on Structural and Attribute Similarities for Community Detection in Attributed Networks

Most of the existing community detection algorithms are based on vertex connectivity. While in many real networks, each vertex usually has one or more attributes describing its properties which are often homogeneous in a cluster. Such networks can be modeled as attributed graphs, whose attributes sometimes are equally important to topological structure in graph clustering. One important challenge is to detect communities considering both topological structure and vertex properties simultaneously. To this propose, a multiobjective evolutionary algorithm based on structural and attribute similarities (MOEA-SA) is first proposed to solve the attributed graph clustering problems in this paper. In MOEA-SA, a new objective named as attribute similarity SA is proposed and another objective employed is the modularity Q. A hybrid representation is used and a neighborhood correction strategy is designed to repair the wrongly assigned genes through making balance between structural and attribute information. Moreover, an effective multi-individual-based mutation operator is designed to guide the evolution toward the good direction. The performance of MOEA-SA is validated on several real Facebook attributed graphs and several ego-networks with multiattribute. Two measurements, namely density T and entropy E, are used to evaluate the quality of communities obtained. Experimental results demonstrate the effectiveness of MOEA-SA and the systematic comparisons with existing methods show that MOEA-SA can get better values of T and E in each graph and find more relevant communities with practical meanings. Knee points corresponding to the best compromise solutions are calculated to guide decision makers to make convenient choices.