Approximating Clustering Coefficient and Transitivity Export

@article{schank2005, abstract = {Since its introduction in the year 1998 by Watts and Strogatz, the clustering-coefficient has become a frequently used tool for analyzing graphs. In 2002 the transitivity was proposed by Newman, Strogatz and Watts as an alternative to the clustering-coefficient. However, as we illustrate by several examples both parameters may differ vastly. On the other hand, an extension of the definitions to weighted versions provides the formal relation between them. As many networks considered in complex systems are huge, the efficient 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 coefficient which also gives very efficient approximation algorithms for the clustering-coefficient and the transitivity. We namely present an algorithm with running time in O(1) for the clustering coefficient, 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. These results also support the assumption that normally the values of clustering-coefficient and transitivity differ considerably.}, author = {Schank, T. and Wagner, D.}, citeulike-article-id = {1274419}, citeulike-linkout-0 = {http://www.ubka.uni-karlsruhe.de/vvv/ira/2004/9/9.pdf}, comment = {* this paper gives insigghts on the evolutive network dynamics model * it contains references to the exact results to compute the \# triangles in a graph}, journal = {Journal of Graph Algorithms and Applications}, keywords = {clustering, coefficient, generative, graphs, models, wattz-sttrogatz}, number = {2}, pages = {265--275}, posted-at = {2007-10-06 06:45:01}, priority = {0}, title = {{Approximating Clustering Coefficient and Transitivity}}, url = {http://www.ubka.uni-karlsruhe.de/vvv/ira/2004/9/9.pdf}, volume = {9}, year = {2005} }

TY - JOUR ID - schank2005 L3 - citeulike-article-id:1274419 N2 - Since its introduction in the year 1998 by Watts and Strogatz, the clustering-coefficient has become a frequently used tool for analyzing graphs. In 2002 the transitivity was proposed by Newman, Strogatz and Watts as an alternative to the clustering-coefficient. However, as we illustrate by several examples both parameters may differ vastly. On the other hand, an extension of the definitions to weighted versions provides the formal relation between them. As many networks considered in complex systems are huge, the efficient 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 coefficient which also gives very efficient approximation algorithms for the clustering-coefficient and the transitivity. We namely present an algorithm with running time in O(1) for the clustering coefficient, 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. These results also support the assumption that normally the values of clustering-coefficient and transitivity differ considerably. IS - 2 JF - Journal of Graph Algorithms and Applications EP - 275 TI - {Approximating Clustering Coefficient and Transitivity} VL - 9 SP - 265 KW - clustering KW - coefficient KW - generative KW - graphs KW - models KW - wattz-sttrogatz N1 - * this paper gives insigghts on the evolutive network dynamics model * it contains references to the exact results to compute the # triangles in a graph AU - Schank, T AU - Wagner, D PY - 2005/// UR - http://www.ubka.uni-karlsruhe.de/vvv/ira/2004/9/9.pdf ER -