{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:57:28Z","timestamp":1775638648925,"version":"3.50.1"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2018,5]]},"abstract":"<jats:p>\n            Community search over large graphs is a fundamental problem in graph analysis. Recent studies propose to compute top-\n            <jats:italic>k<\/jats:italic>\n            influential communities, where each reported community not only is a cohesive subgraph but also has a high influence value. The existing approaches to the problem of top-\n            <jats:italic>k<\/jats:italic>\n            influential community search can be categorized as index-based algorithms and online search algorithms without indexes. The index-based algorithms, although being very efficient in conducting community searches, need to pre-compute a special-purpose index and only work for one built-in vertex weight vector. In this paper, we investigate online search approaches and propose an\n            <jats:italic>instance-optimal<\/jats:italic>\n            algorithm LocalSearch whose time complexity is linearly proportional to the size of the smallest subgraph that a correct algorithm needs to access without indexes. In addition, we also propose techniques to make LocalSearch\n            <jats:italic>progressively<\/jats:italic>\n            compute and report the communities in decreasing influence value order such that\n            <jats:italic>k<\/jats:italic>\n            does not need to be specified. Moreover, we extend our framework to the general case of top-\n            <jats:italic>k<\/jats:italic>\n            influential community search regarding other cohesiveness measures. Extensive empirical studies on real graphs demonstrate that our algorithms outperform the existing online search algorithms by several orders of magnitude.\n          <\/jats:p>","DOI":"10.14778\/3213880.3213881","type":"journal-article","created":{"date-parts":[[2018,6,12]],"date-time":"2018-06-12T18:15:11Z","timestamp":1528827311000},"page":"1056-1068","source":"Crossref","is-referenced-by-count":48,"title":["An optimal and progressive approach to online search of top-k influential communities"],"prefix":"10.14778","volume":"11","author":[{"given":"Fei","family":"Bi","sequence":"first","affiliation":[{"name":"University of New South Wales, Australia"}]},{"given":"Lijun","family":"Chang","sequence":"additional","affiliation":[{"name":"The University of Sydney, Australia"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"University of New South Wales, Australia"}]},{"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of New South Wales, Australia"}]}],"member":"320","published-online":{"date-parts":[[2018,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-015-0422-1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0603056"},{"key":"e_1_2_1_3_1","volume-title":"An optimal and progressive approach to online search of top-k influential communities. CoRR'17, abs\/1711.05857","author":"Bi F.","year":"2017"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-7-488"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2618795"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2746486"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465323"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/646688.702972"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983323.2983836"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.06.015"},{"key":"e_1_2_1_13_1","volume-title":"Introduction to Algorithms (3. ed.)","author":"Cormen T. H.","year":"2009"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00026-6"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.21136\/CMJ.1973.101168"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972825.15"},{"key":"e_1_2_1_18_1","volume-title":"USA","author":"Goldberg A. V.","year":"1984"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/978-0-387-21606-5_9","volume-title":"The Elements ofStatistical Learning","author":"Hastie T.","year":"2001"},{"issue":"8","key":"e_1_2_1_20_1","first-page":"158","article-title":"A direct approach to graph clustering","volume":"4","author":"Hlaoui A.","year":"2004","journal-title":"Neural Networks and Computational Intelligence"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2730873"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.211"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856323"},{"key":"e_1_2_1_25_1","volume-title":"An efficient heuristic procedure for partitioning graphs. The Bell system technical journal, 49(2):291--307","author":"Kernighan B. W.","year":"1970"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.136"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735484"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0467-4"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1140\/epjb\/e2004-00124-y"},{"key":"e_1_2_1_30_1","first-page":"849","volume-title":"Proc. of NIPS' 01","author":"Ng A. Y.","year":"2001"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273496.1273595"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2006.76"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021927"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-44871-6_108"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90028-X"},{"key":"e_1_2_1_36_1","first-page":"731","volume-title":"Proc. of CVPR'97","author":"Shi J.","year":"1997"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835923"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/31.1742"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/2752939.2752948"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2247596.2247652"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3213880.3213881","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:01:08Z","timestamp":1672221668000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3213880.3213881"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5]]},"references-count":39,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2018,5]]}},"alternative-id":["10.14778\/3213880.3213881"],"URL":"https:\/\/doi.org\/10.14778\/3213880.3213881","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,5]]}}}