{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,17]],"date-time":"2026-04-17T02:55:23Z","timestamp":1776394523481,"version":"3.51.2"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,10,12]],"date-time":"2015-10-12T00:00:00Z","timestamp":1444608000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2015,10,26]]},"abstract":"<jats:p>\n            Small changes on the structure of a graph can have a dramatic effect on its connectivity. While in the traditional graph theory, the focus is on well-defined properties of graph connectivity, such as biconnectivity, in the context of a\n            <jats:italic>social graph<\/jats:italic>\n            , connectivity is typically manifested by its ability to carry on\n            <jats:italic>social processes<\/jats:italic>\n            . In this paper, we consider the problem of adding a small set of nonexisting edges (\n            <jats:italic>shortcuts<\/jats:italic>\n            ) in a social graph with the main objective of minimizing its\n            <jats:italic>characteristic path length<\/jats:italic>\n            . This property determines the average distance between pairs of vertices and essentially controls how broadly information can propagate through a network. We formally define the problem of interest, characterize its hardness and propose a novel method,\n            <jats:italic>path screening<\/jats:italic>\n            , which quickly identifies important shortcuts to guide the augmentation of the graph. We devise a sampling-based variant of our method that can scale up the computation in larger graphs. The claims of our methods are formally validated. Through experiments on real and synthetic data, we demonstrate that our methods are\n            <jats:italic>a multitude of times<\/jats:italic>\n            faster than standard approaches, their accuracy outperforms sensible baselines and they can ease the spread of information in a network, for a varying range of conditions.\n          <\/jats:p>","DOI":"10.1145\/2757281","type":"journal-article","created":{"date-parts":[[2015,10,13]],"date-time":"2015-10-13T22:31:00Z","timestamp":1444775460000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":32,"title":["Refining Social Graph Connectivity via Shortcut Edge Addition"],"prefix":"10.1145","volume":"10","author":[{"given":"Manos","family":"Papagelis","sequence":"first","affiliation":[{"name":"University of Toronto, Toronto ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,10,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579166"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90083-3"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.20"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1935826.1935914"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Albert-L\u00e1szl\u00f3 Barab\u00e1si and R\u00e9ka Albert. 1999. Emergence of scaling in random networks. Science 286 5439 509--512.  Albert-L\u00e1szl\u00f3 Barab\u00e1si and R\u00e9ka Albert. 1999. Emergence of scaling in random networks. Science 286 5439 509--512.","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkg340"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/358690.358717"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187908"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Jeffrey Dean and Sanjay Ghemawat. 2004. MapReduce: simplified data processing on large clusters. In OSDI. 107--113.   Jeffrey Dean and Sanjay Ghemawat. 2004. MapReduce: simplified data processing on large clusters. In OSDI. 107--113.","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13731-0_39"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"D. Easley and J. Kleinberg. 2010. Networks Crowds and Markets: Reasoning About a Highly Connected World. Cambridge University Press Cambridge U.K.   D. Easley and J. Kleinberg. 2010. Networks Crowds and Markets: Reasoning About a Highly Connected World. Cambridge University Press Cambridge U.K.","DOI":"10.1017\/CBO9780511761942"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205044"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.55"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210019"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"e_1_2_1_19_1","volume-title":"Goldberg and Chris Harrelson","author":"Andrew","year":"2005","unstructured":"Andrew V. Goldberg and Chris Harrelson . 2005 . Computing the shortest path: A search meets graph theory. In SODA. 156--165. Andrew V. Goldberg and Chris Harrelson. 2005. Computing the shortest path: A search meets graph theory. In SODA. 156--165."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218077"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/321992.321993"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644893.1644912"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Michael Kapralov Ian Post and Jan Vondrak. 2013. Online submodular welfare maximization: Greedy is optimal. In SODA. 1216--1225.   Michael Kapralov Ian Post and Jan Vondrak. 2013. Online submodular welfare maximization: Greedy is optimal. In SODA. 1216--1225.","DOI":"10.1137\/1.9781611973105.88"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1010"},{"key":"e_1_2_1_27_1","volume-title":"Conductance and rapidly mixing Markov chains. Technical report","author":"King Jamie","year":"2003","unstructured":"Jamie King . 2003. Conductance and rapidly mixing Markov chains. Technical report , University of Waterloo , 2003 . Jamie King. 2003. Conductance and rapidly mixing Markov chains. Technical report, University of Waterloo, 2003."},{"key":"e_1_2_1_28_1","volume-title":"Algorithmic Game Theory, Noam Nisan, Tim Roughgarden, \u00c9va Tardos","author":"Kleinberg Jon","unstructured":"Jon Kleinberg . 2007. Cascading behavior in networks: Algorithmic and economic issues . In Algorithmic Game Theory, Noam Nisan, Tim Roughgarden, \u00c9va Tardos , and Vijay Vazirani (Eds.). Cambridge University Press , Cambridge, U.K. Jon Kleinberg. 2007. Cascading behavior in networks: Algorithmic and economic issues. In Algorithmic Game Theory, Noam Nisan, Tim Roughgarden, \u00c9va Tardos, and Vijay Vazirani (Eds.). Cambridge University Press, Cambridge, U.K."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.70"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400774"},{"key":"e_1_2_1_31_1","unstructured":"Konstantina Lazaridou Konstantinos Semertzidis Evaggelia Pitoura and Panayiotis Tsaparas. 2015. Identifying converging pairs of nodes on a budget. EDBT. 313--324.  Konstantina Lazaridou Konstantinos Semertzidis Evaggelia Pitoura and Panayiotis Tsaparas. 2015. Identifying converging pairs of nodes on a budget. EDBT. 313--324."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150479"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281239"},{"key":"e_1_2_1_34_1","volume-title":"SNAP Datasets: Stanford Large Network Dataset Collection. (June","author":"Leskovec Jure","year":"2014","unstructured":"Jure Leskovec and Andrej Krevl . 2014. SNAP Datasets: Stanford Large Network Dataset Collection. (June 2014 ). Retrieved from http:\/\/snap.stanford.edu\/data. Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. (June 2014). Retrieved from http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367591"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/1241540.1241551"},{"key":"e_1_2_1_37_1","volume-title":"Paul erdos is eighty 2, 1","author":"Lov\u00e1sz L\u00e1szl\u00f3","year":"1993","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz . 1993. Random walks on graphs: a survey. Combinatorics , Paul erdos is eighty 2, 1 ( 1993 ), 1--46. L\u00e1szl\u00f3 Lov\u00e1sz. 1993. Random walks on graphs: a survey. Combinatorics, Paul erdos is eighty 2, 1 (1993), 1--46."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00265-003-0651-y"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-10-1-96-115"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_21"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1879141.1879191"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-937X.00121"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2004.11.009"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.74.036104"},{"key":"e_1_2_1_46_1","unstructured":"Zeev Nutov. 2005. Approximating connectivity augmentation problems. In SODA. 176--185.   Zeev Nutov. 2005. Approximating connectivity augmentation problems. In SODA. 176--185."},{"key":"e_1_2_1_47_1","volume-title":"Papadimitriou and Kenneth Steiglitz","author":"Christos","year":"1998","unstructured":"Christos H. Papadimitriou and Kenneth Steiglitz . 1998 . Combinatorial Optimization : Algorithms and Complexity. Courier Corporation , Mineola, New York. Christos H. Papadimitriou and Kenneth Steiglitz. 1998. Combinatorial Optimization: Algorithms and Complexity. Courier Corporation, Mineola, New York."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063952"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.254"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974010.4"},{"key":"e_1_2_1_51_1","volume-title":"IJCAI03 Workshop on Learning Statistical Models from Relational Data. 109--115","author":"Popescul Alexandrin","unstructured":"Alexandrin Popescul , Rin Popescul , and Lyle H. Ungar . 2003. Statistical relational learning for link prediction . In IJCAI03 Workshop on Learning Statistical Models from Relational Data. 109--115 . Alexandrin Popescul, Rin Popescul, and Lyle H. Ungar. 2003. Statistical relational learning for link prediction. In IJCAI03 Workshop on Learning Statistical Models from Relational Data. 109--115."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2012.253"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775057"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSST.2010.5496972"},{"key":"e_1_2_1_55_1","volume-title":"Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow","author":"Sinclair Alistair","unstructured":"Alistair Sinclair . 1992. Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow . Springer , New York . Alistair Sinclair. 1992. Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow. Springer, New York."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1871437.1871514"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2396795"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374389"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544873"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2757281","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2757281","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:16:27Z","timestamp":1750227387000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2757281"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10,12]]},"references-count":59,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,10,26]]}},"alternative-id":["10.1145\/2757281"],"URL":"https:\/\/doi.org\/10.1145\/2757281","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,10,12]]},"assertion":[{"value":"2014-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-10-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}