Research On Overlapping Community Detection And Its Evolutionary Algorithms In Social Networks

Social software has gradually become an essential part in people's life as it is well accepted by the public such as We Chat,Tik Tok Weibo and QQ.The technology of the overlapping community detection technology and its evolution,one of the most important technologies in complex network analysis,plays a pivotal role in controlling complex network,understanding network function,predicting individual behaviors in network and other aspects.This thesis mainly studies overlapping community detection,community evolution algorithm and issues related to both.Analyses indicate that there exist following problems about detection and evolution algorithm of communities.First,the initial position of the seed node has an important influence on the final result of the overlapping community partition algorithm.Second,most of the current evaluation methods of community evolution are based on the similarity strategy to judge the global network.However,the accuracy of evolutionary events cannot be guaranteed without the consideration of the network topology.Based on the research of the overlapping community detection,this thesis further studies the evaluation methods of overlapping community evolution in social networks.The main work of this thesis is as follows:Firstly,aiming at the influence of seed nodes on the results of overlapping community division,this thesis proposes an overlapping community detection algorithm based on node importance expansion.Firstly,the initial seed node is selected based on the node importance formula improved by clustering coefficient,and the initial seed community is selected at random;secondly,based on the idea of local expansion,communities represented by other notes are identified and selected combined with the similarity and fitness between nodes and communities;finally,the selected communities' division results will be overall optimized by the similarity formula between communities.Through comparative experiments,it is shown that the algorithm of this thesis has higher quality in dividing overlapping communities,and the divided community structure is more reasonable.Secondly,aiming at the evaluation issue of community evolution in adjacent time windows found in dynamic network research,this thesis proposes a concept of core node gravity chain based on the idea of gravitation,and introduces this concept into theevaluation criteria of community evolution.This method combines stability and diversity to evaluate whether there is an evolutionary relationship between communities in adjacent time slices.Besides,this method emphasizes the influences of core node gravity chain on global community evolution and it is more suitable for real social network evolution detection.the effectiveness of the algorithm is verified on DBLP and Enron data sets.Through comparative experiments,it is shown that the event-based overlapping community evolution algorithm proposed in this thesis has good community evolution detection capabilities.Thirdly,through the analysis and summary of the aforementioned research work,this thesis designs and implements a prototype system of social network overlapping community detection and evolution algorithm.This system includes functional modules,such as data input,overlapping community detection and community evolution evaluation,all of which are also tested.