---
_id: '18572'
abstract:
- lang: eng
  text: "We present random sampling algorithms that with probability at least 1 − δ
    compute a (1 ±ε)-approximation of the clustering coefficient and of the number
    of bipartite clique subgraphs of a graph given as an incidence stream of edges.
    The space used by our algorithm to estimate the clustering coefficient is inversely
    related to the clustering coefficient of the network itself. The space used by
    our algorithm to compute the number K 3,3 of bipartite cliques is proportional
    to the ratio between the number of K 1,3 and K 3,3 in the graph.\r\n\r\nSince
    the space complexity depends only on the structure of the input graph and not
    on the number of nodes, our algorithms scale very well with increasing graph size.
    Therefore they provide a basic tool to analyze the structure of dense clusters
    in large graphs and have many applications in the discovery of web communities,
    the analysis of the structure of large social networks and the probing of frequent
    patterns in large graphs.\r\n\r\nWe implemented both algorithms and evaluated
    their performance on networks from different application domains and of different
    size; The largest instance is a webgraph consisting of more than 135 million nodes
    and 1 billion edges. Both algorithms compute accurate results in reasonable time
    on the tested instances."
author:
- first_name: Luciana S.
  full_name: Buriol, Luciana S.
  last_name: Buriol
- first_name: Gereon
  full_name: Frahling, Gereon
  last_name: Frahling
- first_name: Stefano
  full_name: Leonardi, Stefano
  last_name: Leonardi
- first_name: Christian
  full_name: Sohler, Christian
  last_name: Sohler
citation:
  ama: 'Buriol LS, Frahling G, Leonardi S, Sohler C. Estimating Clustering Indexes
    in Data Streams. In: <i>Proceedings of the 15th European Symposium on Algorithms
    (ESA)</i>. Vol 4698. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer;
    2007:618-632. doi:<a href="https://doi.org/10.1007/978-3-540-75520-3_55">10.1007/978-3-540-75520-3_55</a>'
  apa: 'Buriol, L. S., Frahling, G., Leonardi, S., &#38; Sohler, C. (2007). Estimating
    Clustering Indexes in Data Streams. In <i>Proceedings of the 15th European Symposium
    on Algorithms (ESA)</i> (Vol. 4698, pp. 618–632). Berlin, Heidelberg: Springer.
    <a href="https://doi.org/10.1007/978-3-540-75520-3_55">https://doi.org/10.1007/978-3-540-75520-3_55</a>'
  bibtex: '@inproceedings{Buriol_Frahling_Leonardi_Sohler_2007, place={Berlin, Heidelberg},
    series={Lecture Notes in Computer Science}, title={Estimating Clustering Indexes
    in Data Streams}, volume={4698}, DOI={<a href="https://doi.org/10.1007/978-3-540-75520-3_55">10.1007/978-3-540-75520-3_55</a>},
    booktitle={Proceedings of the 15th European Symposium on Algorithms (ESA)}, publisher={Springer},
    author={Buriol, Luciana S. and Frahling, Gereon and Leonardi, Stefano and Sohler,
    Christian}, year={2007}, pages={618–632}, collection={Lecture Notes in Computer
    Science} }'
  chicago: 'Buriol, Luciana S., Gereon Frahling, Stefano Leonardi, and Christian Sohler.
    “Estimating Clustering Indexes in Data Streams.” In <i>Proceedings of the 15th
    European Symposium on Algorithms (ESA)</i>, 4698:618–32. Lecture Notes in Computer
    Science. Berlin, Heidelberg: Springer, 2007. <a href="https://doi.org/10.1007/978-3-540-75520-3_55">https://doi.org/10.1007/978-3-540-75520-3_55</a>.'
  ieee: L. S. Buriol, G. Frahling, S. Leonardi, and C. Sohler, “Estimating Clustering
    Indexes in Data Streams,” in <i>Proceedings of the 15th European Symposium on
    Algorithms (ESA)</i>, 2007, vol. 4698, pp. 618–632.
  mla: Buriol, Luciana S., et al. “Estimating Clustering Indexes in Data Streams.”
    <i>Proceedings of the 15th European Symposium on Algorithms (ESA)</i>, vol. 4698,
    Springer, 2007, pp. 618–32, doi:<a href="https://doi.org/10.1007/978-3-540-75520-3_55">10.1007/978-3-540-75520-3_55</a>.
  short: 'L.S. Buriol, G. Frahling, S. Leonardi, C. Sohler, in: Proceedings of the
    15th European Symposium on Algorithms (ESA), Springer, Berlin, Heidelberg, 2007,
    pp. 618–632.'
date_created: 2020-08-28T12:46:05Z
date_updated: 2022-01-06T06:53:40Z
department:
- _id: '63'
doi: 10.1007/978-3-540-75520-3_55
intvolume: '      4698'
language:
- iso: eng
page: 618-632
place: Berlin, Heidelberg
publication: Proceedings of the 15th European Symposium on Algorithms (ESA)
publication_identifier:
  isbn:
  - '9783540755197'
publication_status: published
publisher: Springer
series_title: Lecture Notes in Computer Science
status: public
title: Estimating Clustering Indexes in Data Streams
type: conference
user_id: '15415'
volume: 4698
year: '2007'
...