{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:29:50Z","timestamp":1750220990676,"version":"3.41.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,3,13]],"date-time":"2019-03-13T00:00:00Z","timestamp":1552435200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ARL Network Science CTA"},{"name":"Army Research Laboratory and was accomplished under Cooperative","award":["W911NF-09-2-0053"],"award-info":[{"award-number":["W911NF-09-2-0053"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2019,4,30]]},"abstract":"<jats:p>\n            Expert networks are formed by a group of expert-professionals with different specialties to collaboratively resolve specific queries posted to the network. In such networks, when a query reaches an expert who does not have sufficient expertise, this query needs to be routed to other experts for further processing until it is completely solved; therefore, query answering efficiency is sensitive to the underlying query routing mechanism being used. Among all possible query routing mechanisms, decentralized search, operating purely on each expert\u2019s local information without any knowledge of network global structure, represents the most basic and scalable routing mechanism, which is applicable to any network scenarios even in dynamic networks. However, there is still a lack of fundamental understanding of the efficiency of decentralized search in expert networks. In this regard, we investigate decentralized search by quantifying its performance under a variety of network settings. Our key findings reveal the existence of network conditions, under which decentralized search can achieve significantly short query routing paths (i.e., between\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) and\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) hops,\n            <jats:italic>n<\/jats:italic>\n            : total number of experts in the network). Based on such theoretical foundation, we further study how the unique properties of decentralized search in expert networks are related to the anecdotal small-world phenomenon. In addition, we demonstrate that decentralized search is robust against estimation errors introduced by misinterpreting the required expertise levels. The developed performance bounds, confirmed by real datasets, are able to assist in predicting network performance and designing complex expert networks.\n          <\/jats:p>","DOI":"10.1145\/3300230","type":"journal-article","created":{"date-parts":[[2019,3,14]],"date-time":"2019-03-14T17:11:58Z","timestamp":1552583518000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Performance Bounds of Decentralized Search in Expert Networks for Query Answering"],"prefix":"10.1145","volume":"13","author":[{"given":"Liang","family":"Ma","sequence":"first","affiliation":[{"name":"IBM T. J. Watson Research, Kitchawan Rd, Yorktown, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mudhakar","family":"Srivatsa","sequence":"additional","affiliation":[{"name":"IBM T. J. Watson Research, Kitchawan Rd, Yorktown, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Derya","family":"Cansever","sequence":"additional","affiliation":[{"name":"Army Research Laboratory, Adelphi, MD"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xifeng","family":"Yan","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara, Santa Barbara, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sue","family":"Kase","sequence":"additional","affiliation":[{"name":"Army Research Laboratory, Adelphi, MD"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michelle","family":"Vanni","sequence":"additional","affiliation":[{"name":"Army Research Laboratory, Adelphi, MD"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,3,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.64.046135"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1148170.1148181"},{"key":"e_1_2_1_3_1","unstructured":"Arindam Banerjee and Sugato Basu. 2008. A social query model for decentralized search. In ACM SNAKDD.  Arindam Banerjee and Sugato Basu. 2008. A social query model for decentralized search. In ACM SNAKDD."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0401033"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579310"},{"volume-title":"Convex Optimization","author":"Boyd Stephen","key":"e_1_2_1_6_1","unstructured":"Stephen Boyd and Lieven Vandenberghe . 2004. Convex Optimization . Cambridge University Press . Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Yixin Cao Lifu Huang Heng Ji Xu Chen and Juanzi Li. 2017. Bridge text and knowledge by learning multi-prototype entity mention embedding. In ACL.  Yixin Cao Lifu Huang Heng Ji Xu Chen and Juanzi Li. 2017. Bridge text and knowledge by learning multi-prototype entity mention embedding. In ACL.","DOI":"10.18653\/v1\/P17-1149"},{"volume-title":"Measuring chess experts","author":"Chassy Philippe","key":"e_1_2_1_8_1","unstructured":"Philippe Chassy and Fernand Gobet . 2011. Measuring chess experts \u2019 single-use sequence knowledge: An archival study of departure from \u2018theoretical\u2019 openings. In PloS One . Philippe Chassy and Fernand Gobet. 2011. Measuring chess experts\u2019 single-use sequence knowledge: An archival study of departure from \u2018theoretical\u2019 openings. In PloS One."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Martin Dietzfelbinger and Philipp Woelfel. 2014. Tight lower bounds for greedy routing in higher-dimensional small-world grids. In ACM-SIAM SODA.   Martin Dietzfelbinger and Philipp Woelfel. 2014. Tight lower bounds for greedy routing in higher-dimensional small-world grids. In ACM-SIAM SODA.","DOI":"10.1137\/1.9781611973402.60"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098036"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1239\/jap\/1158784938"},{"key":"e_1_2_1_12_1","unstructured":"Alberto Garcia Duran and Mathias Niepert. 2017. Learning graph representations with embedding propagation. In NIPS.   Alberto Garcia Duran and Mathias Niepert. 2017. Learning graph representations with embedding propagation. In NIPS."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939754"},{"volume-title":"Six Degrees of Separation: A Play","author":"Guare John","key":"e_1_2_1_14_1","unstructured":"John Guare . 1990. Six Degrees of Separation: A Play . Vintage Books . John Guare. 1990. Six Degrees of Separation: A Play. Vintage Books."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2638425"},{"key":"e_1_2_1_16_1","unstructured":"Will Hamilton Zhitao Ying and Jure Leskovec. 2017. Inductive representation learning on large graphs. In NIPS.   Will Hamilton Zhitao Ying and Jure Leskovec. 2017. Inductive representation learning on large graphs. In NIPS."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3018661.3018667"},{"key":"e_1_2_1_18_1","volume-title":"Kipf and Max Welling","author":"Thomas","year":"2017","unstructured":"Thomas N. Kipf and Max Welling . 2017 . Semi-supervised classification with graph convolutional networks. In ICLR. Thomas N. Kipf and Max Welling. 2017. Semi-supervised classification with graph convolutional networks. In ICLR."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1038\/35022643"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335325"},{"key":"e_1_2_1_21_1","volume-title":"International Congress of Mathematicians.","author":"Kleinberg Jon","year":"2006","unstructured":"Jon Kleinberg . 2006 . Complex networks and decentralized search algorithms . In International Congress of Mathematicians. Jon Kleinberg. 2006. Complex networks and decentralized search algorithms. In International Congress of Mathematicians."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.63"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1037\/h0029198"},{"key":"e_1_2_1_24_1","volume-title":"Zemel","author":"Li Yujia","year":"2016","unstructured":"Yujia Li , Daniel Tarlow , Marc Brockschmidt , and Richard S . Zemel . 2016 . Gated graph sequence neural networks. In ICLR. Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard S. Zemel. 2016. Gated graph sequence neural networks. In ICLR."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835897"},{"key":"e_1_2_1_26_1","first-page":"61","article-title":"The small world problem","volume":"67","author":"Milgram Stanley","year":"1967","unstructured":"Stanley Milgram . 1967 . The small world problem . Psychology Today 67 (1967), 61 -- 67 . Stanley Milgram. 1967. The small world problem. Psychology Today 67 (1967), 61--67.","journal-title":"Psychology Today"},{"key":"e_1_2_1_27_1","volume-title":"Subgraph2Vec: Learning distributed representations of rooted sub-graphs from large graphs. CoRR abs\/1606.08928","author":"Narayanan Annamalai","year":"2016","unstructured":"Annamalai Narayanan , Mahinthan Chandramohan , Lihui Chen , Yang Liu , and Santhoshkumar Saminathan . 2016. Subgraph2Vec: Learning distributed representations of rooted sub-graphs from large graphs. CoRR abs\/1606.08928 ( 2016 ). Annamalai Narayanan, Mahinthan Chandramohan, Lihui Chen, Yang Liu, and Santhoshkumar Saminathan. 2016. Subgraph2Vec: Learning distributed representations of rooted sub-graphs from large graphs. CoRR abs\/1606.08928 (2016)."},{"key":"e_1_2_1_28_1","unstructured":"Mathias Niepert Mohamed Ahmed and Konstantin Kutzkov. 2016. Learning convolutional neural networks for graphs. In ICML.   Mathias Niepert Mohamed Ahmed and Konstantin Kutzkov. 2016. Learning convolutional neural networks for graphs. In ICML."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1458082.1458232"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401964"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623722"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.2307\/2786545"},{"key":"e_1_2_1_33_1","unstructured":"Zhigang Wang and Juanzi Li. 2016. Text-enhanced representation learning for knowledge graph. In IJCAI.   Zhigang Wang and Juanzi Li. 2016. Text-enhanced representation learning for knowledge graph. In IJCAI."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"e_1_2_1_35_1","volume-title":"SSP: Semantic space projection for knowledge graph embedding with text descriptions. In AAAI.","author":"Xiao Han","year":"2017","unstructured":"Han Xiao , Minlie Huang , Lian Meng , and Xiaoyan Zhu . 2017 . SSP: Semantic space projection for knowledge graph embedding with text descriptions. In AAAI. Han Xiao, Minlie Huang, Lian Meng, and Xiaoyan Zhu. 2017. SSP: Semantic space projection for knowledge graph embedding with text descriptions. In AAAI."},{"key":"e_1_2_1_36_1","unstructured":"Ruobing Xie Zhiyuan Liu and Maosong Sun. 2016. Representation learning of knowledge graphs with hierarchical types. In IJCAI.   Ruobing Xie Zhiyuan Liu and Maosong Sun. 2016. Representation learning of knowledge graphs with hierarchical types. In IJCAI."},{"key":"e_1_2_1_37_1","unstructured":"Zhilin Yang William W. Cohen and Ruslan Salakhutdinov. 2016. Revisiting semi-supervised learning with graph embeddings. In ICML.   Zhilin Yang William W. Cohen and Ruslan Salakhutdinov. 2016. Revisiting semi-supervised learning with graph embeddings. In ICML."},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Liang Yao Yin Zhang Baogang Wei Zhe Jin Rui Zhang Yangyang Zhang and Qinfei Chen. 2017. Incorporating knowledge graph embeddings into topic modeling. In AAAI.   Liang Yao Yin Zhang Baogang Wei Zhe Jin Rui Zhang Yangyang Zhang and Qinfei Chen. 2017. Incorporating knowledge graph embeddings into topic modeling. In AAAI.","DOI":"10.1609\/aaai.v31i1.10951"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-006-0476-z"},{"key":"e_1_2_1_40_1","volume-title":"Parkes","author":"Zhang Haoqi","year":"2012","unstructured":"Haoqi Zhang , Eric Horvitz , Yiling Chen , and David C . Parkes . 2012 . Task routing for prediction tasks. In AAMAS. Haoqi Zhang, Eric Horvitz, Yiling Chen, and David C. Parkes. 2012. Task routing for prediction tasks. In AAMAS."}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3300230","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3300230","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:25:23Z","timestamp":1750206323000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3300230"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,13]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,4,30]]}},"alternative-id":["10.1145\/3300230"],"URL":"https:\/\/doi.org\/10.1145\/3300230","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2019,3,13]]},"assertion":[{"value":"2016-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-03-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}