{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,24]],"date-time":"2025-11-24T16:29:58Z","timestamp":1764001798574,"version":"3.38.0"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2011,9,27]],"date-time":"2011-09-27T00:00:00Z","timestamp":1317081600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int J Comput Vis"],"published-print":{"date-parts":[[2012,5]]},"DOI":"10.1007\/s11263-011-0496-1","type":"journal-article","created":{"date-parts":[[2011,9,26]],"date-time":"2011-09-26T20:40:44Z","timestamp":1317069644000},"page":"65-82","source":"Crossref","is-referenced-by-count":34,"title":["Dense Neighborhoods on Affinity Graph"],"prefix":"10.1007","volume":"98","author":[{"given":"Hairong","family":"Liu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xingwei","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Longin Jan","family":"Latecki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shuicheng","family":"Yan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,9,27]]},"reference":[{"issue":"6","key":"496_CR1","doi-asserted-by":"crossref","first-page":"891","DOI":"10.1145\/293347.293348","volume":"45","author":"S. Arya","year":"1998","unstructured":"Arya, S., Mount, D., Netanyahu, N., Silverman, R., & Wu, A. (1998). An optimal algorithm for approximate nearest neighbor searching fixed dimensions. Journal of the ACM, 45(6), 891\u2013923.","journal-title":"Journal of the ACM"},{"issue":"1\u20133","key":"496_CR2","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/S0166-218X(01)00243-8","volume":"121","author":"Y. Asahiro","year":"2002","unstructured":"Asahiro, Y., Hassin, R., & Iwama, K. (2002). Complexity of finding dense subgraphs. Discrete Applied Mathematics, 121(1\u20133), 15\u201326.","journal-title":"Discrete Applied Mathematics"},{"issue":"9","key":"496_CR3","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1145\/361002.361012","volume":"18","author":"J. Bentley","year":"1975","unstructured":"Bentley, J. (1975). Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9), 517\u2013525.","journal-title":"Communications of the ACM"},{"issue":"2","key":"496_CR4","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1023\/A:1020209017701","volume":"24","author":"M. Bomze","year":"2002","unstructured":"Bomze, M., & De Klerk, E. (2002). Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. Journal of Global Optimization, 24(2), 163\u2013185.","journal-title":"Journal of Global Optimization"},{"issue":"10","key":"496_CR5","doi-asserted-by":"crossref","first-page":"1646","DOI":"10.1109\/TPAMI.2006.207","volume":"28","author":"T. Caetano","year":"2006","unstructured":"Caetano, T., Caelli, T., Schuurmans, D., & Barone, D. (2006). Graphical models and point pattern matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(10), 1646\u20131663.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"3","key":"496_CR6","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/PL00009390","volume":"20","author":"T. Chan","year":"1998","unstructured":"Chan, T. (1998). Approximate nearest neighbor queries revisited. Discrete & Computational Geometry, 20(3), 359\u2013373.","journal-title":"Discrete & Computational Geometry"},{"key":"496_CR7","unstructured":"Chang, C.-C., & Lin, C.-J. (2001). LIBSVM: a library for support vector machines."},{"key":"496_CR8","doi-asserted-by":"crossref","unstructured":"Chapelle, O., Scholkopf, B., & Zien, A. (2006a) Semi-supervised learning.","DOI":"10.7551\/mitpress\/9780262033589.001.0001"},{"key":"496_CR9","unstructured":"Chapelle, O., Scholkopf, B., & Zien, A. (2006b). The Benchmark Data Sets. http:\/\/www.kyb.tuebingen.mpg.de\/ssl-book\/benchmarks.html ."},{"issue":"7191","key":"496_CR10","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1038\/nature06830","volume":"453","author":"A. Clauset","year":"2008","unstructured":"Clauset, A., Moore, C., & Newman, M. (2008). Hierarchical structure and the prediction of missing links in networks. Nature, 453(7191), 98\u2013101.","journal-title":"Nature"},{"issue":"4","key":"496_CR11","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1109\/TVCG.2010.9","volume":"16","author":"K. P. M. Connor","year":"2010","unstructured":"Connor, K. P. M. (2010). Fast construction of k-nearest neighbor graphs for point clouds. IEEE Transactions on Visualization and Computer Graphics, 16(4), 599\u2013608.","journal-title":"IEEE Transactions on Visualization and Computer Graphics"},{"issue":"1","key":"496_CR12","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1109\/TIT.1967.1053964","volume":"13","author":"T. Cover","year":"1967","unstructured":"Cover, T., & Hart, P. (1967). Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 13(1), 21\u201327.","journal-title":"IEEE Transactions on Information Theory"},{"key":"496_CR13","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1145\/1390156.1390180","volume-title":"Proceedings of the 25th international conference on machine learning","author":"K. Crammer","year":"2008","unstructured":"Crammer, K., Talukdar, P., & Pereira, F. (2008). A rate-distortion one-class model and its applications to clustering. In Proceedings of the 25th international conference on machine learning (pp. 184\u2013191)."},{"key":"496_CR14","doi-asserted-by":"crossref","first-page":"737","DOI":"10.1007\/978-3-540-44792-4_29","volume-title":"Classic works of the Dempster-Shafer theory of belief functions","author":"T. Denoeux","year":"2008","unstructured":"Denoeux, T. (2008). A k-nearest neighbor classification rule based on Dempster-Shafer theory. In Classic works of the Dempster-Shafer theory of belief functions (pp. 737\u2013760)."},{"key":"496_CR15","first-page":"551","volume-title":"International conference on knowledge discovery and data mining","author":"I. Dhillon","year":"2004","unstructured":"Dhillon, I., Guan, Y., & Kulis, B. (2004). Kernel k-means: spectral clustering and normalized cuts. In International conference on knowledge discovery and data mining (pp.\u00a0551\u2013556)."},{"key":"496_CR16","first-page":"552","volume-title":"ACM special interest group on graphics and interactive techniques","author":"S. Fleishman","year":"2005","unstructured":"Fleishman, S., Cohen-Or, D., & Silva, C. (2005). Robust moving least-squares fitting with sharp features. In ACM special interest group on graphics and interactive techniques (pp. 552\u2013560)."},{"key":"496_CR17","unstructured":"Frank, A., & Asuncion, A. (2010). UCI Machine Learning Repository. http:\/\/archive.ics.uci.edu\/ml"},{"issue":"5814","key":"496_CR18","doi-asserted-by":"crossref","first-page":"972","DOI":"10.1126\/science.1136800","volume":"315","author":"B. Frey","year":"2007","unstructured":"Frey, B., & Dueck, D. (2007). Clustering by passing messages between data points. Science, 315(5814), 972\u2013976.","journal-title":"Science"},{"key":"496_CR19","doi-asserted-by":"crossref","first-page":"674","DOI":"10.1109\/TPAMI.2004.2","volume":"26","author":"B. Georgescu","year":"2004","unstructured":"Georgescu, B., & Meer, P. (2004). Point matching under large image deformations and illumination changes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26, 674\u2013688.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"496_CR20","first-page":"732","volume-title":"Proceedings of the 31st international conference on very large data bases","author":"D. Gibson","year":"2005","unstructured":"Gibson, D., Kumar, R., & Tomkins, A. (2005). Discovering large dense subgraphs in massive graphs. In Proceedings of the 31st international conference on very large data bases (pp. 732\u2013741)."},{"issue":"5","key":"496_CR21","doi-asserted-by":"crossref","first-page":"627","DOI":"10.1109\/TIT.1972.1054888","volume":"18","author":"M. Goldstein","year":"1972","unstructured":"Goldstein, M. (1972). K-nearest neighbor classification. IEEE Transactions on Information Theory, 18(5), 627\u2013630.","journal-title":"IEEE Transactions on Information Theory"},{"key":"496_CR22","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1145\/1102351.1102386","volume-title":"Proceedings of the 22nd international conference on machine learning","author":"G. Gupta","year":"2005","unstructured":"Gupta, G., & Ghosh, J. (2005). Robust one-class clustering using hybrid global and local search. In Proceedings of the 22nd international conference on machine learning (pp. 273\u2013280)."},{"key":"496_CR23","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/3-540-45357-1_9","volume-title":"Advances in knowledge discovery and data mining","author":"E. Han","year":"2001","unstructured":"Han, E., Karypis, G., & Kumar, V. (2001). Text categorization using weight adjusted k-nearest neighbor classification. In Advances in knowledge discovery and data mining (pp. 53\u201365)."},{"key":"496_CR24","first-page":"147","volume-title":"International conference on intelligent systems for molecular biology","author":"P. Horton","year":"1997","unstructured":"Horton, P., & Nakai, K. (1997). Better prediction of protein cellular localization sites with the k nearest neighbors classifier. In International conference on intelligent systems for molecular biology (Vol.\u00a05, pp. 147\u2013152)."},{"key":"496_CR25","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1093\/bioinformatics\/bti1049","volume":"21","author":"H. Hu","year":"2005","unstructured":"Hu, H., Yan, X., Huang, Y., Han, J., & Zhou, X. (2005). Mining coherent dense subgraphs across massive biological networks for functional discovery. Bioinformatics, 21, 213\u2013226.","journal-title":"Bioinformatics"},{"key":"496_CR26","first-page":"604","volume-title":"Proceedings of the 30th annual ACM symposium on theory of computing","author":"P. Indyk","year":"1998","unstructured":"Indyk, P., & Motwani, R. (1998). Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the 30th annual ACM symposium on theory of computing (pp.\u00a0604\u2013613)."},{"key":"496_CR27","first-page":"679","volume-title":"European conference on machine learning","author":"T. Jebara","year":"2006","unstructured":"Jebara, T., & Shchogolev, V. (2006). B-matching for spectral clustering. In European conference on machine learning (pp.\u00a0679\u2013686)."},{"key":"496_CR28","first-page":"441","volume-title":"International conference on machine learning","author":"T. Jebara","year":"2009","unstructured":"Jebara, T., Wang, J., & Chang, S. (2009). Graph construction and b-matching for semi-supervised learning. In International conference on machine learning (pp. 441\u2013448)."},{"key":"496_CR29","first-page":"851","volume-title":"Proceedings of the international conference on very large data bases","author":"M. Kolahdouzan","year":"2004","unstructured":"Kolahdouzan, M., & Shahabi, C. (2004). Voronoi-based k nearest neighbor search for spatial network databases. In Proceedings of the international conference on very large data bases (pp. 851\u2013860)."},{"key":"496_CR30","first-page":"215","volume-title":"Proceedings of the international conference on very large data bases","author":"F. Korn","year":"1996","unstructured":"Korn, F., Sidiropoulos, N., Faloutsos, C., Siegel, E., & Protopapas, Z. (1996). Fast nearest neighbor search in medical image databases. In Proceedings of the international conference on very large data bases (pp. 215\u2013226)."},{"key":"496_CR31","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1525\/9780520411586-036","volume-title":"Proceedings of 2nd Berkeley symposium","author":"W. Kuhn","year":"1951","unstructured":"Kuhn, W., & Tucker, A. (1951). Nonlinear programming. In Proceedings of 2nd Berkeley symposium (pp. 481\u2013492)."},{"key":"496_CR32","first-page":"1482","volume-title":"International conference on computer vision","author":"M. Leordeanu","year":"2005","unstructured":"Leordeanu, M., & Hebert, M. (2005). A spectral technique for correspondence problems using pairwise constraints. In International conference on computer vision (pp.\u00a01482\u20131489)."},{"issue":"12","key":"496_CR33","doi-asserted-by":"crossref","first-page":"1131","DOI":"10.1093\/bioinformatics\/17.12.1131","volume":"17","author":"L. Li","year":"2001","unstructured":"Li, L., Weinberg, C., Darden, T., & Pedersen, L. (2001). Gene selection for sample classification based on gene expression data: study of sensitivity to choice of parameters of the GA\/KNN method. Bioinformatics, 17(12), 1131\u20131139.","journal-title":"Bioinformatics"},{"issue":"2","key":"496_CR34","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1109\/TPAMI.2007.41","volume":"29","author":"H. Ling","year":"2007","unstructured":"Ling, H., & Jacobs, D. (2007). Shape classification using the inner-distance. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(2), 286\u2013299.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"4","key":"496_CR35","doi-asserted-by":"crossref","first-page":"533","DOI":"10.4153\/CJM-1965-053-6","volume":"17","author":"T. Motzkin","year":"1965","unstructured":"Motzkin, T., & Straus, E. (1965). Maxima for graphs and a new proof of a theorem of Tur\u00e1n. Canadian Journal of Mathematics, 17(4), 533\u2013540.","journal-title":"Canadian Journal of Mathematics"},{"key":"496_CR36","first-page":"849","volume-title":"Advances in neural information processing systems","author":"A. Ng","year":"2001","unstructured":"Ng, A., Jordan, M., & Weiss, Y. (2001). On spectral clustering: analysis and an algorithm. In Advances in neural information processing systems (pp.\u00a0849\u2013856)."},{"key":"496_CR37","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1126\/science.278.5337.446","volume":"80","author":"Q. Ouyang","year":"1997","unstructured":"Ouyang, Q., Kaplan, P., Liu, S., & Libchaber, A. (1997). DNA solution of the maximal clique problem. Science, 80, 446\u2013448.","journal-title":"Science"},{"issue":"1","key":"496_CR38","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1109\/TPAMI.2007.250608","volume":"29","author":"M. Pavan","year":"2007","unstructured":"Pavan, M., & Pelillo, M. (2007). Dominant sets and pairwise clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(1), 167\u2013172.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"8","key":"496_CR39","doi-asserted-by":"crossref","first-page":"888","DOI":"10.1109\/34.868688","volume":"22","author":"J. Shi","year":"2000","unstructured":"Shi, J., & Malik, J. (2000). Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), 888\u2013905.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"496_CR40","first-page":"421","volume-title":"Proceedings of the international conference on very large data bases","author":"C. Yu","year":"2001","unstructured":"Yu, C., Ooi, B., Tan, K., & Jagadish, H. (2001). Indexing the distance: An efficient method to kNN processing. In Proceedings of the international conference on very large data bases (pp. 421\u2013430)."},{"key":"496_CR41","first-page":"283","volume-title":"International conference on knowledge discovery and data mining","author":"M. Zaki","year":"1997","unstructured":"Zaki, M., Parthasarathy, S., Ogihara, M., & Li, W. (1997). New algorithms for fast discovery of association rules. In International conference on knowledge discovery and data mining (Vol.\u00a020, pp.\u00a0283\u2013286)."},{"key":"496_CR42","first-page":"595","volume-title":"Advances in neural information processing systems","author":"D. Zhou","year":"2004","unstructured":"Zhou, D., Bousquet, O., Lal, T., Weston, J., & Schlkopf, B. (2004). Learning with local and global consistency. In Advances in neural information processing systems (pp. 595\u2013602)."},{"key":"496_CR43","first-page":"912","volume-title":"International conference on machine learning","author":"X. Zhu","year":"2003","unstructured":"Zhu, X., Ghahramani, Z., & Lafferty, J. (2003). Semi-supervised learning using Gaussian fields and harmonic functions. In International conference on machine learning (Vol.\u00a020, pp. 912\u2013919)."}],"container-title":["International Journal of Computer Vision"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11263-011-0496-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11263-011-0496-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11263-011-0496-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,12]],"date-time":"2025-03-12T02:23:52Z","timestamp":1741746232000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11263-011-0496-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,9,27]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,5]]}},"alternative-id":["496"],"URL":"https:\/\/doi.org\/10.1007\/s11263-011-0496-1","relation":{},"ISSN":["0920-5691","1573-1405"],"issn-type":[{"type":"print","value":"0920-5691"},{"type":"electronic","value":"1573-1405"}],"subject":[],"published":{"date-parts":[[2011,9,27]]}}}