{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T20:35:24Z","timestamp":1780346124345,"version":"3.54.1"},"reference-count":83,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,11]]},"abstract":"<jats:p>\n            In applications such as biological, social, and transportation networks, interactions between objects span multiple aspects. For accurately modeling such applications, multilayer networks have been proposed. Community search allows for personalized community discovery and has a wide range of applications in large real-world networks. While community search has been widely explored for single-layer graphs, the problem for multilayer graphs has just recently attracted attention. Existing community models in multilayer graphs have several limitations, including disconnectivity, free-rider effect, resolution limits, and inefficiency. To address these limitations, we study the problem of community search over large multilayer graphs. We first introduce\n            <jats:italic>FirmTruss<\/jats:italic>\n            , a novel dense structure in multilayer networks, which extends the notion of truss to multilayer graphs. We show that FirmTrusses possess nice structural and computational properties and bring many advantages compared to the existing models. Building on this, we present a new community model based on FirmTruss, called\n            <jats:italic>FTCS<\/jats:italic>\n            , and show that finding an FTCS community is NP-hard. We propose two efficient 2-approximation algorithms, and show that no polynomial-time algorithm can have a better approximation guarantee unless P = NP. We propose an index-based method to further improve the efficiency of the algorithms. We then consider attributed multilayer networks and propose a new community model based on network homophily. We show that community search in attributed multilayer graphs is NP-hard and present an effective and efficient approximation algorithm. Experimental studies on real-world graphs with ground-truth communities validate the quality of the solutions we obtain and the efficiency of the proposed algorithms.\n          <\/jats:p>","DOI":"10.14778\/3570690.3570700","type":"journal-article","created":{"date-parts":[[2023,1,23]],"date-time":"2023-01-23T17:29:55Z","timestamp":1674494995000},"page":"505-518","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["FirmTruss Community Search in Multilayer Networks"],"prefix":"10.14778","volume":"16","author":[{"given":"Ali","family":"Behrouz","sequence":"first","affiliation":[{"name":"University of British Columbia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Farnoosh","family":"Hashemi","sequence":"additional","affiliation":[{"name":"University of British Columbia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Laks V. S.","family":"Lakshmanan","sequence":"additional","affiliation":[{"name":"University of British Columbia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,1,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467154"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137640"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-conmatphys-031218-013259"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1038\/75556"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.90.032816"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3511808.3557572"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2205.00742"},{"key":"e_1_2_1_8_1","volume-title":"NeurIPS 2022 Temporal Graph Learning Workshop. https:\/\/openreview.net\/forum?id=UDGZDfwmay","author":"Behrouz Ali","year":"2022","unstructured":"Ali Behrouz and Margo Seltzer . 2022 . Anomaly Detection in Multiplex Dynamic Networks: from Blockchain Security to Brain Disease Prediction . In NeurIPS 2022 Temporal Graph Learning Workshop. https:\/\/openreview.net\/forum?id=UDGZDfwmay Ali Behrouz and Margo Seltzer. 2022. Anomaly Detection in Multiplex Dynamic Networks: from Blockchain Security to Brain Disease Prediction. In NeurIPS 2022 Temporal Graph Learning Workshop. https:\/\/openreview.net\/forum?id=UDGZDfwmay"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0911855107"},{"key":"e_1_2_1_10_1","volume-title":"Jordan","author":"Blei David M.","year":"2003","unstructured":"David M. Blei , Andrew Y. Ng , and Michael I . Jordan . 2003 . Latent Dirichlet Allocation. J. Mach. Learn. Res . 3, null (mar 2003), 993--1022. David M. Blei, Andrew Y. Ng, and Michael I. Jordan. 2003. Latent Dirichlet Allocation. J. Mach. Learn. Res. 3, null (mar 2003), 993--1022."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2728170"},{"key":"e_1_2_1_12_1","volume-title":"International Conference on Social Computing, Behavioral Modeling and Prediction (Lecture Notes in Computer Science). Springer Berlin Heidelberg","author":"Celli Fabio","year":"2010","unstructured":"Fabio Celli , F Marta L Di Lascio , Matteo Magnani , Barbara Pacelli , and Luca Rossi . 2010 . Social Network Data and Practices: the case of Friendfeed . In International Conference on Social Computing, Behavioral Modeling and Prediction (Lecture Notes in Computer Science). Springer Berlin Heidelberg , New York, NY, USA, -. Fabio Celli, F Marta L Di Lascio, Matteo Magnani, Barbara Pacelli, and Luca Rossi. 2010. Social Network Data and Practices: the case of Friendfeed. In International Conference on Social Computing, Behavioral Modeling and Prediction (Lecture Notes in Computer Science). Springer Berlin Heidelberg, New York, NY, USA, -."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783292"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00017"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3231751.3231755"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463722"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"M. De Domenico A. Lima P. Mougel and M. Musolesi. 2013. The Anatomy of a Scientific Rumor. Scientific Reports 3 1 (2013) -.  M. De Domenico A. Lima P. Mougel and M. Musolesi. 2013. The Anatomy of a Scientific Rumor. Scientific Reports 3 1 (2013) -.","DOI":"10.1038\/srep02980"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1093\/comnet\/cnu038"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"M. De Domenico V. Nicosia A. Arenas and V. Latora. 2015. Structural reducibility of multilayer networks. Nature communications 6 (2015) 6864.  M. De Domenico V. Nicosia A. Arenas and V. Latora. 2015. Structural reducibility of multilayer networks. Nature communications 6 (2015) 6864.","DOI":"10.1038\/ncomms7864"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476258"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0482-5"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994538"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.1904.12539"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2872982"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00273"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0605965104"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972825.15"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132993"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3369872"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/3447689.3447704"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2398776.2398792"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41398-021-01278-x"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable Feature Learning for Networks. arXiv:1607.00653 [cs.SI]  Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable Feature Learning for Networks. arXiv:1607.00653 [cs.SI]","DOI":"10.1145\/2939672.2939754"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00017"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485447.3512205"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2013.37"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983323.2983748"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData52589.2021.9671831"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33019945"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-020-00716-6"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3099622.3099626"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856323"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-017-0525-y"},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","unstructured":"V. Jethava and N. Beerenwinkel. 2015. Finding Dense Subgraphs in Relational Graphs. In Machine Learning and Knowledge Discovery in Databases Annalisa Appice Pedro Pereira Rodrigues Vitor Santos Costa Jo\u00e3o Gama Al\u00edpio Jorge and Carlos Soares (Eds.). Springer International Publishing Cham 641--654.  V. Jethava and N. Beerenwinkel. 2015. Finding Dense Subgraphs in Relational Graphs. In Machine Learning and Knowledge Discovery in Databases Annalisa Appice Pedro Pereira Rodrigues Vitor Santos Costa Jo\u00e3o Gama Al\u00edpio Jorge and Carlos Soares (Eds.). Springer International Publishing Cham 641--654.","DOI":"10.1007\/978-3-319-23525-7_39"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2104.03583"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.neuropsychologia.2015.10.033"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_50"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2854006.2854013"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1093\/comnet\/cnu016"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403383"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1232722.1232727"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183736"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00077"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-34223-4_44"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00086"},{"key":"e_1_2_1_59_1","volume-title":"Robustness and lethality in multilayer biological molecular networks. Nature Communications 11","author":"Liu Xueming","year":"2020","unstructured":"Xueming Liu , Enrico Maiorino , Arda Halu , Kimberly Glass , Rashmi B. Prasad , and Joseph Loscalzo . 2020. Robustness and lethality in multilayer biological molecular networks. Nature Communications 11 ( 2020 ), -. Xueming Liu, Enrico Maiorino, Arda Halu, Kimberly Glass, Rashmi B. Prasad, and Joseph Loscalzo. 2020. Robustness and lethality in multilayer biological molecular networks. Nature Communications 11 (2020), -."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403069"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.3389\/fphy.2015.00059"},{"key":"e_1_2_1_62_1","volume-title":"Porter","author":"Peng Kaiyan","year":"2021","unstructured":"Kaiyan Peng , Zheng Lu , Vanessa Lin , Michael R. Lindstrom , Christian Parkinson , Chuntian Wang , Andrea L. Bertozzi , and Mason A . Porter . 2021 . A Multilayer Network Model of the Coevolution of the Spread of a Disease and Competing Opinions . arXiv:2107.01713 [cs.SI] Kaiyan Peng, Zheng Lu, Vanessa Lin, Michael R. Lindstrom, Christian Parkinson, Chuntian Wang, Andrea L. Bertozzi, and Mason A. Porter. 2021. A Multilayer Network Model of the Coevolution of the Spread of a Disease and Competing Opinions. arXiv:2107.01713 [cs.SI]"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.neuron.2011.09.006S0896-6273(11)00792-6[PII"},{"key":"e_1_2_1_64_1","unstructured":"N. Roberts and S. Everton. 2011. The Noordin Top Terrorist Network Data. (2011). http:\/\/www.thearda.com\/Archive\/Files\/Descriptions\/  N. Roberts and S. Everton. 2011. The Noordin Top Terrorist Network Data. (2011). http:\/\/www.thearda.com\/Archive\/Files\/Descriptions\/"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.nicl.2017.05.016"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1209\/0295-5075\/112\/58001"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835923"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835923"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.2147\/NDT.S239013"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-017-0528-8"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1116502109"},{"key":"e_1_2_1_72_1","article-title":"A survey on similarity measures in text mining","volume":"3","author":"Vijaymeena MK","year":"2016","unstructured":"MK Vijaymeena and K Kavitha . 2016 . A survey on similarity measures in text mining . Machine Learning and Applications: An International Journal 3 , 2 (2016). MK Vijaymeena and K Kavitha. 2016. A survey on similarity measures in text mining. Machine Learning and Applications: An International Journal 3, 2 (2016).","journal-title":"Machine Learning and Applications: An International Journal"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-017-0051-3"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.14778\/2752939.2752948"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/2350190.2350193"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2783933"},{"key":"e_1_2_1_78_1","volume-title":"Null model and community structure in multiplex networks. Scientific reports 8, 1","author":"Zhai Xuemeng","year":"2018","unstructured":"Xuemeng Zhai , Wanlei Zhou , Gaolei Fei , Weiyi Liu , Zhoujun Xu , Chengbo Jiao , Cai Lu , and Guangmin Hu. 2018. Null model and community structure in multiplex networks. Scientific reports 8, 1 ( 2018 ), 1--13. Xuemeng Zhai, Wanlei Zhou, Gaolei Fei, Weiyi Liu, Zhoujun Xu, Chengbo Jiao, Cai Lu, and Guangmin Hu. 2018. Null model and community structure in multiplex networks. Scientific reports 8, 1 (2018), 1--13."},{"key":"e_1_2_1_79_1","volume-title":"2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 422--433","author":"Zhang Zhiwei","year":"2019","unstructured":"Zhiwei Zhang , Xin Huang , Jianliang Xu , Byron Choi , and Zechao Shang . 2019 . Keyword-centric community search . In 2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 422--433 . Zhiwei Zhang, Xin Huang, Jianliang Xu, Byron Choi, and Zechao Shang. 2019. Keyword-centric community search. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 422--433."},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2017.07.012"},{"key":"e_1_2_1_81_1","doi-asserted-by":"crossref","unstructured":"Qijun Zhu Haibo Hu Cheng Xu Jianliang Xu and Wang-Chien Lee. 2017. Geo-Social Group Queries with Minimum Acquaintance Constraint. arXiv:1406.7367 [cs.DB]  Qijun Zhu Haibo Hu Cheng Xu Jianliang Xu and Wang-Chien Lee. 2017. Geo-Social Group Queries with Minimum Acquaintance Constraint. arXiv:1406.7367 [cs.DB]","DOI":"10.1007\/s00778-017-0473-6"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00069"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00141"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3570690.3570700","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,23]],"date-time":"2023-01-23T17:34:24Z","timestamp":1674495264000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3570690.3570700"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11]]},"references-count":83,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["10.14778\/3570690.3570700"],"URL":"https:\/\/doi.org\/10.14778\/3570690.3570700","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,11]]},"assertion":[{"value":"2023-01-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}