{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T20:17:32Z","timestamp":1777666652831,"version":"3.51.4"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"1-2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2010,9]]},"abstract":"<jats:p>The identification of clusters, well-connected components in a graph, is useful in many applications from biological function prediction to social community detection. However, finding these clusters can be difficult as graph sizes increase. Most current graph clustering algorithms scale poorly in terms of time or memory. An important insight is that many clustering applications need only the subset of best clusters, and not all clusters in the entire graph. In this paper we propose a new technique, Top Graph Clusters (TopGC), which probabilistically searches large, edge weighted, directed graphs for their best clusters in linear time. The algorithm is inherently parallelizable, and is able to find variable size, overlapping clusters. To increase scalability, a parameter is introduced that controls memory use. When compared with three other state-of-the art clustering techniques, TopGC achieves running time speedups of up to 70% on large scale real world datasets. In addition, the clusters returned by TopGC are consistently found to be better both in calculated score and when compared on real world benchmarks.<\/jats:p>","DOI":"10.14778\/1920841.1920930","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"693-702","source":"Crossref","is-referenced-by-count":37,"title":["Scalable discovery of best clusters on large graphs"],"prefix":"10.14778","volume":"3","author":[{"given":"Kathy","family":"Macropol","sequence":"first","affiliation":[{"name":"University of California, Santa Barbara, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ambuj","family":"Singh","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,9]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"16","volume-title":"IPDPS","author":"Abourjeili A.","year":"2006"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.44"},{"issue":"4","key":"e_1_2_1_3_1","first-page":"297","article-title":"A roadmap of clustering algorithms: finding a match for a biomedical application","volume":"10","author":"Andreopoulos B.","year":"2009","journal-title":"Brief Bioinform"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1038\/75556"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"G. D. Bader and C. W. V. Hogue. An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics 4(2) 2003.  G. D. Bader and C. W. V. Hogue. An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics 4(2) 2003.","DOI":"10.1186\/1471-2105-4-2"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(97)00031-7"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-7-488"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972740.43"},{"key":"e_1_2_1_9_1","unstructured":"J. Dean and S. Ghemawat. MapReduce: Simplified data processing on large clusters. pages 137--150.  J. Dean and S. Ghemawat. MapReduce: Simplified data processing on large clusters. pages 137--150."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.1115"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"e_1_2_1_12_1","first-page":"518","volume-title":"VLDB","author":"Gionis A.","year":"1999"},{"key":"e_1_2_1_13_1","volume-title":"WebDB","author":"Haveliwala T. H.","year":"2000"},{"key":"e_1_2_1_14_1","first-page":"454","volume-title":"SODA '99","author":"Indyk P.","year":"1999"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990313"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1080\/0025570X.1996.11996452"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"I. Lee Z. Li and E. M. Marcotte. An improved bias-reduced probabilistic functional gene network of baker's yeast saccharomyces cerevisiae. PloS one 2(10):e988+ October 2007.  I. Lee Z. Li and E. M. Marcotte. An improved bias-reduced probabilistic functional gene network of baker's yeast saccharomyces cerevisiae. PloS one 2(10):e988+ October 2007.","DOI":"10.1371\/journal.pone.0000988"},{"key":"e_1_2_1_18_1","unstructured":"J. Leskovec. Stanford network analysis package (snap). http:\/\/snap.stanford.edu\/.  J. Leskovec. Stanford network analysis package (snap). http:\/\/snap.stanford.edu\/."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1134707.1134732"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1753326.1753532"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-10-283"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1777879.1777884"},{"issue":"187","key":"e_1_2_1_24_1","first-page":"2006","article-title":"Finding function: evaluation methods for functional genomic data","volume":"7","author":"Myers C. L.","year":"2006","journal-title":"BMC genomics"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557101"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.868688"},{"key":"e_1_2_1_27_1","unstructured":"D. A. Spielman and S.-H. Teng. A local clustering algorithm for massive graphs and its application to nearly-linear time graph partitioning. CoRR abs\/0809.3232 2008.  D. A. Spielman and S.-H. Teng. A local clustering algorithm for massive graphs and its application to nearly-linear time graph partitioning. CoRR abs\/0809.3232 2008."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1553374.1553498"},{"key":"e_1_2_1_29_1","volume-title":"University of Utrecht","author":"van Dongen S.","year":"2000"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/HICSS.2006.272"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1631272.1631320"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447891"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1920841.1920930","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:36:19Z","timestamp":1672227379000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1920841.1920930"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9]]},"references-count":31,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["10.14778\/1920841.1920930"],"URL":"https:\/\/doi.org\/10.14778\/1920841.1920930","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2010,9]]}}}