{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T21:37:02Z","timestamp":1773524222977,"version":"3.50.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T00:00:00Z","timestamp":1648944000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T00:00:00Z","timestamp":1648944000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Big Data"],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract\ufeff<\/jats:title><jats:p>Community Search is the problem of querying networks in order to discover dense subgraphs-communities-that satisfy given query parameters. Most community search models consider link structure and ignore link weight while answering the required queries. Given the importance of link weight in different networks, this paper considers both link structure and link weight to discover top-r weighted k-truss communities via community search. The top-weighted k-truss communities are those communities with the highest weight and the highest cohesiveness within the network. All recent studies that considered link weight discover top-weighted communities via global search and index-based search techniques. In this paper three different algorithms are proposed to scale-up the existing approaches of weighted community search via local search. The performance evaluation shows that the proposed algorithms significantly outperform the existing state-of-the-art algorithms over different datasets in terms of search time by several orders of magnitude.<\/jats:p>","DOI":"10.1186\/s40537-022-00588-1","type":"journal-article","created":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T15:02:18Z","timestamp":1648998138000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Discovering top-weighted k-truss communities in large graphs"],"prefix":"10.1186","volume":"9","author":[{"given":"Wafaa M. A.","family":"Habib","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hoda M. O.","family":"Mokhtar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohamed E.","family":"El-Sharkawi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,4,3]]},"reference":[{"key":"588_CR1","first-page":"3","volume":"16","author":"J Cohen","year":"2008","unstructured":"Cohen J. Trusses: Cohesive subgraphs for social network analysis. Natl Secur Agency Tech Rep. 2008;16:3\u20131.","journal-title":"Natl Secur Agency Tech Rep"},{"issue":"9","key":"588_CR2","doi-asserted-by":"publisher","first-page":"812","DOI":"10.14778\/2311906.2311909","volume":"5","author":"J Wang","year":"2012","unstructured":"Wang J, Cheng J. Truss decomposition in massive networks. Proc VLDB Endow. 2012;5(9):812\u201323.","journal-title":"Proc VLDB Endow"},{"issue":"5","key":"588_CR3","doi-asserted-by":"publisher","first-page":"509","DOI":"10.14778\/2735479.2735484","volume":"8","author":"RH Li","year":"2015","unstructured":"Li RH, Qin L, Yu JX, Mao R. Influential community search in large networks. Proc VLDB Endow. 2015;8(5):509\u201320.","journal-title":"Proc VLDB Endow"},{"key":"588_CR4","doi-asserted-by":"crossref","unstructured":"Cui W, Xiao Y, Wang H, Wang W. Local Search of Communities in Large Graphs. In: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. SIGMOD \u201914. New York, NY, USA: ACM; 2014. p. 991\u20131002. http:\/\/doi.acm.org\/10.1145\/2588555.2612179.","DOI":"10.1145\/2588555.2612179"},{"key":"588_CR5","doi-asserted-by":"crossref","unstructured":"Huang X, Cheng H, Qin L, Tian W, Yu JX. Querying k-truss community in large and dynamic graphs. In: Proceedings of the 2014 ACM SIGMOD international conference on Management of data. ACM; 2014. p. 1311\u20131322.","DOI":"10.1145\/2588555.2610495"},{"issue":"11","key":"588_CR6","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.14778\/3137628.3137640","volume":"10","author":"E Akbas","year":"2017","unstructured":"Akbas E, Zhao P. Truss-based community search: a truss-equivalence based indexing approach. Proc VLDB Endow. 2017;10(11):1298\u2013309.","journal-title":"Proc VLDB Endow"},{"issue":"9","key":"588_CR7","doi-asserted-by":"publisher","first-page":"949","DOI":"10.14778\/3099622.3099626","volume":"10","author":"X Huang","year":"2017","unstructured":"Huang X, Lakshmanan LV. Attribute-driven community search. Proc VLDB Endow. 2017;10(9):949\u201360.","journal-title":"Proc VLDB Endow"},{"key":"588_CR8","doi-asserted-by":"crossref","unstructured":"Chen S, Wei R, Popova D, Thomo A. Efficient computation of importance based communities in web-scale networks using a single machine. In: Proceedings of the 25th ACM International on Conference on Information and Knowledge Management. ACM; 2016. p. 1553\u20131562.","DOI":"10.1145\/2983323.2983836"},{"issue":"3\u20135","key":"588_CR9","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.physrep.2009.11.002","volume":"486","author":"S Fortunato","year":"2010","unstructured":"Fortunato S. Community detection in graphs. Phys Rep. 2010;486(3\u20135):75\u2013174.","journal-title":"Phys Rep"},{"key":"588_CR10","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1016\/j.ins.2017.07.012","volume":"417","author":"Z Zheng","year":"2017","unstructured":"Zheng Z, Ye F, Li RH, Ling G, Jin T. Finding weighted k-truss communities in large networks. Inf Sci. 2017;417:344\u201360.","journal-title":"Inf Sci"},{"issue":"11","key":"588_CR11","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/12\/11\/113043","volume":"12","author":"A Garas","year":"2010","unstructured":"Garas A, Argyrakis P, Rozenblat C, Tomassini M, Havlin S. Worldwide spreading of economic crisis. New J Phys. 2010;12(11): 113043.","journal-title":"New J Phys"},{"issue":"9","key":"588_CR12","doi-asserted-by":"publisher","first-page":"1056","DOI":"10.14778\/3213880.3213881","volume":"11","author":"F Bi","year":"2018","unstructured":"Bi F, Chang L, Lin X, Zhang W. An optimal and progressive approach to online search of top-k influential communities. Proc VLDB Endow. 2018;11(9):1056\u201368.","journal-title":"Proc VLDB Endow"},{"issue":"2","key":"588_CR13","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1109\/TKDE.2016.2618795","volume":"29","author":"L Chang","year":"2017","unstructured":"Chang L, Li W, Qin L, Zhang W, Yang S. Fast and exact structural graph clustering. IEEE Trans Knowl Data Eng. 2017;29(2):387\u2013401.","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"588_CR14","doi-asserted-by":"crossref","unstructured":"Shao J, Han Z, Yang Q, Zhou T. Community Detection Based on Distance Dynamics. In: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD \u201915. New York, NY, USA: ACM; 2015. p. 1075\u20131084. http:\/\/doi.acm.org\/10.1145\/2783258.2783301.","DOI":"10.1145\/2783258.2783301"},{"issue":"1","key":"588_CR15","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/s10115-013-0693-z","volume":"42","author":"J Yang","year":"2015","unstructured":"Yang J, Leskovec J. Defining and evaluating network communities based on ground-truth. Knowl Inf Syst. 2015;42(1):181\u2013213.","journal-title":"Knowl Inf Syst"},{"key":"588_CR16","doi-asserted-by":"crossref","unstructured":"Huang X, Lu W, Lakshmanan LV. Truss decomposition of probabilistic graphs: Semantics and algorithms. In: Proceedings of the 2016 International Conference on Management of Data; 2016. p. 77\u201390.","DOI":"10.1145\/2882903.2882913"},{"issue":"4","key":"588_CR17","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1145\/2043652.2043654","volume":"36","author":"J Cheng","year":"2011","unstructured":"Cheng J, Ke Y, Fu AWC, Yu JX, Zhu L. Finding maximal cliques in massive networks. ACM Trans Database Syst. 2011;36(4):21.","journal-title":"ACM Trans Database Syst"},{"key":"588_CR18","doi-asserted-by":"crossref","unstructured":"Cheng J, Zhu L, Ke Y, Chu S. Fast algorithms for maximal clique enumeration with limited memory. In: Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM; 2012. p. 1240\u20131248.","DOI":"10.1145\/2339530.2339724"},{"key":"588_CR19","doi-asserted-by":"crossref","unstructured":"Tsourakakis C, Bonchi F, Gionis A, Gullo F, Tsiarli M. Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees. In: Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM; 2013. p. 104\u2013112.","DOI":"10.1145\/2487575.2487645"},{"key":"588_CR20","doi-asserted-by":"crossref","unstructured":"Cheng J, Ke Y, Chu S, \u00d6zsu MT. Efficient core decomposition in massive networks. In: 2011 IEEE 27th International Conference on Data Engineering. IEEE; 2011. p. 51\u201362.","DOI":"10.1109\/ICDE.2011.5767911"},{"issue":"1","key":"588_CR21","doi-asserted-by":"publisher","first-page":"13","DOI":"10.14778\/2850469.2850471","volume":"9","author":"W Khaouid","year":"2015","unstructured":"Khaouid W, Barsky M, Srinivasan V, Thomo A. K-core decomposition of large networks on a single PC. Proc VLDB Endow. 2015;9(1):13\u201323.","journal-title":"Proc VLDB Endow"},{"key":"588_CR22","doi-asserted-by":"crossref","unstructured":"Charikar M. Greedy approximation algorithms for finding dense components in a graph. In: International Workshop on Approximation Algorithms for Combinatorial Optimization. Springer; 2000. p. 84\u201395.","DOI":"10.1007\/3-540-44436-X_10"},{"key":"588_CR23","unstructured":"Goldberg AV. Finding a maximum density subgraph. In: Tech. Report No. UCB CSD 84\/171. Computer Science Division (EECS), University of California, Berkeley, CA, 1984."},{"key":"588_CR24","doi-asserted-by":"crossref","unstructured":"Chang L, Yu JX, Qin L, Lin X, Liu C, Liang W. Efficiently computing k-edge connected components via graph decomposition. In: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. ACM; 2013. p. 205\u2013216.","DOI":"10.1145\/2463676.2465323"},{"key":"588_CR25","doi-asserted-by":"crossref","unstructured":"Zhou R, Liu C, Yu JX, Liang W, Chen B, Li J. Finding maximal k-edge-connected subgraphs from a large graph. In: Proceedings of the 15th International Conference on Extending Database Technology. ACM; 2012. p. 480\u2013491.","DOI":"10.1145\/2247596.2247652"},{"key":"588_CR26","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/j.is.2019.03.014","volume":"83","author":"M Alemi","year":"2019","unstructured":"Alemi M, Haghighi H. KTMiner: distributed k-truss detection in big graphs. Inf Syst. 2019;83:195\u2013216.","journal-title":"Inf Syst"},{"key":"588_CR27","doi-asserted-by":"crossref","unstructured":"Sozio M, Gionis A. The community-search problem and how to plan a successful cocktail party. In: Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM; 2010. p. 939\u2013948.","DOI":"10.1145\/1835804.1835923"},{"key":"588_CR28","doi-asserted-by":"crossref","unstructured":"Cui W, Xiao Y, Wang H, Lu Y, Wang W. Online search of overlapping communities. In: Proceedings of the 2013 ACM SIGMOD international conference on Management of data. ACM; 2013. p. 277\u2013288.","DOI":"10.1145\/2463676.2463722"},{"issue":"7","key":"588_CR29","doi-asserted-by":"publisher","first-page":"798","DOI":"10.14778\/2752939.2752948","volume":"8","author":"Y Wu","year":"2015","unstructured":"Wu Y, Jin R, Li J, Zhang X. Robust local community detection: on free rider effect and its elimination. Proc VLDB Endow. 2015;8(7):798\u2013809.","journal-title":"Proc VLDB Endow"},{"key":"588_CR30","doi-asserted-by":"crossref","unstructured":"Zhu Y, He J, Ye J, Qin L, Huang X, Yu JX. When Structure Meets Keywords: Cohesive Attributed Community Search. In: Proceedings of the 29th ACM International Conference on Information & Knowledge Management; 2020. p. 1913\u20131922.","DOI":"10.1145\/3340531.3412006"},{"key":"588_CR31","doi-asserted-by":"publisher","first-page":"148841","DOI":"10.1109\/ACCESS.2020.3016214","volume":"8","author":"WM Habib","year":"2020","unstructured":"Habib WM, Mokhtar HM, El-Sharkawi ME. Weight-Based K-Truss Community Search via Edge Attachment. IEEE Access. 2020;8:148841\u2013148852.","journal-title":"IEEE Access."},{"key":"588_CR32","doi-asserted-by":"crossref","unstructured":"Shao Y, Chen L, Cui B. Efficient cohesive subgraphs detection in parallel. In: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data; 2014. p. 613\u2013624.","DOI":"10.1145\/2588555.2593665"},{"issue":"1\u20133","key":"588_CR33","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1016\/j.tcs.2008.07.017","volume":"407","author":"M Latapy","year":"2008","unstructured":"Latapy M. Main-memory triangle computations for very large (sparse (power-law)) graphs. Theor Comput Sci. 2008;407(1\u20133):458\u201373.","journal-title":"Theor Comput Sci"},{"key":"588_CR34","unstructured":"https:\/\/snap.stanford.edu\/data\/."}],"container-title":["Journal of Big Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s40537-022-00588-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s40537-022-00588-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s40537-022-00588-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T15:03:45Z","timestamp":1648998225000},"score":1,"resource":{"primary":{"URL":"https:\/\/journalofbigdata.springeropen.com\/articles\/10.1186\/s40537-022-00588-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,3]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["588"],"URL":"https:\/\/doi.org\/10.1186\/s40537-022-00588-1","relation":{},"ISSN":["2196-1115"],"issn-type":[{"value":"2196-1115","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,3]]},"assertion":[{"value":"19 November 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 March 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 April 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"36"}}