Geodesic
Approximating Clustering Coefficient and Transitivity
Journal of Graph Algorithms and Applications, Tome 9 (2005) no. 2, pp. 265-275.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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, Watts and Strogatz as an alternative to the clustering coefficient. 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 Ø1 for the clustering coefficient, respectively with running time in Ø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 coefficient. 
@article{JGAA_2005_9_2_a3,
     author = {Thomas Schank and Dorothea Wagner},
     title = {Approximating {Clustering}  {Coefficient} and {Transitivity}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {265--275},
     publisher = {mathdoc},
     volume = {9},
     number = {2},
     year = {2005},
     doi = {10.7155/jgaa.00108},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00108/}
}
TY  - JOUR
AU  - Thomas Schank
AU  - Dorothea Wagner
TI  - Approximating Clustering  Coefficient and Transitivity
JO  - Journal of Graph Algorithms and Applications
PY  - 2005
SP  - 265
EP  - 275
VL  - 9
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00108/
DO  - 10.7155/jgaa.00108
LA  - en
ID  - JGAA_2005_9_2_a3
ER  - 
%0 Journal Article
%A Thomas Schank
%A Dorothea Wagner
%T Approximating Clustering  Coefficient and Transitivity
%J Journal of Graph Algorithms and Applications
%D 2005
%P 265-275
%V 9
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00108/
%R 10.7155/jgaa.00108
%G en
%F JGAA_2005_9_2_a3
Thomas Schank; Dorothea Wagner. Approximating Clustering  Coefficient and Transitivity. Journal of Graph Algorithms and Applications, Tome 9 (2005) no. 2, pp. 265-275. doi : 10.7155/jgaa.00108. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00108/

Cité par Sources :