Research On Community Detection Based On Local Affinity Propagation Algorithm

Community structure is an important topological structure feature of complex networks.With the rapid development of network science,community structure has become the research focus.However,there are still several problems in current community detection algorithm:high time complexity,poor stability and the number of communities should be predetermined.Clustering algorithm is an important method of community detection.Affinity Propagation algorithm considers all data points as potential exemplars,emerges out of the center exemplars through several iterations,and then uses the center exemplars to cluster without a given number of clusters.It has a better stability.In the process of community detection,data sets usually have complex structure,and density of connections between nodes is unevenly distributed.Euclidean distance of traditional AP algorithm shows individual differences in space,but can't reflect the structure information among data completely.Nodes in the same community generally tend to have more connection and greater similarity.Thus,the paper improves the similarity measurement of Affinity Propagation algorithm in view of the community structure feature based on local random walk and local Naive Bayes model.The main research includes:(1)Research on Superposed Random Walk Affinity Propagation(SRWAP)algorithm.Based on the local random walk process,the walk steps are determined by Six Degrees of Separation theory,the similarity among nodes is determined by the Status Probability.Then the paper proposes superposed random walk Affinity Propagation algorithm.The similarity index of the random walk is combined with the direct and indirect adjacent relation in the wandering range.Experiments results verify that the algorithm can reduce the running time and improve the modularity.(2)Research on Local Naive Bayes Affinity Propagation(LNBCNAP)algorithms.In view of different influence in common neighbors,we introduce the role function based on local Naive Bayes model.Then on the basis of adjacency matrix,considering self-similarity and similarity among nodes which has common neighbors but disconnected,the paper proposes Local Naive Bayes Affinity Propagation algorithms.The algorithm considers all possible connection in local area.Experiment proves that the improved algorithm can obtain the results closer to the true partition in the loose data structure.(3)Through simulation experiments on artificial baseline datasets and real network datasets,the results show that SRWAP and LNBCNAP can effectively improve the modularity and normalized mutual information,improve the accuracy of community detection and reduce the running time.Moreover the community detection results are closer to the real network partition.