Research On Community Detection Algorithm Based On Network Structure Change

Nowadays,the problem of community detection in complex networks attracts wide attention of scholars in various fields,and how to detect community structure accurately is the main problem in this field.For the network that the community structure is not obvious,the most of community detection algorithm is difficult to get a satisfactory community division.The reason is that when structure in the network is not obvious,the difference between the number of edge inside the community and the edge between the communities become smaller,and the independence of the community become weaker.In this thesis,we propose a community detection algorithm based on the local community structure and a community detection algorithm based on link prediction.The main research work of this thesis is summarized as follows:(1)Today,the most of the community detection algorithms show higher accuracy when the structure of the complex network is obvious.However,when the community structure is not obvious,the most of the community detection algorithm's performance has dropped sharply.In view of the above problems,this thesis presents a community detection algorithm based on local community detection to add edge and delete edge,and it referred as CSE.The CSE algorithm obtain complete community information by finding local communities in the network and adds or delete some edge among the local communities according to a certain strategy so that the edges within the community increase and the boundaries between the communities decrease.It makes the community structure more obvious than the original community structure of complex network and strengthen the network of community structure to some extent.Experimental results show that the CSE algorithm shows high performance on computer generated data and real network data.(2)As a branch of complex network research,link prediction algorithm is mainly used to predict the existing but undiscovered edges in the network,as well as the possible edges in the future.Link prediction has the characteristics of changing network structure.Since the new edge predicted by the link prediction algorithm is not necessarily within the community,it may be the edge between the communities.Based on this,the community detection algorithm based on link prediction is proposed and called CLPE.CLPE algorithm reduces the range of link prediction according to the central node of the network and proposes a prediction index that fully consider the community characteristics so as to complete the operation of edge addition and operation of edge deletion.Finally,the community expansion is used to get the final community division.Through experimental verification,CLPE algorithm performs better on computer generated data and real data.