{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T17:16:36Z","timestamp":1767374196169},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2016,5]]},"abstract":"<jats:p>\n            In this paper, we leverage the concept of the\n            <jats:italic>metric backbone<\/jats:italic>\n            to improve the efficiency of large-scale graph analytics. The metric backbone is the minimum subgraph that preserves the shortest paths of a weighted graph. We use the metric backbone in place of the original graph to compute various graph metrics exactly or with good approximation. By computing on a smaller graph, we improve the performance of graph analytics applications on two different systems, a batch graph processing system and a graph database.\n          <\/jats:p>\n          <jats:p>\n            Further, we provide an algorithm for the computation of the metric backbone on large graphs. While one can compute the metric backbone by solving the all-pairs-shortest-paths problem, this approach incurs prohibitive time and space complexity for big graphs. Instead, we propose a heuristic that makes computing the metric backbone practical even for large graphs. Additionally, we analyze several real datasets of different sizes and domains and we show that we can approximate the metric backbone by removing only first-order\n            <jats:italic>semi-metric<\/jats:italic>\n            edges; edges for which a shorter two-hop path exists.\n          <\/jats:p>\n          <jats:p>We provide a distributed implementation of our algorithm and apply it in large scale scenarios. We evaluate our algorithm using a variety of real graphs, including a Facebook social network subgraph of ~50 billion edges. We measure the impact of using the metric backbone on runtime performance in two graph management systems. We achieve query speedups of up to 6.7x in the Neo4j commercial graph database and job speedups of up to 6x in the Giraph graph processing system.<\/jats:p>","DOI":"10.14778\/2947618.2947623","type":"journal-article","created":{"date-parts":[[2016,7,26]],"date-time":"2016-07-26T13:28:39Z","timestamp":1469539719000},"page":"672-683","source":"Crossref","is-referenced-by-count":19,"title":["The shortest path is not always a straight line"],"prefix":"10.14778","volume":"9","author":[{"given":"Vasiliki","family":"Kalavri","sequence":"first","affiliation":[{"name":"KTH Royal Institute of Technology, Stockholm, Sweden"}]},{"given":"Tiago","family":"Simas","sequence":"additional","affiliation":[{"name":"Telefonica Research, Barcelona, Spain"}]},{"given":"Dionysios","family":"Logothetis","sequence":"additional","affiliation":[{"name":"Facebook, Menlo Park, CA"}]}],"member":"320","published-online":{"date-parts":[[2016,5]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Apache Giraph Project. http:\/\/giraph.apache.org\/.  Apache Giraph Project. http:\/\/giraph.apache.org\/."},{"key":"e_1_2_1_2_1","unstructured":"The movielens dataset. http:\/\/grouplens.org\/datasets\/movielens.  The movielens dataset. http:\/\/grouplens.org\/datasets\/movielens."},{"key":"e_1_2_1_3_1","unstructured":"Neo4j Graph Database. http:\/\/neo4j.com.  Neo4j Graph Database. http:\/\/neo4j.com."},{"key":"e_1_2_1_4_1","unstructured":"The Tuenti Social Network. http:\/\/www.tuenti.com.  The Tuenti Social Network. http:\/\/www.tuenti.com."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-8733(03)00009-1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201008"},{"issue":"6749","key":"e_1_2_1_7_1","first-page":"130","article-title":"Internet","volume":"401","author":"Albert R.","year":"1999","unstructured":"R. Albert , Internet : Diameter of the World-Wide Web. Nature , 401 ( 6749 ): 130 -- 131 , Sept. 1999 . R. Albert, et al. Internet: Diameter of the World-Wide Web. Nature, 401(6749):130--131, Sept. 1999.","journal-title":"Diameter of the World-Wide Web. Nature"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150412"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0400087101"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554819"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/P2P.2014.6934314"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963488"},{"key":"e_1_2_1_13_1","first-page":"621","volume-title":"In-Core Computation of Geometric Centralities with HyperBall: A Hundred Billion Nodes and Beyond. In IEEE International Conference on Data Mining Workshops","author":"Boldi P.","year":"2013","unstructured":"P. Boldi In-Core Computation of Geometric Centralities with HyperBall: A Hundred Billion Nodes and Beyond. In IEEE International Conference on Data Mining Workshops , pages 621 -- 628 . IEEE, Dec. 2013 . P. Boldi et al. In-Core Computation of Geometric Centralities with HyperBall: A Hundred Billion Nodes and Beyond. In IEEE International Conference on Data Mining Workshops, pages 621--628. IEEE, Dec. 2013."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.2001.9990249"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.02.023"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557049"},{"key":"e_1_2_1_17_1","volume-title":"Connected: The Surprising Power of Our Social Networks and how They Shape Our Lives","author":"Christakis N. A.","year":"2009","unstructured":"N. A. Christakis Connected: The Surprising Power of Our Social Networks and how They Shape Our Lives . 2009 . N. A. Christakis et al. Connected: The Surprising Power of Our Social Networks and how They Shape Our Lives. 2009."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020513"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1038\/nphys560"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.10.002"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2013.107"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213855"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218127407018439"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1093\/sf\/62.1.54"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993647"},{"key":"e_1_2_1_27_1","volume-title":"USENIX Symposium on Operating Systems Design and Implementation","author":"Gonzalez J. E.","year":"2014","unstructured":"J. E. Gonzalez , : Graph Processing in a Distributed Dataflow Framework . In USENIX Symposium on Operating Systems Design and Implementation , 2014 . J. E. Gonzalez, et al. GraphX: Graph Processing in a Distributed Dataflow Framework. In USENIX Symposium on Operating Systems Design and Implementation, 2014."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1086\/225469"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0207033"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1469-8137.1912.tb05611.x"},{"key":"e_1_2_1_31_1","series-title":"SIAM International Conference on Data Mining","volume-title":"Centralities in Large Networks: Algorithms and Observations","author":"Kang U.","unstructured":"U. Kang , Centralities in Large Networks: Algorithms and Observations . SIAM International Conference on Data Mining . U. Kang, et al. Centralities in Large Networks: Algorithms and Observations. SIAM International Conference on Data Mining."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.07.017"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.79.066107"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661829.2661862"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_38_1","volume-title":"Advances in Neural Information Processing Systems","author":"McAuley J.","year":"2012","unstructured":"J. McAuley Learning to Discover Social Circles in Ego Networks . In Advances in Neural Information Processing Systems , 2012 . J. McAuley et al. Learning to Discover Social Circles in Ego Networks. In Advances in Neural Information Processing Systems, 2012."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/321526.321534"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376661"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2011.07.001"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM.2012.254"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/WI.2005.106"},{"key":"e_1_2_1_45_1","first-page":"02","volume-title":"Internal Report of Advanced Knowledge Integration In Assessing Terrorist Threats LDRD-DR Network Analysis Component. LAUR","author":"Rocha L. M.","year":"2002","unstructured":"L. M. Rocha . Proximity and semi-metric analysis of social networks . In Internal Report of Advanced Knowledge Integration In Assessing Terrorist Threats LDRD-DR Network Analysis Component. LAUR , pages 02 -- 6557 , 2002 . L. M. Rocha. Proximity and semi-metric analysis of social networks. In Internal Report of Advanced Knowledge Integration In Assessing Terrorist Threats LDRD-DR Network Analysis Component. LAUR, pages 02--6557, 2002."},{"key":"e_1_2_1_46_1","first-page":"137","article-title":"Semi-metric behavior in document networks and its application to recommendation systems","volume":"83","author":"Rocha L. M.","year":"2002","unstructured":"L. M. Rocha . Semi-metric behavior in document networks and its application to recommendation systems . Soft Computing Agents: A New Perspective for Dynamic Information Systems , 83 : 137 , 2002 . L. M. Rocha. Semi-metric behavior in document networks and its application to recommendation systems. Soft Computing Agents: A New Perspective for Dynamic Information Systems, 83:137, 2002.","journal-title":"Soft Computing Agents: A New Perspective for Dynamic Information Systems"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/11427186_54"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/WI-IAT.2012.245"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1017\/nws.2015.11"},{"key":"e_1_2_1_50_1","volume-title":"Nature","author":"Watts D.","year":"1998","unstructured":"D. Watts Collective dynamics of 'small-world' networks . Nature , 1998 . D. Watts et al. Collective dynamics of 'small-world' networks. Nature, 1998."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1519065.1519089"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.138"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920887"},{"key":"e_1_2_1_54_1","volume-title":"The Influence of Indirect Ties on Social Network Dynamics. In International Conference on Social Informatics","author":"Zuo X.","year":"2014","unstructured":"X. Zuo , The Influence of Indirect Ties on Social Network Dynamics. In International Conference on Social Informatics , Nov. 2014 . X. Zuo, et al. The Influence of Indirect Ties on Social Network Dynamics. In International Conference on Social Informatics, Nov. 2014."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2947618.2947623","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:33:29Z","timestamp":1672220009000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2947618.2947623"}},"subtitle":["leveraging semi-metricity in graph analysis"],"short-title":[],"issued":{"date-parts":[[2016,5]]},"references-count":53,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2016,5]]}},"alternative-id":["10.14778\/2947618.2947623"],"URL":"https:\/\/doi.org\/10.14778\/2947618.2947623","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2016,5]]}}}