Incremental algorithm based on wedge sampling for estimating clustering coefficient with MapReduce

摘要

Clustering coefficient is widely used in many real-world applications, such as social network analysis and community mining. However, it is expensive to compute clustering coefficient for the large and dynamic networks. To improve the performance of clustering coefficient computing for these dynamic graphs, we propose an incremental algorithm based on random wedge sampling and implement the proposed algorithm upon MapReduce. The proposed algorithm reuses previous result and updates the estimate incrementally, instead of computing the whole dynamic graph from scratch. Experiments on real-world graphs demonstrate that the proposed algorithm is accurate and efficient. Compared with a state-of-the-art MapReduce algorithm, the proposed algorithm runs faster without scarifying accuracy of estimate.