Research On Community Detection Algorithms In Social Network

With the development of the Internet,the relationship between people and people is becoming more and more closely,and the network is also more complex.It is difficult to study the social network on the whole.However,the community structure,an important attribute of the social network,can help us understand the topology and hierarchical structure of the network,forecast the trend of the network and find the characteristics hidden in the network.The community structure of the social network involves many disciplines and has a good application prospect in many fields,which has caused the wide attention of scholars both at home and abroad.In recent years,there have been many classic community detection algorithms.But the time complexity is still to be reduced,and the accuracy and stability are still to be improved.This thesis takes the non overlapping community of the undirected and unweighted network as the research object.In order to improve the accuracy,reduce time complexity and increase the stability of the algorithm,we analyse the classic community detection algorithms and propose two improved algorithms based on the clustering algorithm and label propagation algorithm.One is a community detection algorithm based on node similarity,named as NSCDA.The other is a community detection algorithm based on label weight coefficient,named as LWC.On the basis of K-Means algorithm,the NSCDA changes the way of choosing initial k nodes,the new way chooses k nodes whose node degree is larger than the average node degree and the similarity between each other is lower.The NSCDA replaces the Euclidean distance with the node similarity.Each node is classified into the community which has the maximum average similarity with the node so as to get the final community structure.The theoretical analysis and experimental results on both the synthetic networks and the real social networks demonstrate that NSCDA is feasible,and it has higher accuracy and time efficiency compared with other classical algorithms.In order to solve the problem of poor stability and low accuracy of the label propagation algorithm,LWC algorithm updates node label in the descending order of node's degree,introduces the concept of label weight coefficient so as to choose label correctly according to the local similarity and degree of neigbor node,and introduces the concept of label connection degree in order to avoid random selection when there is more than one candidate label which meets the conditions.The experimental results on both the synthetic networks and the real social networks demonstrate that LWC algorithm has high accuracy and good stability.In summary,this thesis has certain value both on theory and practice.The algorithms designed in this thesis can not only improve the accuracy and efficiency,but also increase stability.They can be used in the real social network scene.