Dynamic Social Network Overlapping Community Detection Study Based On Multi-objective Evolutionary Algorithm

In recent years,the study of dynamic network community detection algorithm gradually receives attention,and made some achievements,but the researches on the dynamic social network is not mature and the existing methods are limited.Therefore,it is particularly important to research dynamic social network.In the social network,the virtual community structure appears diversity characteristics and overlapping community structure is one of the typical representatives.Therefore,we make an investigation to the researches for overlapping community detection problems in dynamic social network,we find that the research on it is very a little,and there is no mature and complete algorithm for overlapping community detection in dynamic social network.So we make the study on the problem of overlapping community detection in dynamic social network,the main research content is as follows:(1)Build the model of the dynamic social network.We constructed the base map of social network topological structure of network according to the connection between the individuals in the social network based on graph theory.Due to the dynamics of social networks,we built a type of dynamic social network model by using a network model framework on discrete time sequence,and present a corresponding mathematical model description.(2)The clustering method of community detection in network.For the community detection in the Snapshot of dynamic social networks at one time step,we have adopted a clustering method based on edge(connections)to obtain the overlapping communities of the networks;For different social network on discrete time sequence,we adopted a smoothness and consistency of evolutionary clustering framework,when clustering for dynamic social network as a whole.We not only could got the dynamic social network community division,but also we could keep the consistency and the smoothness of the change of the network structures of adjacent moment.(3)Establishing the objective functions.Based the overlapping characteristics of overlapping community in dynamic social network and the dynamic characteristics of social network,and the we have used the way of evolution clustering,when we to choose the objective functions,we chose the overlapping community modularity function and Rand index as the objective function,the former as the cost of clustering function,the latter as the cost function of the evolutionary clustering framework.(4)Design the multi-objective optimization algorithm.This paper proposed a multi-objective optimization algorithm for overlapping community detection in dynamic social network based on evolutionary clustering framework and link clustering framework,we called it as DNOCD-LMOGA algorithm.In DNOCD-LMOGA algorithm,we improved and simplified the NSGA-II algorithm.In addition,this paper designed the way of encoding and decoding of solution,the individual selection strategy,crossover and mutation operation,etc.Finally,we run the algorithm that we proposed on real data sets,the experiment results show that the proposed multi-objective evolutionary algorithm can effectively solve the problem of overlapping community detection in dynamic social network.