EVA STAR Trefferanzeige

Volltextanzeige Volltext.pdf1.pdf (326 KB)
Titel Approximating clustering-coefficient and transitivity.
Autor Schank, Thomas
Wagner, Dorothea
Institution Fakultät für Informatik (Fak. f. Informatik)
Institut für Logik, Komplexität und Deduktionssysteme (ILKD)
Dokumenttyp Buch
Verlag Karlsruhe
Jahr 2004
Serie Interner Bericht. Fakultät für Informatik, Universität Karlsruhe ; 2004,9
URL für Zitat http://digbib.ubka.uni-karlsruhe.de/volltexte/1000001239
URN für Zitat urn:nbn:de:swb:90-12398
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.