Computing Clustering Coefficients in Data Streams

C. Sohler, G. Frahling, A. Marchetti-Spaccamela, S. Leonardi, L. Buriol, in: Proceedings of  the European Conference on Complex Systems (ECCS’06), 2006.

Download
No fulltext has been uploaded.
Conference Paper | English
Author
; ; ; ;
Abstract
We present random sampling algorithms that with probability at least 1 - δ compute a (1 ± ǫ)- approximation of the clustering coefficient, the transitiv ity coefficient, and of the number of bipartite cliques in a graph given as a stream of edges. Our methods can be extended to approximately count the number of occurences of fixed constant-size subgraphs. Our a lgorithms only require one pass over the input stream and their storage space depends only on structural parameters of the graphs, the approxi- mation guarantee, and the confidence probability. For examp le, the algorithms to compute the clustering and transitivity coefficient depend on that coefficient but n ot on the size of the graph. Since many large social networks have small clustering and transitivity coe fficient, our algorithms use space independent of the size of the input for these graphs. We implemented our algorithms and evaluated their performance on networks from different appli- cation domains. The sizes of the considered input graphs varied from about 8, 000 nodes and 40, 000 edges to about 135 million nodes and more than 1 billion edges. For both algorithms we run experiments with a sample set size varying from 100, 000 to 1, 000, 000 to evaluate running time and approximation guarantee. Our algorithms appear to be time efficient for the se sample sizes.
Publishing Year
Proceedings Title
Proceedings of the European Conference on Complex Systems (ECCS'06)
LibreCat-ID

Cite this

Sohler C, Frahling G, Marchetti-Spaccamela A, Leonardi S, Buriol L. Computing Clustering Coefficients in Data Streams. In: Proceedings of  the European Conference on Complex Systems (ECCS’06). ; 2006.
Sohler, C., Frahling, G., Marchetti-Spaccamela, A., Leonardi, S., & Buriol, L. (2006). Computing Clustering Coefficients in Data Streams. In Proceedings of  the European Conference on Complex Systems (ECCS’06).
@inproceedings{Sohler_Frahling_Marchetti-Spaccamela_Leonardi_Buriol_2006, title={Computing Clustering Coefficients in Data Streams}, booktitle={Proceedings of  the European Conference on Complex Systems (ECCS’06)}, author={Sohler, Christian and Frahling, Gereon and Marchetti-Spaccamela, Alberto and Leonardi, Stefano and Buriol, Luciana}, year={2006} }
Sohler, Christian, Gereon Frahling, Alberto Marchetti-Spaccamela, Stefano Leonardi, and Luciana Buriol. “Computing Clustering Coefficients in Data Streams.” In Proceedings of  the European Conference on Complex Systems (ECCS’06), 2006.
C. Sohler, G. Frahling, A. Marchetti-Spaccamela, S. Leonardi, and L. Buriol, “Computing Clustering Coefficients in Data Streams,” in Proceedings of  the European Conference on Complex Systems (ECCS’06), 2006.
Sohler, Christian, et al. “Computing Clustering Coefficients in Data Streams.” Proceedings of  the European Conference on Complex Systems (ECCS’06), 2006.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar