{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,10]],"date-time":"2023-01-10T05:38:07Z","timestamp":1673329087324},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,4]]},"abstract":"<jats:p>\n            Detecting dominant clusters is important in many analytic applications. The state-of-the-art methods find dense subgraphs on the affinity graph as dominant clusters. However, the time and space complexities of those methods are dominated by the construction of affinity graph, which is quadratic with respect to the number of data points, and thus are impractical on large data sets. To tackle the challenge, in this paper, we apply\n            <jats:italic>Evolutionary Game Theory<\/jats:italic>\n            (EGT) and develop a scalable algorithm, Approximate Localized Infection Immunization Dynamics (ALID). The major idea is to perform Localized Infection Immunization Dynamics (LID) to find dense subgraphs within local ranges of the affinity graph. LID is further scaled up with guaranteed high efficiency and detection quality by an estimated Region of Interest (ROI) and a Candidate Infective Vertex Search method (CIVS). ALID only constructs small local affinity graphs and has time complexity\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>C<\/jats:italic>\n            (\n            <jats:italic>a<\/jats:italic>\n            <jats:sup>*<\/jats:sup>\n            +\n            <jats:italic>\u03b4<\/jats:italic>\n            )\n            <jats:italic>n<\/jats:italic>\n            ) and space complexity\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>a<\/jats:italic>\n            <jats:sup>*<\/jats:sup>\n            (\n            <jats:italic>a<\/jats:italic>\n            <jats:sup>*<\/jats:sup>\n            +\n            <jats:italic>\u03b4<\/jats:italic>\n            )), where\n            <jats:italic>a<\/jats:italic>\n            <jats:sup>*<\/jats:sup>\n            is the size of the largest dominant cluster, and\n            <jats:italic>C<\/jats:italic>\n            \u00ab\n            <jats:italic>n<\/jats:italic>\n            and\n            <jats:italic>\u03b4<\/jats:italic>\n            \u00ab\n            <jats:italic>n<\/jats:italic>\n            are small constants. We demonstrate by extensive experiments on both synthetic data and real world data that ALID achieves the state-of-the-art detection quality with much lower time and space cost on single machine. We also demonstrate the encouraging parallelization performance of ALID by implementing the Parallel ALID (PALID) on\n            <jats:italic>Apache Spark.<\/jats:italic>\n            PALID processes 50 million SIFT data points in 2.29 hours, achieving a speedup ratio of 7.51 with 8 executors.\n          <\/jats:p>","DOI":"10.14778\/2757807.2757808","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"826-837","source":"Crossref","is-referenced-by-count":11,"title":["ALID"],"prefix":"10.14778","volume":"8","author":[{"given":"Lingyang","family":"Chu","sequence":"first","affiliation":[{"name":"Key Lab of Intell. Info. Process., ICT, CAS, Beijing, China"}]},{"given":"Shuhui","family":"Wang","sequence":"additional","affiliation":[{"name":"Key Lab of Intell. Info. Process., ICT, CAS, Beijing, China"}]},{"given":"Siyuan","family":"Liu","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh"}]},{"given":"Qingming","family":"Huang","sequence":"additional","affiliation":[{"name":"University of Chinese Academy of Sciences, Beijing, China"}]},{"given":"Jian","family":"Pei","sequence":"additional","affiliation":[{"name":"Simon Fraser University, Vancouver, Canada"}]}],"member":"320","published-online":{"date-parts":[[2015,4]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"www.psi.toronto.edu\/index.php?q=affinity%20propagation.  www.psi.toronto.edu\/index.php?q=affinity%20propagation."},{"key":"e_1_2_1_2_1","unstructured":"https:\/\/sites.google.com\/site\/lhrbss\/.  https:\/\/sites.google.com\/site\/lhrbss\/."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213930"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/2168651.2168658"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/2180912.2180915"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/944919.944937"},{"key":"e_1_2_1_7_1","first-page":"1571","volume-title":"NIPS","author":"Bul\u00f2 S. R.","year":"2009","unstructured":"S. R. Bul\u00f2 and M. Pelillo . A game-theoretic approach to hypergraph clustering . In NIPS , pages 1571 -- 1579 , 2009 . S. R. Bul\u00f2 and M. Pelillo. A game-theoretic approach to hypergraph clustering. In NIPS, pages 1571--1579, 2009."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.271"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.88"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMM.2013.2270455"},{"key":"e_1_2_1_11_1","volume-title":"ALID: Scalable dominant cluster detection. in arxiv.org","author":"Chu L.","year":"2014","unstructured":"L. Chu , S. Wang , S. Liu , Q. Huang , and J. Pei . ALID: Scalable dominant cluster detection. in arxiv.org , 2014 . L. Chu, S. Wang, S. Liu, Q. Huang, and J. Pei. ALID: Scalable dominant cluster detection. in arxiv.org, 2014."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.1000236"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997857"},{"key":"e_1_2_1_14_1","volume-title":"Mapreduce: Simplified data processing on large clusters. OSDI, page 1","author":"Dean J.","year":"2004","unstructured":"J. Dean and S. Ghemawat . Mapreduce: Simplified data processing on large clusters. OSDI, page 1 , 2004 . J. Dean and S. Ghemawat. Mapreduce: Simplified data processing on large clusters. OSDI, page 1, 2004."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0047-2484(92)90081-J"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.1262185"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1136800"},{"key":"e_1_2_1_18_1","first-page":"631","volume-title":"ICML","author":"Li M.","year":"2010","unstructured":"M. Li and J. T. Kwok . Making large-scale nystrom approximation possible . In ICML , pages 631 -- 638 , 2010 . M. Li and J. T. Kwok. Making large-scale nystrom approximation possible. In ICML, pages 631--638, 2010."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2013.16"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2014.2346173"},{"key":"e_1_2_1_21_1","volume-title":"ICML","author":"Liu H.","year":"2010","unstructured":"H. Liu and S. Yan . Robust graph mode seeking by graph shift . In ICML , 2010 . H. Liu and S. Yan. Robust graph mode seeking by graph shift. In ICML, 2010."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:VISI.0000029664.99615.94"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-053-6"},{"key":"e_1_2_1_25_1","first-page":"849","volume-title":"NIPS","author":"Ng A. Y.","year":"2002","unstructured":"A. Y. Ng , M. I. Jordan , Y. Weiss , On spectral clustering: Analysis and an algorithm . In NIPS , pages 849 -- 856 , 2002 . A. Y. Ng, M. I. Jordan, Y. Weiss, et al. On spectral clustering: Analysis and an algorithm. In NIPS, pages 849--856, 2002."},{"key":"e_1_2_1_26_1","first-page":"84","volume-title":"Neural Networks","author":"Nunes de Casto L.","year":"2000","unstructured":"L. Nunes de Casto and F. J. Von Zuben . An evolutionary immune network for data clustering . In Neural Networks , pages 84 -- 89 . IEEE, 2000 . L. Nunes de Casto and F. J. Von Zuben. An evolutionary immune network for data clustering. In Neural Networks, pages 84--89. IEEE, 2000."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1011139631724"},{"key":"e_1_2_1_28_1","first-page":"1057","volume-title":"NIPS","author":"Pavan M.","year":"2004","unstructured":"M. Pavan and M. Pelillo . Efficient out-of-sample extension of dominant-set clusters . In NIPS , pages 1057 -- 1064 , 2004 . M. Pavan and M. Pelillo. Efficient out-of-sample extension of dominant-set clusters. In NIPS, pages 1057--1064, 2004."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.10"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2010.06.004"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cviu.2010.12.004"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1653771.1653781"},{"key":"e_1_2_1_33_1","volume-title":"NIPS","author":"Shindler M.","year":"2011","unstructured":"M. Shindler , A. Meyerson , and A. Wong . Fast and accurate k-means for large datasets . In NIPS , 2011 . M. Shindler, A. Meyerson, and A. Wong. Fast and accurate k-means for large datasets. In NIPS, 2011."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/946247.946751"},{"key":"e_1_2_1_35_1","volume-title":"VLFeat: An open and portable library of computer vision algorithms","author":"Vedaldi A.","year":"2008","unstructured":"A. Vedaldi and B. Fulkerson . VLFeat: An open and portable library of computer vision algorithms , 2008 . A. Vedaldi and B. Fulkerson. VLFeat: An open and portable library of computer vision algorithms, 2008."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376663"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339737"},{"key":"e_1_2_1_38_1","volume-title":"Evolutionary game theory","author":"Weibull J. W.","year":"1997","unstructured":"J. W. Weibull . Evolutionary game theory . The MIT Press , 1997 . J. W. Weibull. Evolutionary game theory. The MIT Press, 1997."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281280"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2757807.2757808","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:45:51Z","timestamp":1672220751000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2757807.2757808"}},"subtitle":["scalable dominant cluster detection"],"short-title":[],"issued":{"date-parts":[[2015,4]]},"references-count":39,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2015,4]]}},"alternative-id":["10.14778\/2757807.2757808"],"URL":"https:\/\/doi.org\/10.14778\/2757807.2757808","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,4]]}}}