Evolutionary Multi-Objective Optimization Based Community Detection Algorithms For Attributed Networks

Numerous complex systems in the real world can be abstractly expressed as networks,and the research on them has permeated to various fields of disciplines.Networks generally have the characteristics of community structure,finding out the community structure in the networks is beneficial to better understand the structure and function of the network system,to excavate the potential information and hidden rules of the system,and to predict some unknown functions and behaviors.In the real world,there exist a kind of special networks,each node of which has one or multiple attributes,are usually called attribute networks.Discovering the community structure of attribute networks not only depends on the topology of the networks,but also the node attributes that are critical for complementing the topology.In recent years,researchers in many fields have put forward many attribute network community detection algorithms on the basis of different strategies.It is a challenging problem that how to use the topological structure of the network and the node attributes synthetically to detect the communities in the attributed networks so as to nodes are closely related and have more public attributes.Based on this problem,this paper firstly proposes a multi-objective evolutionary community detection algorithm based on node attributes to optimize network structure.Then,further research is conducted to tackle with the performance degradation problem when the networks with noisy attribute information,and a bi-population based multi-objective evolutionary algorithm for balancing topology structure and node attribute information in community detection of attributed networks is proposed.The main research work in this paper is as follows:(1)This paper puts forward a multi-objective evolutionary community detection algorithm based on node attribute information,termed MOEA-AT,to optimize network structure.Specifically,an attribute-correlation network is firstly constructed by using the attribute similarity of nodes.Then,the proposed MOEA-AT selects some edges from attributecorrelation network to join the original topology network on the basis of the framework of evolutionary algorithm,which enhances the connection between the nodes in the community and makes the community structure of the network more obvious.Afterwards,a community adjustment strategy is designed to adjust the local community ownership when topological network changes,thus can quickly obtain the corresponding community division of the next generation networks.The proposed MOEA-AT does not need to set the number of communities artificially in the process of detecting community and simultaneously avoids the problem that the community detection algorithms with linear overlay network topology and node attribute information need to specify the balance parameters.Compared with several excellent community detection algorithms in LFR attribute networks and real attribute networks with different generation parameters,the experimental results show that the MOEA-AT has certain advantages in terms of optimizing network structure,determining community number and detecting community precision compared with other algorithms.(2)By exploiting the node attribute information to optimize the network structure,the MOEA-AT makes comprehensive use of the network topology and node attribute information to a certain extent,which shows high performance and high stability in the networks with no obvious topology.However,when the attribute information is more and more noisy,the performance of the MOEA-AT has declined sharply.In order to tackle with this issue,this paper presents a multi-objective evolutionary community detection algorithm(MOEA-DP)based on the bi-population co-evolution for balancing topology structure and attribute information.In the MOEA-DP,two populations are established,one takes charge of detecting communities according to network topology,whereas the other is responsible for finding communities according to node attributes.These two populations evolve independently by different gene recombination methods,and interact with each other at certain number of generations to utilize the good individuals obtained by the other population.The experimental results show that the superiority of the proposed MOEA-DP for community detection in attributed networks,especially when the community structure is not clear or attribute information is noisy.