Estimating Clustering Indexes in Data Streams
Identifieur interne : 001B74 ( Istex/Corpus ); précédent : 001B73; suivant : 001B75Estimating Clustering Indexes in Data Streams
Auteurs : Luciana S. Buriol ; Gereon Frahling ; Stefano Leonardi ; Christian SohlerSource :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2007.
Abstract
Abstract: 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. Since 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. We 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.
Url:
DOI: 10.1007/978-3-540-75520-3_55
Links to Exploration step
ISTEX:485A339ABBCCE2B9488B249981FEEA298729FE1FLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Estimating Clustering Indexes in Data Streams</title><author><name sortKey="Buriol, Luciana S" sort="Buriol, Luciana S" uniqKey="Buriol L" first="Luciana S." last="Buriol">Luciana S. Buriol</name><affiliation><mods:affiliation>Federal University of Rio Grande do Sul, Porto Alegre, Brazil</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: buriol@inf.ufrgs.br</mods:affiliation></affiliation></author><author><name sortKey="Frahling, Gereon" sort="Frahling, Gereon" uniqKey="Frahling G" first="Gereon" last="Frahling">Gereon Frahling</name><affiliation><mods:affiliation>Google Research, New York, United States</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: gereon@google.com</mods:affiliation></affiliation></author><author><name sortKey="Leonardi, Stefano" sort="Leonardi, Stefano" uniqKey="Leonardi S" first="Stefano" last="Leonardi">Stefano Leonardi</name><affiliation><mods:affiliation>University of Rome “La Sapienza”, Rome, Italy</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: Stefano.Leonardi@dis.uniroma1.it</mods:affiliation></affiliation></author><author><name sortKey="Sohler, Christian" sort="Sohler, Christian" uniqKey="Sohler C" first="Christian" last="Sohler">Christian Sohler</name><affiliation><mods:affiliation>Heinz Nixdorf Institute and University of Paderborn, Paderborn, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: csohler@upb.de</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:485A339ABBCCE2B9488B249981FEEA298729FE1F</idno><date when="2007" year="2007">2007</date><idno type="doi">10.1007/978-3-540-75520-3_55</idno><idno type="url">https://api.istex.fr/document/485A339ABBCCE2B9488B249981FEEA298729FE1F/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001B74</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001B74</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Estimating Clustering Indexes in Data Streams</title><author><name sortKey="Buriol, Luciana S" sort="Buriol, Luciana S" uniqKey="Buriol L" first="Luciana S." last="Buriol">Luciana S. Buriol</name><affiliation><mods:affiliation>Federal University of Rio Grande do Sul, Porto Alegre, Brazil</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: buriol@inf.ufrgs.br</mods:affiliation></affiliation></author><author><name sortKey="Frahling, Gereon" sort="Frahling, Gereon" uniqKey="Frahling G" first="Gereon" last="Frahling">Gereon Frahling</name><affiliation><mods:affiliation>Google Research, New York, United States</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: gereon@google.com</mods:affiliation></affiliation></author><author><name sortKey="Leonardi, Stefano" sort="Leonardi, Stefano" uniqKey="Leonardi S" first="Stefano" last="Leonardi">Stefano Leonardi</name><affiliation><mods:affiliation>University of Rome “La Sapienza”, Rome, Italy</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: Stefano.Leonardi@dis.uniroma1.it</mods:affiliation></affiliation></author><author><name sortKey="Sohler, Christian" sort="Sohler, Christian" uniqKey="Sohler C" first="Christian" last="Sohler">Christian Sohler</name><affiliation><mods:affiliation>Heinz Nixdorf Institute and University of Paderborn, Paderborn, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: csohler@upb.de</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2007</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">485A339ABBCCE2B9488B249981FEEA298729FE1F</idno><idno type="DOI">10.1007/978-3-540-75520-3_55</idno><idno type="ChapterID">55</idno><idno type="ChapterID">Chap55</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: 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. Since 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. We 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.</div></front></TEI><istex><corpusName>springer</corpusName><author><json:item><name>Luciana S. Buriol</name><affiliations><json:string>Federal University of Rio Grande do Sul, Porto Alegre, Brazil</json:string><json:string>E-mail: buriol@inf.ufrgs.br</json:string></affiliations></json:item><json:item><name>Gereon Frahling</name><affiliations><json:string>Google Research, New York, United States</json:string><json:string>E-mail: gereon@google.com</json:string></affiliations></json:item><json:item><name>Stefano Leonardi</name><affiliations><json:string>University of Rome “La Sapienza”, Rome, Italy</json:string><json:string>E-mail: Stefano.Leonardi@dis.uniroma1.it</json:string></affiliations></json:item><json:item><name>Christian Sohler</name><affiliations><json:string>Heinz Nixdorf Institute and University of Paderborn, Paderborn, Germany</json:string><json:string>E-mail: csohler@upb.de</json:string></affiliations></json:item></author><language><json:string>eng</json:string></language><originalGenre><json:string>OriginalPaper</json:string></originalGenre><abstract>Abstract: 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. Since 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. We 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.</abstract><qualityIndicators><score>9.044</score><pdfVersion>1.6</pdfVersion><pdfPageSize>430 x 660 pts</pdfPageSize><refBibsNative>false</refBibsNative><keywordCount>0</keywordCount><abstractCharCount>1301</abstractCharCount><pdfWordCount>6256</pdfWordCount><pdfCharCount>32488</pdfCharCount><pdfPageCount>15</pdfPageCount><abstractWordCount>212</abstractWordCount></qualityIndicators><title>Estimating Clustering Indexes in Data Streams</title><chapterId><json:string>55</json:string><json:string>Chap55</json:string></chapterId><refBibs><json:item><host><author><json:item><name>N Alon</name></json:item><json:item><name>Y Matias</name></json:item><json:item><name>M Szegedy</name></json:item></author><title>The space complexity of approximating the frequency moments</title></host></json:item><json:item><author><json:item><name>L Buriol</name></json:item><json:item><name>G Frahling</name></json:item><json:item><name>S Leonardi</name></json:item><json:item><name>A Marchetti-Spaccamela</name></json:item><json:item><name>C Sohler</name></json:item></author><host><author></author><title>Proceedings of the ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 06</title><publicationDate>2006</publicationDate></host><title>Counting triangles in data streams</title><publicationDate>2006</publicationDate></json:item><json:item><author><json:item><name>L,S Buriol</name></json:item><json:item><name>C Castillo</name></json:item><json:item><name>D Donato</name></json:item><json:item><name>S Leonardi</name></json:item><json:item><name>S Millozzi</name></json:item></author><host><author></author><title>Proceedings of Web Intelligence</title><publicationDate>2006</publicationDate></host><title>Temporal evolution of the wikigraph</title><publicationDate>2006</publicationDate></json:item><json:item><author><json:item><name>D Coppersmith</name></json:item><json:item><name>S Winograd</name></json:item></author><host><volume>3</volume><pages><last>280</last><first>251</first></pages><issue>9</issue><author></author><title>Journal of Symbolic Computation</title><publicationDate>1990</publicationDate></host><title>Matrix multiplication via arith-metic progressions</title><publicationDate>1990</publicationDate></json:item><json:item><author><json:item><name>J Dean</name></json:item><json:item><name>S Ghemawat</name></json:item></author><host><author></author><title>Proceedings of the 6th Symposium on Operating System Design and Implementation</title><publicationDate>2004</publicationDate></host><title>Mapreduce: Simplified data processing on large clusters</title><publicationDate>2004</publicationDate></json:item><json:item><author><json:item><name>S Eubank</name></json:item><json:item><name>V,S A Kumar</name></json:item><json:item><name>M,V Marathe</name></json:item><json:item><name>A Srinivasan</name></json:item><json:item><name>N Wang</name></json:item></author><host><pages><last>727</last><first>718</first></pages><author></author><title>SODA '04: Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms</title><publicationDate>2004</publicationDate></host><title>Structural and algorithmic aspects of massive social networks</title><publicationDate>2004</publicationDate></json:item><json:item><author><json:item><name>C Sohler</name></json:item><json:item><name>G Frahling</name></json:item><json:item><name>P Indyk</name></json:item></author><host><pages><last>149</last><first>142</first></pages><author></author><title>21st Annual Symposium on Computational Geometry</title><publicationDate>2005</publicationDate></host><title>Sampling in dynamic data streams and applications</title><publicationDate>2005</publicationDate></json:item><json:item><host><pages><last>88</last><first>79</first></pages><author><json:item><name>A,C Gilbert</name></json:item><json:item><name>Y Kotidis</name></json:item><json:item><name>S Muthukrishnan</name></json:item><json:item><name>M Strauss</name></json:item></author><title>Surfing wavelets on streams: Onepass summaries for approximate aggregate queries</title><publicationDate>2001</publicationDate></host></json:item><json:item><author><json:item><name>S Guha</name></json:item><json:item><name>N Koudas</name></json:item><json:item><name>K Shim</name></json:item></author><host><pages><last>475</last><first>471</first></pages><author></author><title>ACM Symposium on Theory of Computing</title><publicationDate>2001</publicationDate></host><title>Data-streams and histograms</title><publicationDate>2001</publicationDate></json:item><json:item><host><author><json:item><name>M Henzinger</name></json:item><json:item><name>P Raghavan</name></json:item><json:item><name>S Rajagopalan</name></json:item></author><title>Computing on data streams</title><publicationDate>1998</publicationDate></host></json:item><json:item><author><json:item><name>H Jowhari</name></json:item><json:item><name>M Ghodsi</name></json:item></author><host><pages><last>716</last><first>710</first></pages><author></author><title>COCOON 2005</title><publicationDate>2005</publicationDate></host><title>New streaming algorithms for counting triangles in graphs</title><publicationDate>2005</publicationDate></json:item><json:item><author><json:item><name>R Kumar</name></json:item><json:item><name>P Raghavan</name></json:item><json:item><name>S Rajagopalan</name></json:item><json:item><name>A Tomkins</name></json:item></author><host><pages><last>416</last><first>403</first></pages><author></author><title>Proc. of the 8th WWW Conference</title><publicationDate>1999</publicationDate></host><title>Trawling the web for emerging cyber communities</title><publicationDate>1999</publicationDate></json:item><json:item><host><pages><last>65</last><first>57</first></pages><author><json:item><name>R Kumar</name></json:item><json:item><name>P Raghavan</name></json:item><json:item><name>S Rajagopalan</name></json:item><json:item><name>D Sivakumar</name></json:item><json:item><name>A Tomkins</name></json:item><json:item><name>E Upfal</name></json:item></author><title>Random graph models for the web graph</title><publicationDate>2000</publicationDate></host></json:item><json:item><author><json:item><name>L Laura</name></json:item><json:item><name>S Leonardi</name></json:item><json:item><name>S Millozzi</name></json:item><json:item><name>J,F Sybeyn</name></json:item></author><host><author></author><title>ESA 2002</title><publicationDate>2002</publicationDate></host><title>Algorithms and experiments for the webgraph</title><publicationDate>2002</publicationDate></json:item><json:item><host><author><json:item><name>S Muthukrishnan</name></json:item></author><title>Computing on data streams</title><publicationDate>2005</publicationDate></host></json:item><json:item><author><json:item><name>T Schank</name></json:item><json:item><name>D Wagner</name></json:item></author><host><pages><last>609</last><first>606</first></pages><author></author><title>WEA 2005</title><publicationDate>2005</publicationDate></host><title>Finding, counting and listing all triangles in large graphs, an experimental study</title><publicationDate>2005</publicationDate></json:item><json:item><author><json:item><name>D,J Watts</name></json:item><json:item><name>S,H Strogatz</name></json:item></author><host><volume>393</volume><pages><last>442</last><first>440</first></pages><author></author><title>Nature</title><publicationDate>1998</publicationDate></host><title>Collective dynamics of small-world networks</title><publicationDate>1998</publicationDate></json:item><json:item><author><json:item><name>D Sivakumar</name></json:item><json:item><name>Z Bar-Yosseff</name></json:item><json:item><name>R Kumar</name></json:item></author><host><pages><last>632</last><first>623</first></pages><author></author><title>Proceedings of the thirteenth annual ACM- SIAM symposium on Discrete algorithms</title><publicationDate>2002</publicationDate></host><title>Reductions in streaming algorithms, with an application to counting triangles in graphs</title><publicationDate>2002</publicationDate></json:item></refBibs><genre><json:string>conference</json:string></genre><serie><editor><json:item><name>David Hutchison</name></json:item><json:item><name>Takeo Kanade</name></json:item><json:item><name>Josef Kittler</name></json:item><json:item><name>Jon M. Kleinberg</name></json:item><json:item><name>Friedemann Mattern</name></json:item><json:item><name>John C. Mitchell</name></json:item><json:item><name>Moni Naor</name></json:item><json:item><name>Oscar Nierstrasz</name></json:item><json:item><name>C. Pandu Rangan</name></json:item><json:item><name>Bernhard Steffen</name></json:item><json:item><name>Madhu Sudan</name></json:item><json:item><name>Demetri Terzopoulos</name></json:item><json:item><name>Doug Tygar</name></json:item><json:item><name>Moshe Y. Vardi</name></json:item><json:item><name>Gerhard Weikum</name></json:item></editor><issn><json:string>0302-9743</json:string></issn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Lecture Notes in Computer Science</title><copyrightDate>2007</copyrightDate></serie><host><editor><json:item><name>Lars Arge</name></json:item><json:item><name>Michael Hoffmann</name></json:item><json:item><name>Emo Welzl</name></json:item></editor><subject><json:item><value>Computer Science</value></json:item><json:item><value>Computer Science</value></json:item><json:item><value>Algorithm Analysis and Problem Complexity</value></json:item><json:item><value>Numeric Computing</value></json:item><json:item><value>Discrete Mathematics in Computer Science</value></json:item><json:item><value>Data Structures</value></json:item><json:item><value>Computer Communication Networks</value></json:item><json:item><value>Computer Graphics</value></json:item></subject><isbn><json:string>978-3-540-75519-7</json:string></isbn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Algorithms – ESA 2007</title><bookId><json:string>978-3-540-75520-3</json:string></bookId><volume>4698</volume><pages><last>632</last><first>618</first></pages><issn><json:string>0302-9743</json:string></issn><genre><json:string>book-series</json:string></genre><eisbn><json:string>978-3-540-75520-3</json:string></eisbn><copyrightDate>2007</copyrightDate><doi><json:string>10.1007/978-3-540-75520-3</json:string></doi></host><publicationDate>2007</publicationDate><copyrightDate>2007</copyrightDate><doi><json:string>10.1007/978-3-540-75520-3_55</json:string></doi><id>485A339ABBCCE2B9488B249981FEEA298729FE1F</id><score>0.01927354</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/485A339ABBCCE2B9488B249981FEEA298729FE1F/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/485A339ABBCCE2B9488B249981FEEA298729FE1F/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/485A339ABBCCE2B9488B249981FEEA298729FE1F/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">Estimating Clustering Indexes in Data Streams</title><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><availability><p>Springer-Verlag Berlin Heidelberg, 2007</p></availability><date>2007</date></publicationStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">Estimating Clustering Indexes in Data Streams</title><author xml:id="author-1"><persName><forename type="first">Luciana</forename><surname>Buriol</surname></persName><email>buriol@inf.ufrgs.br</email><affiliation>Federal University of Rio Grande do Sul, Porto Alegre, Brazil</affiliation></author><author xml:id="author-2"><persName><forename type="first">Gereon</forename><surname>Frahling</surname></persName><email>gereon@google.com</email><affiliation>Google Research, New York, United States</affiliation></author><author xml:id="author-3"><persName><forename type="first">Stefano</forename><surname>Leonardi</surname></persName><email>Stefano.Leonardi@dis.uniroma1.it</email><affiliation>University of Rome “La Sapienza”, Rome, Italy</affiliation></author><author xml:id="author-4"><persName><forename type="first">Christian</forename><surname>Sohler</surname></persName><email>csohler@upb.de</email><affiliation>Heinz Nixdorf Institute and University of Paderborn, Paderborn, Germany</affiliation></author></analytic><monogr><title level="m">Algorithms – ESA 2007</title><title level="m" type="sub">15th Annual European Symposium, Eilat, Israel, October 8-10, 2007. Proceedings</title><idno type="pISBN">978-3-540-75519-7</idno><idno type="eISBN">978-3-540-75520-3</idno><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="DOI">10.1007/978-3-540-75520-3</idno><idno type="book-ID">978-3-540-75520-3</idno><idno type="book-title-ID">157051</idno><idno type="book-sequence-number">4698</idno><idno type="book-volume-number">4698</idno><idno type="book-chapter-count">66</idno><editor><persName><forename type="first">Lars</forename><surname>Arge</surname></persName></editor><editor><persName><forename type="first">Michael</forename><surname>Hoffmann</surname></persName></editor><editor><persName><forename type="first">Emo</forename><surname>Welzl</surname></persName></editor><imprint><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><date type="published" when="2007"></date><biblScope unit="volume">4698</biblScope><biblScope unit="page" from="618">618</biblScope><biblScope unit="page" to="632">632</biblScope></imprint></monogr><series><title level="s">Lecture Notes in Computer Science</title><editor><persName><forename type="first">David</forename><surname>Hutchison</surname></persName></editor><editor><persName><forename type="first">Takeo</forename><surname>Kanade</surname></persName></editor><editor><persName><forename type="first">Josef</forename><surname>Kittler</surname></persName></editor><editor><persName><forename type="first">Jon</forename><forename type="first">M.</forename><surname>Kleinberg</surname></persName></editor><editor><persName><forename type="first">Friedemann</forename><surname>Mattern</surname></persName></editor><editor><persName><forename type="first">John</forename><forename type="first">C.</forename><surname>Mitchell</surname></persName></editor><editor><persName><forename type="first">Moni</forename><surname>Naor</surname></persName></editor><editor><persName><forename type="first">Oscar</forename><surname>Nierstrasz</surname></persName></editor><editor><persName><forename type="first">C.</forename><surname>Pandu Rangan</surname></persName></editor><editor><persName><forename type="first">Bernhard</forename><surname>Steffen</surname></persName></editor><editor><persName><forename type="first">Madhu</forename><surname>Sudan</surname></persName></editor><editor><persName><forename type="first">Demetri</forename><surname>Terzopoulos</surname></persName></editor><editor><persName><forename type="first">Doug</forename><surname>Tygar</surname></persName></editor><editor><persName><forename type="first">Moshe</forename><forename type="first">Y.</forename><surname>Vardi</surname></persName></editor><editor><persName><forename type="first">Gerhard</forename><surname>Weikum</surname></persName></editor><biblScope><date>2007</date></biblScope><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="series-Id">558</idno></series><idno type="istex">485A339ABBCCE2B9488B249981FEEA298729FE1F</idno><idno type="DOI">10.1007/978-3-540-75520-3_55</idno><idno type="ChapterID">55</idno><idno type="ChapterID">Chap55</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>2007</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>Abstract: 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. Since 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. We 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.</p></abstract><textClass><keywords scheme="Book-Subject-Collection"><list><label>SUCO11645</label><item><term>Computer Science</term></item></list></keywords></textClass><textClass><keywords scheme="Book-Subject-Group"><list><label>I</label><label>I16021</label><label>I1701X</label><label>I17028</label><label>I15017</label><label>I13022</label><label>I22013</label><item><term>Computer Science</term></item><item><term>Algorithm Analysis and Problem Complexity</term></item><item><term>Numeric Computing</term></item><item><term>Discrete Mathematics in Computer Science</term></item><item><term>Data Structures</term></item><item><term>Computer Communication Networks</term></item><item><term>Computer Graphics</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="2007">Published</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2016-11-23">References added</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2017-01-21">References added</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/document/485A339ABBCCE2B9488B249981FEEA298729FE1F/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Springer, Publisher found" wicri:toSee="no header"><istex:xmlDeclaration>version="1.0" encoding="UTF-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//Springer-Verlag//DTD A++ V2.4//EN" URI="http://devel.springer.de/A++/V2.4/DTD/A++V2.4.dtd" name="istex:docType"></istex:docType><istex:document><Publisher><PublisherInfo><PublisherName>Springer Berlin Heidelberg</PublisherName><PublisherLocation>Berlin, Heidelberg</PublisherLocation></PublisherInfo><Series><SeriesInfo SeriesType="Series" TocLevels="0"><SeriesID>558</SeriesID><SeriesPrintISSN>0302-9743</SeriesPrintISSN><SeriesElectronicISSN>1611-3349</SeriesElectronicISSN><SeriesTitle Language="En">Lecture Notes in Computer Science</SeriesTitle></SeriesInfo><SeriesHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>David</GivenName><FamilyName>Hutchison</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Takeo</GivenName><FamilyName>Kanade</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Josef</GivenName><FamilyName>Kittler</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Jon</GivenName><GivenName>M.</GivenName><FamilyName>Kleinberg</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Friedemann</GivenName><FamilyName>Mattern</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>John</GivenName><GivenName>C.</GivenName><FamilyName>Mitchell</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Moni</GivenName><FamilyName>Naor</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Oscar</GivenName><FamilyName>Nierstrasz</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>C.</GivenName><FamilyName>Pandu Rangan</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Bernhard</GivenName><FamilyName>Steffen</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Madhu</GivenName><FamilyName>Sudan</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Demetri</GivenName><FamilyName>Terzopoulos</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Doug</GivenName><FamilyName>Tygar</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Moshe</GivenName><GivenName>Y.</GivenName><FamilyName>Vardi</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Gerhard</GivenName><FamilyName>Weikum</FamilyName></EditorName></Editor></EditorGroup></SeriesHeader><Book Language="En"><BookInfo BookProductType="Proceedings" ContainsESM="No" Language="En" MediaType="eBook" NumberingStyle="Unnumbered" OutputMedium="All" TocLevels="0"><BookID>978-3-540-75520-3</BookID><BookTitle>Algorithms – ESA 2007</BookTitle><BookSubTitle>15th Annual European Symposium, Eilat, Israel, October 8-10, 2007. Proceedings</BookSubTitle><BookVolumeNumber>4698</BookVolumeNumber><BookSequenceNumber>4698</BookSequenceNumber><BookDOI>10.1007/978-3-540-75520-3</BookDOI><BookTitleID>157051</BookTitleID><BookPrintISBN>978-3-540-75519-7</BookPrintISBN><BookElectronicISBN>978-3-540-75520-3</BookElectronicISBN><BookChapterCount>66</BookChapterCount><BookCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2007</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I16021" Priority="1" Type="Secondary">Algorithm Analysis and Problem Complexity</BookSubject><BookSubject Code="I1701X" Priority="2" Type="Secondary">Numeric Computing</BookSubject><BookSubject Code="I17028" Priority="3" Type="Secondary">Discrete Mathematics in Computer Science</BookSubject><BookSubject Code="I15017" Priority="4" Type="Secondary">Data Structures</BookSubject><BookSubject Code="I13022" Priority="5" Type="Secondary">Computer Communication Networks</BookSubject><BookSubject Code="I22013" Priority="6" Type="Secondary">Computer Graphics</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup></BookInfo><BookHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>Lars</GivenName><FamilyName>Arge</FamilyName></EditorName><Contact><Email>large@daimi.au.dk</Email></Contact></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Michael</GivenName><FamilyName>Hoffmann</FamilyName></EditorName><Contact><Email>mh55@mcs.le.ac.uk</Email></Contact></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Emo</GivenName><FamilyName>Welzl</FamilyName></EditorName><Contact><Email>welzl@inf.ethz.ch</Email></Contact></Editor></EditorGroup></BookHeader><Part ID="Part3"><PartInfo TocLevels="0"><PartID>3</PartID><PartSequenceNumber>3</PartSequenceNumber><PartTitle>Contributed Papers: Engineering and Applications Track</PartTitle><PartChapterCount>13</PartChapterCount><PartContext><SeriesID>558</SeriesID><BookTitle>Algorithms – ESA 2007</BookTitle></PartContext></PartInfo><Chapter ID="Chap55" Language="En"><ChapterInfo ChapterType="OriginalPaper" ContainsESM="No" NumberingStyle="Unnumbered" TocLevels="0"><ChapterID>55</ChapterID><ChapterDOI>10.1007/978-3-540-75520-3_55</ChapterDOI><ChapterSequenceNumber>55</ChapterSequenceNumber><ChapterTitle Language="En">Estimating Clustering Indexes in Data Streams</ChapterTitle><ChapterFirstPage>618</ChapterFirstPage><ChapterLastPage>632</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2007</CopyrightYear></ChapterCopyright><ChapterGrants Type="Regular"><MetadataGrant Grant="OpenAccess"></MetadataGrant><AbstractGrant Grant="OpenAccess"></AbstractGrant><BodyPDFGrant Grant="Restricted"></BodyPDFGrant><BodyHTMLGrant Grant="Restricted"></BodyHTMLGrant><BibliographyGrant Grant="Restricted"></BibliographyGrant><ESMGrant Grant="Restricted"></ESMGrant></ChapterGrants><ChapterContext><SeriesID>558</SeriesID><PartID>3</PartID><BookID>978-3-540-75520-3</BookID><BookTitle>Algorithms – ESA 2007</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff1"><AuthorName DisplayOrder="Western"><GivenName>Luciana</GivenName><GivenName>S.</GivenName><FamilyName>Buriol</FamilyName></AuthorName><Contact><Email>buriol@inf.ufrgs.br</Email></Contact></Author><Author AffiliationIDS="Aff2"><AuthorName DisplayOrder="Western"><GivenName>Gereon</GivenName><FamilyName>Frahling</FamilyName></AuthorName><Contact><Email>gereon@google.com</Email></Contact></Author><Author AffiliationIDS="Aff3"><AuthorName DisplayOrder="Western"><GivenName>Stefano</GivenName><FamilyName>Leonardi</FamilyName></AuthorName><Contact><Email>Stefano.Leonardi@dis.uniroma1.it</Email></Contact></Author><Author AffiliationIDS="Aff4"><AuthorName DisplayOrder="Western"><GivenName>Christian</GivenName><FamilyName>Sohler</FamilyName></AuthorName><Contact><Email>csohler@upb.de</Email></Contact></Author><Affiliation ID="Aff1"><OrgName>Federal University of Rio Grande do Sul, Porto Alegre</OrgName><OrgAddress><Country>Brazil</Country></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgName>Google Research, New York</OrgName><OrgAddress><Country>United States</Country></OrgAddress></Affiliation><Affiliation ID="Aff3"><OrgName>University of Rome “La Sapienza”, Rome</OrgName><OrgAddress><Country>Italy</Country></OrgAddress></Affiliation><Affiliation ID="Aff4"><OrgName>Heinz Nixdorf Institute and University of Paderborn, Paderborn</OrgName><OrgAddress><Country>Germany</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>We present random sampling algorithms that with probability at least 1 − <Emphasis Type="Italic">δ</Emphasis> compute a (1 ±<Emphasis Type="Italic">ε</Emphasis>)-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 <Emphasis Type="Italic">K</Emphasis><Subscript>3,3</Subscript> of bipartite cliques is proportional to the ratio between the number of <Emphasis Type="Italic">K</Emphasis><Subscript>1,3</Subscript> and <Emphasis Type="Italic">K</Emphasis><Subscript>3,3</Subscript> in the graph.</Para><Para>Since 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.</Para><Para>We 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.</Para></Abstract><ArticleNote Type="Misc"><SimplePara>This work was partially supported by the EU within the 6th Framework Programme under contract 001907 “Dynamically Evolving, Large Scale Information Systems” (DELIS) and DFG project So 514/1-1.</SimplePara></ArticleNote></ChapterHeader><NoBody></NoBody></Chapter></Part></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>Estimating Clustering Indexes in Data Streams</title></titleInfo><titleInfo type="alternative" contentType="CDATA" lang="en"><title>Estimating Clustering Indexes in Data Streams</title></titleInfo><name type="personal"><namePart type="given">Luciana</namePart><namePart type="given">S.</namePart><namePart type="family">Buriol</namePart><affiliation>Federal University of Rio Grande do Sul, Porto Alegre, Brazil</affiliation><affiliation>E-mail: buriol@inf.ufrgs.br</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Gereon</namePart><namePart type="family">Frahling</namePart><affiliation>Google Research, New York, United States</affiliation><affiliation>E-mail: gereon@google.com</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Stefano</namePart><namePart type="family">Leonardi</namePart><affiliation>University of Rome “La Sapienza”, Rome, Italy</affiliation><affiliation>E-mail: Stefano.Leonardi@dis.uniroma1.it</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Christian</namePart><namePart type="family">Sohler</namePart><affiliation>Heinz Nixdorf Institute and University of Paderborn, Paderborn, Germany</affiliation><affiliation>E-mail: csohler@upb.de</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="conference" displayLabel="OriginalPaper"></genre><originInfo><publisher>Springer Berlin Heidelberg</publisher><place><placeTerm type="text">Berlin, Heidelberg</placeTerm></place><dateIssued encoding="w3cdtf">2007</dateIssued><copyrightDate encoding="w3cdtf">2007</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType></physicalDescription><abstract lang="en">Abstract: 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. Since 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. We 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.</abstract><relatedItem type="host"><titleInfo><title>Algorithms – ESA 2007</title><subTitle>15th Annual European Symposium, Eilat, Israel, October 8-10, 2007. Proceedings</subTitle></titleInfo><name type="personal"><namePart type="given">Lars</namePart><namePart type="family">Arge</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Michael</namePart><namePart type="family">Hoffmann</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Emo</namePart><namePart type="family">Welzl</namePart><role><roleTerm type="text">editor</roleTerm></role></name><genre type="book-series" displayLabel="Proceedings"></genre><originInfo><copyrightDate encoding="w3cdtf">2007</copyrightDate><issuance>monographic</issuance></originInfo><subject><genre>Book-Subject-Collection</genre><topic authority="SpringerSubjectCodes" authorityURI="SUCO11645">Computer Science</topic></subject><subject><genre>Book-Subject-Group</genre><topic authority="SpringerSubjectCodes" authorityURI="I">Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I16021">Algorithm Analysis and Problem Complexity</topic><topic authority="SpringerSubjectCodes" authorityURI="I1701X">Numeric Computing</topic><topic authority="SpringerSubjectCodes" authorityURI="I17028">Discrete Mathematics in Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I15017">Data Structures</topic><topic authority="SpringerSubjectCodes" authorityURI="I13022">Computer Communication Networks</topic><topic authority="SpringerSubjectCodes" authorityURI="I22013">Computer Graphics</topic></subject><identifier type="DOI">10.1007/978-3-540-75520-3</identifier><identifier type="ISBN">978-3-540-75519-7</identifier><identifier type="eISBN">978-3-540-75520-3</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="BookTitleID">157051</identifier><identifier type="BookID">978-3-540-75520-3</identifier><identifier type="BookChapterCount">66</identifier><identifier type="BookVolumeNumber">4698</identifier><identifier type="BookSequenceNumber">4698</identifier><identifier type="PartChapterCount">13</identifier><part><date>2007</date><detail type="part"><title>Contributed Papers: Engineering and Applications Track</title></detail><detail type="volume"><number>4698</number><caption>vol.</caption></detail><extent unit="pages"><start>618</start><end>632</end></extent></part><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2007</recordOrigin></recordInfo></relatedItem><relatedItem type="series"><titleInfo><title>Lecture Notes in Computer Science</title></titleInfo><name type="personal"><namePart type="given">David</namePart><namePart type="family">Hutchison</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Takeo</namePart><namePart type="family">Kanade</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Josef</namePart><namePart type="family">Kittler</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jon</namePart><namePart type="given">M.</namePart><namePart type="family">Kleinberg</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Friedemann</namePart><namePart type="family">Mattern</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">John</namePart><namePart type="given">C.</namePart><namePart type="family">Mitchell</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Moni</namePart><namePart type="family">Naor</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Oscar</namePart><namePart type="family">Nierstrasz</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">C.</namePart><namePart type="family">Pandu Rangan</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Bernhard</namePart><namePart type="family">Steffen</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Madhu</namePart><namePart type="family">Sudan</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Demetri</namePart><namePart type="family">Terzopoulos</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Doug</namePart><namePart type="family">Tygar</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Moshe</namePart><namePart type="given">Y.</namePart><namePart type="family">Vardi</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Gerhard</namePart><namePart type="family">Weikum</namePart><role><roleTerm type="text">editor</roleTerm></role></name><originInfo><copyrightDate encoding="w3cdtf">2007</copyrightDate><issuance>serial</issuance></originInfo><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="SeriesID">558</identifier><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2007</recordOrigin></recordInfo></relatedItem><identifier type="istex">485A339ABBCCE2B9488B249981FEEA298729FE1F</identifier><identifier type="DOI">10.1007/978-3-540-75520-3_55</identifier><identifier type="ChapterID">55</identifier><identifier type="ChapterID">Chap55</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag Berlin Heidelberg, 2007</accessCondition><recordInfo><recordContentSource>SPRINGER</recordContentSource><recordOrigin>Springer-Verlag Berlin Heidelberg, 2007</recordOrigin></recordInfo></mods></metadata></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001B74 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001B74 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:485A339ABBCCE2B9488B249981FEEA298729FE1F
|texte= Estimating Clustering Indexes in Data Streams
}}
| This area was generated with Dilib version V0.6.31. |  |