| Many complex systems formed by interaction and dependence in the real world can be abstracted as complex networks.Community detection in complex networks has become a research hotspot in many interdisciplinary disciplines and industries.Owing to the expansion of the application fields on complex networks,it is difficult for some traditional community detection methods to deal with more high-dimensional and sparse data.The problems of hard division and high cost are emerging.It is important to design better algorithms with higher accuracy and lower computing costs for meeting the updated challenges in complex networks.The popular and meta-heuristic affinity propagation(AP)algorithm automatically obtains a group of representative points(exemplars)and all communities by passing messages between data points,this can accurately divide the networks.However,it is unavailable in dynamic networks and its inflexible parameters may lead to high time,memory consumption and excessive detection in the process of large networks or high-dimensional sparse data.Thus,two novel community detection methods based on affinity propagation are proposed to detect community structures in static and dynamic complex networks respectively.The main contents are as follows:(1)Based on AP algorithm,a novel affinity propagation algorithm in t-distribution(APT)is proposed for community detection in high dimensional complex networks,in which manifold learning is used to reduce network dimensions and create joint probability similarity of low-dimensional space.APT algorithm not only reduces the memory of AP algorithm,improves its detection efficiency,but also makes it applicable to more data types.Thus it can better deal with the community detection in multi-scale data and complete the analysis of large complex networks faster.(2)Improve the accuracy of APT algorithm to detect communities by using modularity optimization.Since manifold learning reduces dimensions,some topological structures will be lost when the network is mapped to a low-dimensional space,resulting in inaccurate detection.This paper takes the modularity as the objective function,and increases the value of modularity by adjusting the dimension reduction and damping factor,so as to improve the detection effect.(3)The AP algorithm is improved in the incremental framework,then a novel incremental affinity propagation algorithm(INAP)is proposed for community detection in dynamic networks.In order to preserve important structural information and save time,INAP adjusts the communities of changed nodes by identifying and processing incremental elements separately,based on historical detection.It then divides the current time-step networks and identifies new communities that are difficult to detect by traditional methods.Based on the simulation experiments on the real-world networks and the LFR-benchmark generated networks,the results verify the feasibility and effectiveness of two algorithms.Compared with other mainstream community detection algorithms in evaluation criteria,APT algorithm can effectively divide more types of static networks with more universality and higher accuracy.In the dynamic networks,INAP algorithm can identify more new communities,correct division and reduce the cumulative error to avoid losing important information.It is also more easily and efficiently to detect the community structures with time stamps. |
