{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,22]],"date-time":"2024-07-22T07:12:31Z","timestamp":1721632351587},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","funder":[{"name":"U.S. Department of Energy, Office of Science","award":["DE-AC02-06CH11357"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"\n Networks model a variety of complex phenomena across different domains. In many applications, one of the most essential tasks is to align two or more networks to infer the similarities between cross-network vertices and to discover potential node-level correspondence. In this article, we propose ELRUNA (\n el<\/jats:bold>\n imination\n ru<\/jats:bold>\n le-based\n n<\/jats:bold>\n etwork\n a<\/jats:bold>\n lignment), a novel network alignment algorithm that relies exclusively on the underlying graph structure. Under the guidance of the elimination rules that we defined, ELRUNA computes the similarity between a pair of cross-network vertices iteratively by accumulating the similarities between their selected neighbors. The resulting cross-network similarity matrix is then used to infer a permutation matrix that encodes the final alignment of cross-network vertices. In addition to the novel alignment algorithm, we improve the performance of\n local search<\/jats:italic>\n , a commonly used postprocessing step for solving the network alignment problem, by introducing a novel selection method RAWSEM (\n ra<\/jats:bold>\n ndom-\n w<\/jats:bold>\n alk-based\n se<\/jats:bold>\n lection\n m<\/jats:bold>\n ethod) based on the propagation of vertices\u2019 mismatching across the networks. The key idea is to pass on the initial levels of mismatching of vertices throughout the entire network in a random-walk fashion. Through extensive numerical experiments on real networks, we demonstrate that ELRUNA significantly outperforms the state-of-the-art alignment methods in terms of alignment accuracy under lower or comparable running time. Moreover, ELRUNA is robust to network perturbations such that it can maintain a close-to-optimal objective value under a high level of noise added to the original networks. Finally, the proposed RAWSEM can further improve the alignment quality with a smaller number of iterations compared with the naive local search method.\n <\/jats:p>\n \n Reproducibility<\/jats:bold>\n : The source code and data are available at https:\/\/tinyurl.com\/uwn35an.\n <\/jats:p>","DOI":"10.1145\/3450703","type":"journal-article","created":{"date-parts":[[2021,7,9]],"date-time":"2021-07-09T15:06:22Z","timestamp":1625843182000},"page":"1-32","source":"Crossref","is-referenced-by-count":3,"title":["ELRUNA"],"prefix":"10.1145","volume":"26","author":[{"given":"Zirou","family":"Qiu","sequence":"first","affiliation":[{"name":"Clemson University"}]},{"given":"Ruslan","family":"Shaydulin","sequence":"additional","affiliation":[{"name":"Clemson University"}]},{"given":"Xiaoyuan","family":"Liu","sequence":"additional","affiliation":[{"name":"Clemson University"}]},{"given":"Yuri","family":"Alexeev","sequence":"additional","affiliation":[{"name":"Argonne National Laboratory"}]},{"given":"Christopher S.","family":"Henry","sequence":"additional","affiliation":[{"name":"Argonne National Laboratory"}]},{"given":"Ilya","family":"Safro","sequence":"additional","affiliation":[{"name":"University of Delaware"}]}],"member":"320","published-online":{"date-parts":[[2021,7,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"A. Barab\u00e1si and R. Albert. 1999. Emergence of scaling in random networks. Science 286 5439 (1999) 509\u2013512. A. Barab\u00e1si and R. Albert. 1999. Emergence of scaling in random networks. Science 286 5439 (1999) 509\u2013512.","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 9th IEEE International Conference on Data Mining. 705\u2013710","author":"Bayati M."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.056122"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/CSE.2009.439"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098040"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2019.2913233"},{"key":"e_1_2_1_7_1","first-page":"472","article-title":"Survey of local and global biological network alignment: The need to reconcile the two sides of the same coin","volume":"19","author":"Hiram Guzzi P.","year":"2017","journal-title":"Briefings. Bioinf."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btw447"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btu450"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-93040-4_57"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3269206.3271788"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.65.026107"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-10-S1-S59"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.2200\/S00796ED1V01Y201708DMK014"},{"key":"e_1_2_1_15_1","volume-title":"2013 Proceedings of the 13th International Conference on Data Mining (ICDM\u201913)","author":"Koutra D."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the International Conference on Advances in Neural Information Processing Systems. 539\u2013547","author":"Leskovec Jure"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btp203"},{"key":"e_1_2_1_18_1","volume-title":"International Conference on 31st AAAI Conference on Artificial Intelligence.","author":"Liu Yangwei","year":"2017"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1039\/c2ib00140c"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btt202"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bts592"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/100791142"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897350.2897355"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.10.004"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2670338"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btu409"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2019.2908942"},{"key":"e_1_2_1_29_1","unstructured":"R. Shaydulin H. Ushijima-Mwesigwa I. Safro S. Mniszewski and Y. Alexeev. 2018. Community detection across emerging quantum architectures. arXiv preprint arXiv:1810.07765 (2018). R. Shaydulin H. Ushijima-Mwesigwa I. Safro S. Mniszewski and Y. Alexeev. 2018. Community detection across emerging quantum architectures. arXiv preprint arXiv:1810.07765 (2018)."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1002\/qute.201900029"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0806627105"},{"key":"e_1_2_1_32_1","volume-title":"Multilevel combinatorial optimization across quantum architectures. arXiv preprint arXiv:1910.09985","author":"Ushijima-Mwesigwa Hayato","year":"2019"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btx246"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btv161"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 2nd ACM Workshop on Online Social Networks. 37\u201342","author":"Viswanath Bimal"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0121002"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2614\u20132623","author":"Abdurrahman"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 22nd ACM SIGKDD. ACM, 1345\u20131354","author":"Zhang S."},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the World Wide Web Conference. ACM, 2344\u20132354","author":"Zhang S."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3450703","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T20:24:49Z","timestamp":1672604689000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3450703"}},"subtitle":["Elimination Rule-based Network Alignment"],"short-title":[],"issued":{"date-parts":[[2021,7,9]]},"references-count":38,"alternative-id":["10.1145\/3450703"],"URL":"https:\/\/doi.org\/10.1145\/3450703","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,9]]}}}