{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,9]],"date-time":"2026-10-09T23:35:41Z","timestamp":1791588941775,"version":"4.3.4"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2010,11]]},"abstract":"<jats:p>\n            This paper introduces a new definition of dense subgraph pattern, the\n            <jats:italic>DN<\/jats:italic>\n            -graph.\n            <jats:italic>DN<\/jats:italic>\n            -graph considers both the size of the substructure and the minimum level of interactions between any pair of the vertices.\n          <\/jats:p>\n          <jats:p>\n            The mining of\n            <jats:italic>DN<\/jats:italic>\n            -graphs inherits the difficulty of finding clique, the fully-connected subgraphs. We thus opt for approximately locating the\n            <jats:italic>DN<\/jats:italic>\n            -graphs using the state-of-the-art graph triangulation methods. Our solution consists of a family of algorithms, each of which targets a different problem setting. These algorithms are iterative, and utilize repeated scans through the triangles in the graph to approximately locate the\n            <jats:italic>DN<\/jats:italic>\n            -graphs. Each scan on the graph triangles improves the results. Since the triangles are not physically materialized, the algorithms have small memory footprint.\n          <\/jats:p>\n          <jats:p>With our solution, the users can adopt a \"pay as you go\" approach. They have the flexibility to terminate the mining process once they are satisfied with the quality of the results. As a result, our algorithms can cope with semi-streaming environment where the graph edges cannot fit into main memory. Results of extensive performance study confirmed our claims.<\/jats:p>","DOI":"10.14778\/1921071.1921073","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"58-68","source":"Crossref","is-referenced-by-count":86,"title":["On triangulation-based dense neighborhood graph discovery"],"prefix":"10.14778","volume":"4","author":[{"given":"Nan","family":"Wang","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jingbo","family":"Zhang","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kian-Lee","family":"Tan","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anthony K. H.","family":"Tung","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2010,11]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Netflix Prize Data Set 2009 (accessed July 23 2009).  Netflix Prize Data Set 2009 (accessed July 23 2009)."},{"key":"e_1_2_1_2_1","first-page":"598","volume-title":"Proc. 5th Latin American Symposium on Theoretical Informatics","author":"Abello J.","year":"2002"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021726221443"},{"issue":"5666","key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"2026","DOI":"10.1126\/science.1092645","article-title":"Structure-based assembly of protein complexes in yeast","volume":"303","author":"Aloy P.","year":"2004","journal-title":"Science"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1145\/1401890.1401898","volume-title":"ACM KDD '08","author":"Becchetti L.","year":"2008"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2005.01.027"},{"key":"e_1_2_1_7_1","first-page":"75","article-title":"Camouflaging independent sets in quasi-random graphs","volume":"26","author":"Brockington M.","year":"1994","journal-title":"DIMACS Series"},{"key":"e_1_2_1_8_1","first-page":"721","volume-title":"VLDB'05","author":"Gibson D.","year":"2005"},{"key":"e_1_2_1_9_1","first-page":"144","volume-title":"PAKDD'98 {Lecture Notes in Artificial Intelligence, 1394","author":"Han J.","year":"1998"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti1049"},{"key":"e_1_2_1_11_1","first-page":"6","article-title":"Proteincprotein interactions essentials: Key concepts to building and analyzing interactome networks","volume":"6","author":"Rivas C. F. J.","year":"2010","journal-title":"PLoS Computational Biology"},{"key":"e_1_2_1_12_1","first-page":"618","article-title":"Reducibility among combinatorial problems","volume":"40","author":"Karp R.","year":"1975","journal-title":"The Journal of Symbolic Logic"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.07.017"},{"key":"e_1_2_1_14_1","first-page":"606","volume-title":"WEA","author":"Schank T.","year":"2005"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1145\/1376616.1376663","volume-title":"SIGMOD'08","author":"Wang N.","year":"2008"},{"issue":"1","key":"e_1_2_1_16_1","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1093\/nar\/30.1.303","article-title":"DIP, the database of interacting proteins: A research tool for studying cellular networks of protein interactions","volume":"30","author":"Xenarios I.","year":"2002","journal-title":"Nucleic Acids Research"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1921071.1921073","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:51:03Z","timestamp":1672221063000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1921071.1921073"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,11]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,11]]}},"alternative-id":["10.14778\/1921071.1921073"],"URL":"https:\/\/doi.org\/10.14778\/1921071.1921073","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2010,11]]}}}