Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00108
Approximating Clustering Coefficient and Transitivity
Vol. 9, no. 2, pp. 265-275, 2005. Concise paper.
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, 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.
|
Journal Supporters
|