Comparative Analysis Of Classical Community Detection Algorithms

The rapid development of Internet technology,has promoted the prosperity of various social platforms application.The research on social network,such as finding the characteristics of network structure,is helpful to understand the social network system deeply.Communities have different designations in different backgrounds,such as clusters,associations.Community detection is an important research direction in the field of complex networks data mining,at the same time,it is also a basic task for network analysis.The purpose of community detection is to identify a set of nodes in the network which make the interaction between the nodes in the community stronger than the interaction between the communities.Community detection is not only used to explore the potential cluster structure in the network,but also applied to solve many practical problems in our life.Earlier studies only found the non-overlapping community and considered that a node belonged to one community.As further research,the experts considered a node could belong to multiple communities,and found the overlapping community structure in social networks.Later,the experts focused their eyes on the edges to find the overlapping community structure in social networks.In this thesis,the community discovery algorithm in social networks is studied,and the two aspects of the concrete work in this thesis are as follows:First of all,we introduce the purpose and significance of the research on complex network community structure.At the same time,we also have a brief description of the basic knowledge of complex networks and their representation.In the next place,in the aspect of non-overlapping community detection algorithms,we introduced the ideas of the spectral clustering SC algorithm,GN algorithm,FN algorithm,CNM algorithm,FU algorithm,Infomap algorithm and LPA algorithm.Immediately,in the aspect of overlapping community detection algorithms,we research the basic idea and objective function of CPM algorithm,LFM algorithm,COPRA algorithm,SLPA algorithm and GCE algorithm are studied in detail.Then,we introduce the evaluation index and data set of the community detection algorithm.Finally,according to the idea of these community detection algorithms,those community detection algorithms are implemented and applied them to the network data mining,so as to achieve the purpose of mining network structure.We analyze the objective functions of these algorithms in detail on a large number of real network data and artificial network data.We demonstrate the performance effectiveness and running time of these community detection algorithms to show the rationality and effectiveness of these algorithms.