Research And Application Of Affinity Propagation Algorithm On Non-overlapping Community Detection

Complex social networks can be abstracted as a topology structure with a large number of nodes and edges between nodes, and it is widespread in many fields.Clustering is one of the important means of complex social network research,it is aimed to find the community structure and reflect intrinsic property, to guide real life better. Aming at the low time efficiency and unsupervision of Affinity Propagation Algorithm, we propose the improved algorithm and apply AP Algorithm on incremental community detection.Firstly, we propose a Fast Semi-supervised Community Detection Algorithm Based on Affinity Propagation(FSAP). It bases on the research of AP Algorithm,according to rules of information transmission between the nodes in the factor graph model, to improve the time efficiency by clustering nodes that its similarity value is 0into different classes directly, to be the Fast Affinity Propagation Algorithm(FAP).And it combines with partial pairwise constraints information of Must-link and Cannot-link to adjust similarity matrix, then implementing FAP algorithm. FSAP algorithm not only has the advantage of time efficiency, but also can make full use of prior knowledge to guide the clustering process, and improve the accuracy in community detection, comparing with the original AP algorithm and other algorithms.Secondly, we propose an Incremental Community Detection Algorithm Based on Affinity Propagation(IAP). It bases on the FAP algorithm, according to the characteristics of network’s dynamic changes, the increments are divided into four categories: adding edges, deleting edges, adding nodes and deleting nodes, and presenting the corresponding treatment methods. Because IAP algorithm updates network changes partly, after a period of time, there may be a distortion between algorithm’s results with the real community structure, giving the minimum modularity for testing. IAP algorithm not only can reduce the time complexity effectively, but also can ensure the clustering accuracy comparing with the static AP algorithm to update network structure globally in the dynamic community detection.At last we design and implement a prototype program of Non-overlapping community detection algorithm. The program can realize data loading 、 algorithm selection、results show、and settings, and so on. It can intuitively show the results of community detection So, it plays a good role in the study of community detection.