{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,5,12]],"date-time":"2023-05-12T21:54:20Z","timestamp":1683928460714},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2019,6]]},"abstract":"<jats:p>Given a database network where each vertex is associated with a transaction database, we are interested in finding theme communities. Here, a theme community is a cohesive subgraph such that a common pattern is frequent in all transaction databases associated with the vertices in the subgraph. Finding all theme communities from a database network enjoys many novel applications. However, it is challenging since even counting the number of all theme communities in a database network is #P-hard. Inspired by the observation that a theme community shrinks when the length of the pattern increases, we investigate several properties of theme communities and develop TCFI, a scalable algorithm that uses these properties to effectively prune the patterns that cannot form any theme community. We also design TC-Tree, a scalable algorithm that decomposes and indexes theme communities efficiently. Retrieving a ranked list of theme communities from a TC-Tree of hundreds of millions of theme communities takes less than 1 second. Extensive experiments and a case study demonstrate the effectiveness and scalability of TCFI and TC-Tree in discovering and querying meaningful theme communities from large database networks.<\/jats:p>","DOI":"10.14778\/3339490.3339492","type":"journal-article","created":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T12:50:07Z","timestamp":1565182207000},"page":"1071-1084","source":"Crossref","is-referenced-by-count":3,"title":["Finding theme communities from database networks"],"prefix":"10.14778","volume":"12","author":[{"given":"Lingyang","family":"Chu","sequence":"first","affiliation":[{"name":"Simon Fraser University, Burnaby, Canada"}]},{"given":"Zhefeng","family":"Wang","sequence":"additional","affiliation":[{"name":"Huawei Technologies, China"}]},{"given":"Jian","family":"Pei","sequence":"additional","affiliation":[{"name":"Simon Fraser University, Burnaby, Canada"}]},{"given":"Yanyan","family":"Zhang","sequence":"additional","affiliation":[{"name":"Simon Fraser University, Burnaby, Canada"}]},{"given":"Yu","family":"Yang","sequence":"additional","affiliation":[{"name":"Simon Fraser University, Burnaby, Canada"}]},{"given":"Enhong","family":"Chen","sequence":"additional","affiliation":[{"name":"Univ. of Science and Tech. of China (Hefei, China)"}]}],"member":"320","published-online":{"date-parts":[[2019,6]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"487","article-title":"Fast algorithms for mining association rules","volume":"1215","author":"Agrawal R.","year":"1994","unstructured":"R. Agrawal and R. Srikant . Fast algorithms for mining association rules . PVLDB , 1215 : 487 -- 499 , 1994 . R. Agrawal and R. Srikant. Fast algorithms for mining association rules. PVLDB, 1215:487--499, 1994.","journal-title":"PVLDB"},{"key":"e_1_2_1_2_1","volume-title":"https:\/\/aminer.org\/citation","author":"AMINER.","year":"2010","unstructured":"AMINER. https:\/\/aminer.org\/citation , 2010 . AMINER. https:\/\/aminer.org\/citation, 2010."},{"key":"e_1_2_1_3_1","volume-title":"Dec.","author":"Assal A. F. A.","year":"2010","unstructured":"A. F. A. Assal , R. M. M. Lim , and M.-H. L. Lee . Multi-user on-line real-time virtual social networks based upon communities of interest for entertainment, information or e-commerce purposes , Dec. 2010 . US Patent 7,853,881. A. F. A. Assal, R. M. M. Lim, and M.-H. L. Lee. Multi-user on-line real-time virtual social networks based upon communities of interest for entertainment, information or e-commerce purposes, Dec. 2010. US Patent 7,853,881."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972818.39"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-013-0331-0"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020579"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/2757807.2757808"},{"key":"e_1_2_1_8_1","volume-title":"Barycentric graph clustering","author":"Cohen J.","year":"2008","unstructured":"J. Cohen . Barycentric graph clustering . Oregon Health Science University , 2008 . J. Cohen. Barycentric graph clustering. Oregon Health Science University, 2008."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2009.120"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM.2012.215"},{"key":"e_1_2_1_12_1","first-page":"175","volume-title":"CORIA","author":"Cruz J. D.","year":"2011","unstructured":"J. D. Cruz , C. Bothorel , and F. Poulet . Semantic clustering of social networks using points of view . In CORIA , pages 175 -- 182 , 2011 . J. D. Cruz, C. Bothorel, and F. Poulet. Semantic clustering of social networks using points of view. In CORIA, pages 175--182, 2011."},{"key":"e_1_2_1_13_1","first-page":"7","volume-title":"International Conference on Digital Society","author":"Dang T.","year":"2012","unstructured":"T. Dang and E. Viennet . Community detection based on structural and attribute similarities . In International Conference on Digital Society , pages 7 -- 12 , 2012 . T. Dang and E. Viennet. Community detection based on structural and attribute similarities. In International Conference on Digital Society, pages 7--12, 2012."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/2034063.2034112"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/777943.777945"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335372"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2013.37"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3099622.3099626"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/WISA.2015.16"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.elerap.2012.12.003"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289199"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1718487.1718519"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-016-0970-8"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972795.51"},{"key":"e_1_2_1_26_1","first-page":"849","volume-title":"Advances in Neural Information Processing Systems","author":"Ng A. Y.","year":"2002","unstructured":"A. Y. Ng , M. I. Jordan , and Y. Weiss . On spectral clustering: Analysis and an algorithm . In Advances in Neural Information Processing Systems , pages 849 -- 856 , 2002 . A. Y. Ng, M. I. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In Advances in Neural Information Processing Systems, pages 849--856, 2002."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.250608"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2012.154"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90028-X"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.868688"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1007\/978-0-387-77672-9_19","volume-title":"Social computing, behavioral modeling, and prediction","author":"Steinhaeuser K.","year":"2008","unstructured":"K. Steinhaeuser and N. V. Chawla . Community detection in a large real-world social network . In Social computing, behavioral modeling, and prediction , pages 168 -- 175 . Springer , 2008 . K. Steinhaeuser and N. V. Chawla. Community detection in a large real-world social network. In Social computing, behavioral modeling, and prediction, pages 168--175. Springer, 2008."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311909"},{"key":"e_1_2_1_34_1","volume-title":"the AAAI Conference on Artificial Intelligence","author":"Wang X.","year":"2016","unstructured":"X. Wang , D. Jin , X. Cao , L. Yang , and W. Zhang . Semantic community identification in large attribute networks . In the AAAI Conference on Artificial Intelligence , 2016 . X. Wang, D. Jin, X. Cao, L. Yang, and W. Zhang. Semantic community identification in large attribute networks. In the AAAI Conference on Artificial Intelligence, 2016."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882913"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-013-0693-z"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2013.167"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687709"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3339490.3339492","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:24:25Z","timestamp":1672223065000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3339490.3339492"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6]]},"references-count":36,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["10.14778\/3339490.3339492"],"URL":"https:\/\/doi.org\/10.14778\/3339490.3339492","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,6]]}}}