Community Detection In Attributed Networks Based On Evolutionary Algorithms And Its Applications

In recent years,the complex network has attracted lots of attention in academia.Network can be modeled as graph,while nodes represent objects,and edges represent the interactions between the objects.Community structure is an important attribute of the complex network,which illustrates that the network can be divided into a number of communities,and nodes inside communities are densely connected,while nodes beside communities are sparely connected.Community detection is the discovery of community structure hidden in the network,which has great significance in understanding the function of the network,exploring the hidden information of the network and tracking network behavior.A lot of effective algorithms have been proposed for community detection.However,these algorithms only consider the topology of some common networks for community detection.While real networks usually have abundant information,in attribute networks,users have attribute information,such as age,gender,university and hobbies.In addition,the communities are often overlapping in real network.On one hand,this thesis designs a community detection algorithm based on multi-agent system,on the other hand,attribute network clustering and overlapping community were intensively studied.The main work is summarized as follows:First,we study community detection based on multi-agent genetic system.As the traditional genetic algorithms select parents from the whole population to produce the offspring,while in the practical process of natural selection,the interactions between individuals often occur in a certain local environment.In this thesis,a multi-agent genetic algorithm variant,named as MAGA-Net,is proposed to optimize modularity value in community detection.A series of operators are designed,namely split and merge based neighborhood competition operator,hybrid neighborhood crossover,adaptive mutation and self-learning operator,to increase modularity value.In the experiments,the performance of MAGA-Net is validated on both well-known real-world networks and large-scale synthetic LFR networks with 5000 nodes.The systematic comparisons with existing algorithms show that MAGA-Net outperforms the others.Next,a multi-objective evolutionary algorithm based on structural and attribute similarities,named as MOEA-SA,is proposed to solve the attributed graph clustering problems in this thesis.In many real-world graphs,except for topological structure,each node usually has one or more attributes describing its properties which are often homogeneous in a community.So when content information is available,it is possible to detect more relevant and practical communities,inside which the nodes are not only densely connected but also share common attributes.In MOEA-SA,A new objective attribute similarity S_A is proposed and another objective modularity Q is employed.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 towards good direction.The performance of MOEA-SA is validated on several real Facebook attributed graphs and several ego-networks with multi-attribute.Two measurements density T and entropy E are used to evaluate the quality of obtained communities.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.Finally,we study community detection in ego networks with multi-attributes.In recent years,with the rapid development of social network,such as Facebook,Twitter,Wechat and Google+,community discovery methods are urgently needed.However,social network always with hundreds of millions,while Ego-network consists of a set of nodes which are directly connected to the ego.Ego network is always small,practical,with property and overlapping.Therefore,a multi-objective evolutionary algorithms for overlapping community detection in ego networks,named as _OMOEA/D-SA is designed.Permutation encoding and local structural and attribute based decoding method are also designed.