A Graph Clustering Algorithm Providing Scalability
Based on the current studies on the algorithms of the affinity propagation and normalized cut, a new scalable graph clustering method called APANC (Affinity Propagation And Normalized Cut) is proposed in this paper. During the APANC process, the authors firstly use the "Affinity Propagation" (AP) to preliminarily group the original data in order to reduce the data-scale, and then they further group the result of AP using "Normalized Cut" (NC) to get the final result. Through such combination, the advantages of AP in time costs and the advantages of NC in accuracy have been adopted. The experimental results show that even though APANC includes two clustering processes, this two-phase algorithm helps to reduce the experiment time compared to NC, and meanwhile, maintain the accuracy.