Approximating Clustering Coefficient and Transitivity

Since its introduction in the year 1998 by Watts and Strogatz, the clustering coecient has become a frequently used tool for analyzing graphs. In 2002 the transitivity was proposed by Newman, Watts and Strogatz as an alternative to the clustering coecient. As many networks considered in complex systems are huge, the ecient computation of such network parameters is crucial. Several algorithms with polynomial running time can be derived from results known in graph theory. The main contribution of this work is a new fast approximation algorithm for the weighted clustering coecient which also gives very ecient approximation algorithms for the clustering coecient and the transitivity. We namely present an algorithm with running time in O(1) for the clustering coecient, respectively with running time in O(n) for the transitivity. By an experimental study we demonstrate the performance of the proposed algorithms on real-world data as well as on generated graphs. Moreover we give a simple graph generator algorithm that works according to the preferential attachment rule but also generates graphs with adjustable clustering coecient.