A Fast Semi-supervised Affinity Propagation Community Detection Algorithm

摘要

Nowadays time efficiencies of most of the community detection algorithms are low, and they cannot make use of prior knowledge effectively, we propose a Fast Semi-supervised Affinity Propagation community detection algorithm (FSAP). First, it has introduced the pairwise constraints, Must-link and Cannot-link, to adjust the similarity matrix; Then, according to rule of information passing between the nodes based on the factor graph model of AP, it directly assigns the two nodes with 0 similarity to different clusters to improve time efficiency. Because social networks are usually large-scale sparse networks, they have lots of pairwise nodes with 0 similarity, so the algorithm can improve the efficiency in community detection. Comparing with other algorithms, the experimental results demonstrate the algorithm has low time cost, and can use prior knowledge to improve the clustering performance effectively.