{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:28:34Z","timestamp":1750307314174,"version":"3.41.0"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2011,8,1]],"date-time":"2011-08-01T00:00:00Z","timestamp":1312156800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["W7405-ENG-48"],"award-info":[{"award-number":["W7405-ENG-48"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["IIS-0326249"],"award-info":[{"award-number":["IIS-0326249"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2011,8]]},"abstract":"<jats:p>The ability to discover low-cost paths in networks has practical consequences for knowledge discovery and social network analysis tasks. Many analytic techniques for networks require finding low-cost paths, but exact methods for search become prohibitive for large networks, and data sets are steadily increasing in size. Short paths can be found efficiently by utilizing an index of network structure, which estimates network distances and enables rapid discovery of short paths. Through experiments on synthetic networks, we demonstrate that one such novel network structure index based on the shortest-path tree outperforms other previously proposed indices. We also show that it generalizes across arbitrarily weighted networks of various structures and densities, provides accurate estimates of distance, and has efficient time and space complexity. We present results on real data sets for several applications, including navigation, diameter estimation, centrality computation, and clustering---all made efficient by virtue of the network structure index.<\/jats:p>","DOI":"10.1145\/1993077.1993079","type":"journal-article","created":{"date-parts":[[2011,8,10]],"date-time":"2011-08-10T16:16:22Z","timestamp":1312992982000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Indexing Network Structure with Shortest-Path Trees"],"prefix":"10.1145","volume":"5","author":[{"given":"Marc","family":"Maier","sequence":"first","affiliation":[{"name":"University of Massachusetts, Amherst"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthew","family":"Rattigan","sequence":"additional","affiliation":[{"name":"University of Massachusetts, Amherst"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Jensen","sequence":"additional","affiliation":[{"name":"University of Massachusetts, Amherst"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.64.046135"},{"volume-title":"Proceedings of the 5th International Conference on Algorithms and Models for the Web-Graph. 187--194","author":"Arcaute E.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0400087101"},{"volume-title":"Proceedings of the 4th Latin American Symposium on Theoretical Information (LATIN\u201900)","author":"Bender M.","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.2001.9990249"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218127407018403"},{"key":"e_1_2_1_7_1","unstructured":"Chow E. 2004. A graph search heuristic for shortest distance paths. Tech. rep. UCRL-JRNL-202894 Lawrence Livermore National Laboratory. Chow E. 2004. A graph search heuristic for shortest distance paths. Tech. rep. UCRL-JRNL-202894 Lawrence Livermore National Laboratory."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1117"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015467.1015471"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"volume-title":"Proceedings of the Annual Symposium on Foundations of Computer Science 37","author":"Dor D.","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","article-title":"On random graphs","volume":"6","author":"Erdos P.","year":"1959","journal-title":"Publ. Math. Debrecen"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014068"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281293"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129093"},{"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.1016\/0378-8733(78)90021-7"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281226"},{"volume-title":"Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 210--219","author":"Gavoille C.","key":"e_1_2_1_19_1"},{"volume-title":"Proceedings of the 10th Workshop on Algorithm Engineering and Experiments. SIAM.","author":"Geisberger R.","key":"e_1_2_1_20_1"},{"volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. 156--165","author":"Goldberg A. V.","key":"e_1_2_1_21_1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(199909)34:2<88::AID-NET2>3.0.CO;2-1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1038\/35022643"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335325"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568322"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1297332.1297336"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(85)90084-0"},{"volume-title":"Proceedings of 23rd IEEE Conference on Computer Communications.","author":"Krioukov D.","key":"e_1_2_1_29_1"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_44"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146847.1146849"},{"key":"e_1_2_1_32_1","unstructured":"Leskovec J. 2008. Dynamics of large networks. Ph.D. thesis Carnegie Mellon University. Leskovec J. 2008. Dynamics of large networks. Ph.D. thesis Carnegie Mellon University."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"volume-title":"Proceedings of the 5th ACM IMC Internet Measurement Conference. 125--138","author":"Lua E. K.","key":"e_1_2_1_34_1"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1028788.1028827"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.056131"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1140\/epjb\/e2004-00124-y"},{"volume-title":"Proceedings of the 21st IEEE Conference on Computer Communications.","author":"Ng T.","key":"e_1_2_1_38_1"},{"volume-title":"Proceedings of the International Workshop on Peer-To-Peer Systems.","author":"Pias M.","key":"e_1_2_1_39_1"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1209\/epl\/i2005-10414-6"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1645953.1646063"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/312129.312188"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150443"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273496.1273595"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/11558590_2"},{"volume-title":"Artificial Intelligence: A Modern Approach","year":"1995","author":"Russell S.","key":"e_1_2_1_46_1"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2004.838597"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0800497105"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/3271139.3271275"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/948205.948223"},{"volume-title":"Proceedings of the 5th Passive and Active Measurement Workshop.","author":"Tang L.","key":"e_1_2_1_51_1"},{"volume-title":"Proceedings of the IEEE Global Telecommunications Conference 3.","author":"Tauro S.","key":"e_1_2_1_52_1"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044732"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.2307\/2786545"},{"volume-title":"Proceedings of the 16th International Joint Conference on Artificial Intelligence. 1172--1177","year":"1999","author":"Walsh T.","key":"e_1_2_1_55_1"},{"key":"e_1_2_1_56_1","doi-asserted-by":"crossref","unstructured":"Wasserman S. and Faust K. 1994. Social Network Analysis: Methods and Applications. Cambridge University Press. Wasserman S. and Faust K. 1994. Social Network Analysis: Methods and Applications . Cambridge University Press.","DOI":"10.1017\/CBO9780511815478"},{"key":"e_1_2_1_57_1","doi-asserted-by":"crossref","unstructured":"Watts D. and Strogatz S. 1998. Collective dynamics of \u2018small-world\u2019 networks. Nature 393 6684 409--10. Watts D. and Strogatz S. 1998. Collective dynamics of \u2018small-world\u2019 networks. Nature 393 6684 409--10.","DOI":"10.1038\/30918"},{"key":"e_1_2_1_58_1","doi-asserted-by":"crossref","unstructured":"Watts D. Dodds P. and Newman M. 2002. Identity and search in social networks. Science 296 5571 1302--1305. Watts D. Dodds P. and Newman M. 2002. Identity and search in social networks. Science 296 5571 1302--1305.","DOI":"10.1126\/science.1070120"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/1080091.1080103"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.5555\/647911.740642"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1993077.1993079","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1993077.1993079","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:05:45Z","timestamp":1750244745000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1993077.1993079"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,8]]},"references-count":60,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,8]]}},"alternative-id":["10.1145\/1993077.1993079"],"URL":"https:\/\/doi.org\/10.1145\/1993077.1993079","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2011,8]]},"assertion":[{"value":"2009-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}