{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T14:43:04Z","timestamp":1767969784874,"version":"3.49.0"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2019,9,24]],"date-time":"2019-09-24T00:00:00Z","timestamp":1569283200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61772219, 61702473, 61572221, U1836204"],"award-info":[{"award-number":["61772219, 61702473, 61572221, U1836204"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2019,10,31]]},"abstract":"<jats:p>\n            Community detection is an important information mining task to uncover modular structures in large networks. For increasingly common large network datasets, global community detection is prohibitively expensive, and attention has shifted to methods that mine local communities,\u00a0 i.e.,\u00a0identifying all latent members of a particular community from a few labeled seed members. To address such semi-supervised mining task, we systematically develop a local spectral (LOSP) subspace-based community detection method, called LOSP. We define a family of LOSP subspaces based on Krylov subspaces, and seek a sparse indicator for the target community via an \u2113\n            <jats:sub>1<\/jats:sub>\n            norm minimization over the Krylov subspace. Variants of LOSP depend on type of random walks with different diffusion speeds, type of random walks, dimension of the LOSP subspace, and step of diffusions. The effectiveness of the proposed LOSP approach is theoretically analyzed based on Rayleigh quotients, and it is experimentally verified on a wide variety of real-world networks across social, production, and biological domains, as well as on an extensive set of synthetic LFR benchmark datasets.\n          <\/jats:p>","DOI":"10.1145\/3340708","type":"journal-article","created":{"date-parts":[[2019,9,25]],"date-time":"2019-09-25T12:57:52Z","timestamp":1569416272000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":34,"title":["Krylov Subspace Approximation for Local Community Detection in Large Networks"],"prefix":"10.1145","volume":"13","author":[{"given":"Kun","family":"He","sequence":"first","affiliation":[{"name":"Huazhong University of Science and Technology, Wuhan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pan","family":"Shi","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology, Wuhan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Bindel","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John E.","family":"Hopcroft","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,9,24]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/3122009.3242034"},{"key":"e_1_2_1_2_1","volume-title":"A separability framework for analyzing community structure. ACM Transactions on Knowledge Discovery from Data 8, 1","author":"Abrahao Bruno","year":"2014","unstructured":"Bruno Abrahao , Sucheta Soundarajan , John E. Hopcroft , and Robert Kleinberg . 2014. A separability framework for analyzing community structure. ACM Transactions on Knowledge Discovery from Data 8, 1 ( 2014 ), 5. Bruno Abrahao, Sucheta Soundarajan, John E. Hopcroft, and Robert Kleinberg. 2014. A separability framework for analyzing community structure. ACM Transactions on Knowledge Discovery from Data 8, 1 (2014), 5."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature09182"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/3122009.3242082"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Reid Andersen Fan Chung and Kevin Lang. 2006. Local graph partitioning using PageRank vectors. In FOCS. 475--486.  Reid Andersen Fan Chung and Kevin Lang. 2006. Local graph partitioning using PageRank vectors. In FOCS. 475--486.","DOI":"10.1109\/FOCS.2006.44"},{"key":"e_1_2_1_6_1","volume-title":"Lang","author":"Andersen Reid","year":"2006","unstructured":"Reid Andersen and Kevin J . Lang . 2006 . Communities from seed sets. In WWW. ACM , 223--232. Reid Andersen and Kevin J. Lang. 2006. Communities from seed sets. In WWW. ACM, 223--232."},{"key":"e_1_2_1_7_1","volume-title":"Scalable and efficient flow-based community detection for large-scale graph analysis. ACM Transactions on Knowledge Discovery from Data 11, 3","author":"Bae Seung-Hee","year":"2017","unstructured":"Seung-Hee Bae , Daniel Halperin , Jevin D. West , Martin Rosvall , and Bill Howe . 2017. Scalable and efficient flow-based community detection for large-scale graph analysis. ACM Transactions on Knowledge Discovery from Data 11, 3 ( 2017 ), 32:1--32:30. Seung-Hee Bae, Daniel Halperin, Jevin D. West, Martin Rosvall, and Bill Howe. 2017. Scalable and efficient flow-based community detection for large-scale graph analysis. ACM Transactions on Knowledge Discovery from Data 11, 3 (2017), 32:1--32:30."},{"key":"e_1_2_1_8_1","volume-title":"Grace Mary Kanaga, and Piotr Br\u00f3dka","author":"Belfin R. V.","year":"2018","unstructured":"R. V. Belfin , E. Grace Mary Kanaga, and Piotr Br\u00f3dka . 2018 . Overlapping community detection using superior seed set selection in social networks. Computers 8 Electrical Engineering 70, 6 (2018) 1074--1083. R. V. Belfin, E. Grace Mary Kanaga, and Piotr Br\u00f3dka. 2018. Overlapping community detection using superior seed set selection in social networks. Computers 8 Electrical Engineering 70, 6 (2018) 1074--1083."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2008\/10\/P10008"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1986.11971855"},{"key":"e_1_2_1_11_1","volume-title":"Weighted modularity optimization for crisp and fuzzy community detection in large-scale networks. Physica A: Statistical Mechanics and its Applications 462, 22","author":"Cao Jie","year":"2016","unstructured":"Jie Cao , Zhan Bu , Guangliang Gao , and Haicheng Tao . 2016. Weighted modularity optimization for crisp and fuzzy community detection in large-scale networks. Physica A: Statistical Mechanics and its Applications 462, 22 ( 2016 ), 386--395. Jie Cao, Zhan Bu, Guangliang Gao, and Haicheng Tao. 2016. Weighted modularity optimization for crisp and fuzzy community detection in large-scale networks. Physica A: Statistical Mechanics and its Applications 462, 22 (2016), 386--395."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.neucom.2018.01.065"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Fun Chung. 1997. Spectral Graph Theory. American Mathematical Soc.  Fun Chung. 1997. Spectral Graph Theory. American Mathematical Soc.","DOI":"10.1090\/cbms\/092"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0708838104"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2009.10390643"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Fan Chung and Olivia Simpson. 2013. Solving linear systems with boundary conditions using heat kernel PageRank. In Algorithms and Models for the Web Graph (WAW\u201913). 203--219.  Fan Chung and Olivia Simpson. 2013. Solving linear systems with boundary conditions using heat kernel PageRank. In Algorithms and Models for the Web Graph (WAW\u201913). 203--219.","DOI":"10.1007\/978-3-319-03536-9_16"},{"key":"e_1_2_1_17_1","volume-title":"Demon: A local-first discovery method for overlapping communities. In KDD. ACM, 615--623.","author":"Coscia Michele","year":"2012","unstructured":"Michele Coscia , Giulio Rossetti , Fosca Giannotti , and Dino Pedreschi . 2012 . Demon: A local-first discovery method for overlapping communities. In KDD. ACM, 615--623. Michele Coscia, Giulio Rossetti, Fosca Giannotti, and Dino Pedreschi. 2012. Demon: A local-first discovery method for overlapping communities. In KDD. ACM, 615--623."},{"key":"e_1_2_1_18_1","volume-title":"Computational Complexity","author":"Fortunato Santo","unstructured":"Santo Fortunato and Claudio Castellano . 2012. Community structure in graphs . In Computational Complexity . Springer , 490--512. Santo Fortunato and Claudio Castellano. 2012. Community structure in graphs. In Computational Complexity. Springer, 490--512."},{"key":"e_1_2_1_19_1","volume-title":"Van Loan","author":"Golub Gene H.","year":"1996","unstructured":"Gene H. Golub and Charles F . Van Loan . 1996 . Matrix Computations (3rd ed.). Johns Hopkins University Press . Gene H. Golub and Charles F. Van Loan. 1996. Matrix Computations (3rd ed.). Johns Hopkins University Press."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783274"},{"key":"e_1_2_1_21_1","volume-title":"32nd AAAI Conference on Artificial Intelligence.","author":"He Dongxiao","year":"2018","unstructured":"Dongxiao He , Xinxin You , Zhiyong Feng , Di Jin , Xue Yang , and Weixiong Zhang . 2018 . A network-specific Markov random field approach to community detection . In 32nd AAAI Conference on Artificial Intelligence. Dongxiao He, Xinxin You, Zhiyong Feng, Di Jin, Xue Yang, and Weixiong Zhang. 2018. A network-specific Markov random field approach to community detection. In 32nd AAAI Conference on Artificial Intelligence."},{"key":"e_1_2_1_22_1","volume-title":"Hopcroft","author":"He Kun","year":"2018","unstructured":"Kun He , Yingru Li , Sucheta Soundarajan , and John E . Hopcroft . 2018 . Hidden community detection in social networks. Inf. Sci. 425, C ( 2018), 92--106. Kun He, Yingru Li, Sucheta Soundarajan, and John E. Hopcroft. 2018. Hidden community detection in social networks. Inf. Sci. 425, C (2018), 92--106."},{"key":"e_1_2_1_23_1","volume-title":"12th Workshop on Mining and Learning with Graphs.","author":"He Kun","year":"2016","unstructured":"Kun He , Pan Shi , John E. Hopcroft , and David Bindel . 2016 . Local spectral diffusion for robust community detection . In 12th Workshop on Mining and Learning with Graphs. Kun He, Pan Shi, John E. Hopcroft, and David Bindel. 2016. Local spectral diffusion for robust community detection. In 12th Workshop on Mining and Learning with Graphs."},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Kun He Yiwei Sun David Bindel John E. Hopcroft and Yixuan Li. 2015. Detecting overlapping communities from local spectral subspaces. In ICDM. 769--774.  Kun He Yiwei Sun David Bindel John E. Hopcroft and Yixuan Li. 2015. Detecting overlapping communities from local spectral subspaces. In ICDM. 769--774.","DOI":"10.1109\/ICDM.2015.89"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.91.012821"},{"key":"e_1_2_1_26_1","unstructured":"Ravi Kannan Santosh Vempala and Adrian Vetta. 2000. On clusterings--good bad and spectral. In FOCS. 367--377.  Ravi Kannan Santosh Vempala and Adrian Vetta. 2000. On clusterings--good bad and spectral. In FOCS. 367--377."},{"key":"e_1_2_1_27_1","volume-title":"Gleich","author":"Kloster Kyle","year":"2014","unstructured":"Kyle Kloster and David F . Gleich . 2014 . Heat kernel based community detection. In KDD. ACM , 1386--1395. Kyle Kloster and David F. Gleich. 2014. Heat kernel based community detection. In KDD. ACM, 1386--1395."},{"key":"e_1_2_1_28_1","volume-title":"Kleinberg","author":"Kloumann Isabel M.","year":"2014","unstructured":"Isabel M. Kloumann and Jon M . Kleinberg . 2014 . Community membership identification from small seed sets. In KDD. ACM , 1366--1375. Isabel M. Kloumann and Jon M. Kleinberg. 2014. Community membership identification from small seed sets. In KDD. ACM, 1366--1375."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.80.016118"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.78.046110"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0018961"},{"key":"e_1_2_1_32_1","volume-title":"Mahoney","author":"Leskovec Jure","year":"2008","unstructured":"Jure Leskovec , Kevin J. Lang , Anirban Dasgupta , and Michael W . Mahoney . 2008 . Statistical properties of community structure in large social and information networks. In WWW. 695--704. Jure Leskovec, Kevin J. Lang, Anirban Dasgupta, and Michael W. Mahoney. 2008. Statistical properties of community structure in large social and information networks. In WWW. 695--704."},{"key":"e_1_2_1_33_1","volume-title":"Hopcroft","author":"Li Yixuan","year":"2015","unstructured":"Yixuan Li , Kun He , David Bindel , and John E . Hopcroft . 2015 . Uncovering the small community structure in large networks. In WWW. 658--668. Yixuan Li, Kun He, David Bindel, and John E. Hopcroft. 2015. Uncovering the small community structure in large networks. In WWW. 658--668."},{"key":"e_1_2_1_34_1","volume-title":"Hopcroft","author":"Li Yixuan","year":"2018","unstructured":"Yixuan Li , Kun He , Kyle Kloster , David Bindel , and John E . Hopcroft . 2018 . Local spectral clustering for overlapping community detection. ACM Transactions on Knowledge Discovery from Data 12, 2 (2018), 17:1--17:27. Yixuan Li, Kun He, Kyle Kloster, David Bindel, and John E. Hopcroft. 2018. Local spectral clustering for overlapping community detection. ACM Transactions on Knowledge Discovery from Data 12, 2 (2018), 17:1--17:27."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/2503308.2503318"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.066133"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0601602103"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.88.042822"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature03607"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-011-0224-z"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.868688"},{"key":"e_1_2_1_42_1","volume-title":"Hopcroft","author":"Shi Pan","year":"2017","unstructured":"Pan Shi , Kun He , David Bindel , and John E . Hopcroft . 2017 . Local lanczos spectral approximation for community detection. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer , 651--667. Pan Shi, Kun He, David Bindel, and John E. Hopcroft. 2017. Local lanczos spectral approximation for community detection. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, 651--667."},{"key":"e_1_2_1_43_1","volume-title":"Hopcroft","author":"Soundarajan Sucheta","year":"2015","unstructured":"Sucheta Soundarajan and John E . Hopcroft . 2015 . Use of local group information to identify communities in networks. ACM Transactions on Knowledge Discovery from Data 9, 3 (2015), 21:1--21:27. Sucheta Soundarajan and John E. Hopcroft. 2015. Use of local group information to identify communities in networks. ACM Transactions on Knowledge Discovery from Data 9, 3 (2015), 21:1--21:27."},{"key":"e_1_2_1_44_1","volume-title":"Spielman and Shanghua Teng","author":"Danial","year":"2004","unstructured":"Danial A. Spielman and Shanghua Teng . 2004 . Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In STOC. 81--90. Danial A. Spielman and Shanghua Teng. 2004. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In STOC. 81--90."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/2946645.3007100"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11222-007-9033-z"},{"key":"e_1_2_1_47_1","doi-asserted-by":"crossref","unstructured":"Ingmar Weber Venkata R. Kiran Garimella and Alaa Batayneh. 2013. Secular vs. Islamist polarization in Egypt on Twitter. In ASONAM. 290--297.  Ingmar Weber Venkata R. Kiran Garimella and Alaa Batayneh. 2013. Secular vs. Islamist polarization in Egypt on Twitter. In ASONAM. 290--297.","DOI":"10.1145\/2492517.2492557"},{"key":"e_1_2_1_48_1","volume-title":"Dhillon","author":"Whang Joyce J.","year":"2013","unstructured":"Joyce J. Whang , David F. Gleich , and Inderjit S . Dhillon . 2013 . Overlapping community detection using seed set expansion. In CIKM. 2099--2108. Joyce J. Whang, David F. Gleich, and Inderjit S. Dhillon. 2013. Overlapping community detection using seed set expansion. In CIKM. 2099--2108."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2518687"},{"key":"e_1_2_1_50_1","doi-asserted-by":"crossref","unstructured":"Yubao Wu Ruoming Jin Jing Li and Xiang Zhang. 2015. Robust local community detection: On free rider effect and its elimination. In VLDB. 798--809.  Yubao Wu Ruoming Jin Jing Li and Xiang Zhang. 2015. Robust local community detection: On free rider effect and its elimination. In VLDB. 798--809.","DOI":"10.14778\/2752939.2752948"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2501654.2501657"},{"key":"e_1_2_1_52_1","doi-asserted-by":"crossref","unstructured":"Jaewon Yang and Jure Leskovec. 2012. Defining and evaluating network communities based on ground-truth. In ICDM. 745--754.  Jaewon Yang and Jure Leskovec. 2012. Defining and evaluating network communities based on ground-truth. In ICDM. 745--754.","DOI":"10.1109\/ICDM.2012.138"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2433396.2433471"},{"key":"e_1_2_1_54_1","volume-title":"Identification of overlapping community structure in complex networks using fuzzy c-means clustering. Physica A: Statistical Mechanics and its Applications 374, 1","author":"Zhang Shihua","year":"2007","unstructured":"Shihua Zhang , Rui-Sheng Wang , and Xiang-Sun Zhang . 2007. Identification of overlapping community structure in complex networks using fuzzy c-means clustering. Physica A: Statistical Mechanics and its Applications 374, 1 ( 2007 ), 483--490. Shihua Zhang, Rui-Sheng Wang, and Xiang-Sun Zhang. 2007. Identification of overlapping community structure in complex networks using fuzzy c-means clustering. Physica A: Statistical Mechanics and its Applications 374, 1 (2007), 483--490."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339629"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3340708","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3340708","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:11Z","timestamp":1750200071000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3340708"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,24]]},"references-count":55,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,10,31]]}},"alternative-id":["10.1145\/3340708"],"URL":"https:\/\/doi.org\/10.1145\/3340708","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9,24]]},"assertion":[{"value":"2018-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-09-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}