{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,2]],"date-time":"2023-01-02T02:26:46Z","timestamp":1672626406097},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,8]]},"abstract":"\n Given two sets of vertices in a graph, it is often of a great interest to find out how these vertices are connected, especially to identify the vertices of high prominence defined on the topological structure. In this work, we formally define a\n \n V<\/jats:bold>\n ertex\n S<\/jats:bold>\n et\n B<\/jats:bold>\n onding\n <\/jats:italic>\n query (shorted as VSB), which returns a minimum set of vertices with the maximum importance\n w.r.t<\/jats:italic>\n total betweenness and shortest path reachability in connecting two sets of input vertices. We find that such a kind of query is representative and could be widely applied in many real world scenarios, e.g., logistic planning, social community bonding and etc. Challenges are that many of such applications are constructed on graphs that are too large to fit in single server, and the VSB query evaluation turns to be NP-hard. To cope with the scalability issue and return the near optimal result in almost real time, we propose a generic solution framework on a shared nothing distributed environment. With the development of two novel techniques, guided graph exploration and betweenness ranking on exploration, we are able to efficiently evaluate queries for error bounded results with bounded space cost. We demonstrate the effectiveness of our solution with extensive experiments over both real and synthetic large graphs on the Google's Cloud platform. Comparing to the exploration only baseline method, our method achieves several times of speedup.\n <\/jats:p>","DOI":"10.14778\/2824032.2824041","type":"journal-article","created":{"date-parts":[[2015,9,16]],"date-time":"2015-09-16T12:18:17Z","timestamp":1442405897000},"page":"1418-1429","source":"Crossref","is-referenced-by-count":3,"title":["Bonding vertex sets over distributed graph"],"prefix":"10.14778","volume":"8","author":[{"given":"Xiaofei","family":"Zhang","sequence":"first","affiliation":[{"name":"HKUST"}]},{"given":"Hong","family":"Cheng","sequence":"additional","affiliation":[{"name":"CUHK"}]},{"given":"Lei","family":"Chen","sequence":"additional","affiliation":[{"name":"HKUST"}]}],"member":"320","published-online":{"date-parts":[[2015,8]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"1","volume-title":"Proceedings of the 4th Workshop on Social Network Systems","author":"Alahakoon T.","year":"2011","unstructured":"T. Alahakoon , R. Tripathi , N. Kourtellis , R. Simha , and A. Iamnitchi . K-path centrality: a new centrality measure in social networks . In Proceedings of the 4th Workshop on Social Network Systems , page 1 , 2011 . 10.1145\/1989656.1989657 T. Alahakoon, R. Tripathi, N. Kourtellis, R. Simha, and A. Iamnitchi. K-path centrality: a new centrality measure in social networks. In Proceedings of the 4th Workshop on Social Network Systems, page 1, 2011. 10.1145\/1989656.1989657"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480103433409"},{"key":"e_1_2_1_3_1","first-page":"124","volume-title":"WAW","author":"Bader D. A.","year":"2007","unstructured":"D. A. Bader , S. Kintali , K. Madduri , and M. Mihail . Approximating betweenness centrality . In WAW , pages 124 -- 137 , 2007 . D. A. Bader, S. Kintali, K. Madduri, and M. Mihail. Approximating betweenness centrality. In WAW, pages 124--137, 2007."},{"key":"e_1_2_1_4_1","first-page":"539","volume-title":"ICPP","author":"Bader D. A.","year":"2006","unstructured":"D. A. Bader and K. Madduri . Parallel algorithms for evaluating centrality indices in real-world networks . In ICPP , pages 539 -- 550 , 2006 . 10.1109\/ICPP.2006.57 D. A. Bader and K. Madduri. Parallel algorithms for evaluating centrality indices in real-world networks. In ICPP, pages 539--550, 2006. 10.1109\/ICPP.2006.57"},{"key":"e_1_2_1_5_1","first-page":"450","volume-title":"ASONAM","author":"Baglioni M.","year":"2012","unstructured":"M. Baglioni , F. Geraci , M. Pellegrini , and E. Lastres . Fast exact computation of betweenness centrality in social networks . In ASONAM , pages 450 -- 456 , 2012 . 10.1109\/ASONAM.2012.79 M. Baglioni, F. Geraci, M. Pellegrini, and E. Lastres. Fast exact computation of betweenness centrality in social networks. In ASONAM, pages 450--456, 2012. 10.1109\/ASONAM.2012.79"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1080\/0022250X.2001.9990249","article-title":"A faster algorithm for betweenness centrality","volume":"25","author":"Brandes U.","year":"2001","unstructured":"U. Brandes . A faster algorithm for betweenness centrality . Journal of Mathematical Sociology , 25 : 163 -- 177 , 2001 . U. Brandes. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25: 163--177, 2001.","journal-title":"Journal of Mathematical Sociology"},{"issue":"7","key":"e_1_2_1_7_1","doi-asserted-by":"crossref","first-page":"2303","DOI":"10.1142\/S0218127407018403","article-title":"Centrality estimation in large networks","volume":"17","author":"Brandes U.","year":"2007","unstructured":"U. Brandes and C. Pich . Centrality estimation in large networks . I. J. Bifurcation and Chaos , 17 ( 7 ): 2303 -- 2318 , 2007 . U. Brandes and C. Pich. Centrality estimation in large networks. I. J. Bifurcation and Chaos, 17(7):2303--2318, 2007.","journal-title":"I. J. Bifurcation and Chaos"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1504\/IJWBC.2010.033750"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735471.2735477"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"A. Bulu and J. R. Gilbert. The combinatorial blas: design implementation and applications. IJHPCA (4):496--509. 10.1177\/1094342011403516 A. Bulu and J. R. Gilbert. The combinatorial blas: design implementation and applications. IJHPCA (4):496--509. 10.1177\/1094342011403516","DOI":"10.1177\/1094342011403516"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1007\/3-540-37795-6_19","volume-title":"Future directions in distributed computing","author":"Castro M.","year":"2003","unstructured":"M. Castro and et. al. Future directions in distributed computing . chapter Topology-aware Routing in Structured Peer-to-peer Overlay Networks, pages 103 -- 107 . Springer-Verlag , Berlin, Heidelberg , 2003 . M. Castro and et. al. Future directions in distributed computing. chapter Topology-aware Routing in Structured Peer-to-peer Overlay Networks, pages 103--107. Springer-Verlag, Berlin, Heidelberg, 2003."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403098"},{"key":"e_1_2_1_13_1","first-page":"688","volume-title":"IPDPS","author":"Cong G.","year":"2011","unstructured":"G. Cong and K. Makarychev . Optimizing large-scale graph analysis on a multi-threaded, multi-core platform . In IPDPS , pages 688 -- 697 , 2011 . 10.1109\/IPDPS.2011.393 G. Cong and K. Makarychev. Optimizing large-scale graph analysis on a multi-threaded, multi-core platform. In IPDPS, pages 688--697, 2011. 10.1109\/IPDPS.2011.393"},{"key":"e_1_2_1_14_1","volume-title":"The igraph software package for complex network research","author":"Csardi G.","year":"2006","unstructured":"G. Csardi and T. Nepusz . The igraph software package for complex network research . 2006 . G. Csardi and T. Nepusz. The igraph software package for complex network research. 2006."},{"key":"e_1_2_1_15_1","first-page":"997","volume-title":"MIPRO","author":"Despalatovic L.","year":"2014","unstructured":"L. Despalatovic , T. Vojkovic , and D. Vukicevic . Community structure in networks: Girvan-newman algorithm improvement . In MIPRO , Opatija, Croatia , May 26-30, 2014 , pages 997 -- 1002 . L. Despalatovic, T. Vojkovic, and D. Vukicevic. Community structure in networks: Girvan-newman algorithm improvement. In MIPRO, Opatija, Croatia, May 26-30, 2014, pages 997--1002."},{"key":"e_1_2_1_16_1","first-page":"1","volume-title":"HiPC","author":"Edmonds N.","year":"2010","unstructured":"N. Edmonds and et. al. A space-efficient parallel algorithm for computing betweenness centrality in distributed memory . In HiPC , pages 1 -- 10 , 2010 . N. Edmonds and et. al. A space-efficient parallel algorithm for computing betweenness centrality in distributed memory. In HiPC, pages 1--10, 2010."},{"key":"e_1_2_1_17_1","first-page":"301","volume-title":"SIGMOD","author":"Fan W.","year":"2014","unstructured":"W. Fan , X. Wang , and Y. Wu . Querying big graphs within bounded resources . In SIGMOD , pages 301 -- 312 , 2014 . 10.1145\/2588555.2610513 W. Fan, X. Wang, and Y. Wu. Querying big graphs within bounded resources. In SIGMOD, pages 301--312, 2014. 10.1145\/2588555.2610513"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732951.2732963"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.05.002"},{"key":"e_1_2_1_20_1","first-page":"90","volume-title":"ALENEX","author":"Geisberger R.","year":"2008","unstructured":"R. Geisberger , P. Sanders , and D. Schultes . Better approximation of betweenness centrality . In ALENEX , pages 90 -- 100 , 2008 . R. Geisberger, P. Sanders, and D. Schultes. Better approximation of betweenness centrality. In ALENEX, pages 90--100, 2008."},{"key":"e_1_2_1_21_1","first-page":"8271","volume-title":"In Proceedings of the National Academy of Science USA","author":"Girvan M.","year":"2002","unstructured":"M. Girvan and M. E. J. Newman . Community structure in social and biological network . In In Proceedings of the National Academy of Science USA , pages 99: 8271 -- 8276 , 2002 . M. Girvan and M. E. J. Newman. Community structure in social and biological network. In In Proceedings of the National Academy of Science USA, pages 99: 8271--8276, 2002."},{"key":"e_1_2_1_22_1","first-page":"599","volume-title":"OSDI","author":"Gonzalez J. E.","year":"2014","unstructured":"J. E. Gonzalez and et. al. Graphx : Graph processing in a distributed dataflow framework . In OSDI , pages 599 -- 613 , 2014 . J. E. Gonzalez and et. al. Graphx: Graph processing in a distributed dataflow framework. In OSDI, pages 599--613, 2014."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2503792.2503797"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","first-page":"821","DOI":"10.1145\/2487788.2488055","volume-title":"WWW, Companion Volume","author":"Guimar\u00e3es A.","year":"2013","unstructured":"A. Guimar\u00e3es , A. B. Vieira , A. P. C. da Silva , and A. Ziviani . Fast centrality-driven diffusion in dynamic networks . In WWW, Companion Volume , pages 821 -- 828 , 2013 . A. Guimar\u00e3es, A. B. Vieira, A. P. C. da Silva, and A. Ziviani. Fast centrality-driven diffusion in dynamic networks. In WWW, Companion Volume, pages 821--828, 2013."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the Third Annual ACM\/SIGACT-SIAM Symposium on Discrete Algorithms, 27--29","author":"Hao J.","year":"1992","unstructured":"J. Hao and J. B. Orlin . A faster algorithm for finding the minimum cut in a graph . In Proceedings of the Third Annual ACM\/SIGACT-SIAM Symposium on Discrete Algorithms, 27--29 January 1992 , Orlando, Florida., pages 165--174 , 1992. J. Hao and J. B. Orlin. A faster algorithm for finding the minimum cut in a graph. In Proceedings of the Third Annual ACM\/SIGACT-SIAM Symposium on Discrete Algorithms, 27--29 January 1992, Orlando, Florida., pages 165--174, 1992."},{"key":"e_1_2_1_26_1","first-page":"1","volume-title":"IPDPS","author":"Jin S.","year":"2010","unstructured":"S. Jin , Z. Huang , Y. Chen , D. G. Chavarr\u00eda-Miranda , J. Feo , and P. C. Wong . A novel application of parallel betweenness centrality to power grid contingency analysis . In IPDPS , pages 1 -- 7 , 2010 . S. Jin, Z. Huang, Y. Chen, D. G. Chavarr\u00eda-Miranda, J. Feo, and P. C. Wong. A novel application of parallel betweenness centrality to power grid contingency analysis. In IPDPS, pages 1--7, 2010."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_2_1_28_1","first-page":"137","volume-title":"SIGKDD","author":"Kempe D.","year":"2003","unstructured":"D. Kempe , J. M. Kleinberg , and \u00c9. Tardos. Maximizing the spread of influence through a social network . In SIGKDD , pages 137 -- 146 , 2003 . 10.1145\/956750.956769 D. Kempe, J. M. Kleinberg, and \u00c9. Tardos. Maximizing the spread of influence through a social network. In SIGKDD, pages 137--146, 2003. 10.1145\/956750.956769"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.70"},{"key":"e_1_2_1_30_1","first-page":"591","volume-title":"WWW","author":"Kwak H.","year":"2010","unstructured":"H. Kwak , C. Lee , H. Park , and S. B. Moon . What is twitter, a social network or a news media ? In WWW , pages 591 -- 600 , 2010 . 10.1145\/1772690.1772751 H. Kwak, C. Lee, H. Park, and S. B. Moon. What is twitter, a social network or a news media? In WWW, pages 591--600, 2010. 10.1145\/1772690.1772751"},{"key":"e_1_2_1_31_1","first-page":"340","volume-title":"UAI","author":"Low Y.","year":"2010","unstructured":"Y. Low and et. al. Graphlab : A new framework for parallel machine learning . In UAI , pages 340 -- 349 , 2010 . Y. Low and et. al. Graphlab: A new framework for parallel machine learning. In UAI, pages 340--349, 2010."},{"key":"e_1_2_1_32_1","first-page":"1","volume-title":"IPDPS","author":"Madduri K.","year":"2009","unstructured":"K. Madduri and et. al. A faster parallel algorithm and efficient multithreaded implementations for evaluating betweenness centrality on massive datasets . In IPDPS , pages 1 -- 8 , 2009 . 10.1109\/IPDPS.2009.5161100 K. Madduri and et. al. A faster parallel algorithm and efficient multithreaded implementations for evaluating betweenness centrality on massive datasets. In IPDPS, pages 1--8, 2009. 10.1109\/IPDPS.2009.5161100"},{"key":"e_1_2_1_33_1","first-page":"91","volume-title":"PAKDD Part I","author":"Maiya A. S.","year":"2010","unstructured":"A. S. Maiya and T. Y. Berger-Wolf . Online sampling of high centrality individuals in social networks . In PAKDD Part I , pages 91 -- 98 , 2010 . 10.1007\/978-3-642-13657-3_12 A. S. Maiya and T. Y. Berger-Wolf. Online sampling of high centrality individuals in social networks. In PAKDD Part I, pages 91--98, 2010. 10.1007\/978-3-642-13657-3_12"},{"key":"e_1_2_1_34_1","first-page":"135","volume-title":"SIGMOD","author":"Malewicz G.","year":"2010","unstructured":"G. Malewicz and et. al. Pregel : a system for large-scale graph processing . In SIGMOD , pages 135 -- 146 , 2010 . 10.1145\/1807167.1807184 G. Malewicz and et. al. Pregel: a system for large-scale graph processing. In SIGMOD, pages 135--146, 2010. 10.1145\/1807167.1807184"},{"key":"e_1_2_1_35_1","first-page":"427","volume-title":"WWW","author":"Meusel R.","year":"2014","unstructured":"R. Meusel and et. al. Graph structure in the web - revisited: a trick of the heavy tail . In WWW , pages 427 -- 432 , 2014 . 10.1145\/2567948.2576928 R. Meusel and et. al. Graph structure in the web - revisited: a trick of the heavy tail. In WWW, pages 427--432, 2014. 10.1145\/2567948.2576928"},{"key":"e_1_2_1_36_1","volume-title":"ECIS, page 101","author":"Mochalova A.","year":"2013","unstructured":"A. Mochalova and A. Nanopoulos . On the role of centrality in information diffusion in social networks . In ECIS, page 101 , 2013 . A. Mochalova and A. Nanopoulos. On the role of centrality in information diffusion in social networks. In ECIS, page 101, 2013."},{"key":"e_1_2_1_37_1","volume-title":"INFOCOM","author":"Ng T. S. E.","year":"2002","unstructured":"T. S. E. Ng and H. Zhang . Predicting internet network distance with coordinates-based approaches . In INFOCOM , 2002 . T. S. E. Ng and H. Zhang. Predicting internet network distance with coordinates-based approaches. In INFOCOM, 2002."},{"key":"e_1_2_1_38_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1007\/978-3-319-11593-1_19","volume-title":"Geographic Information Science","author":"Oliver D.","year":"2014","unstructured":"D. Oliver and et. al. Significant route discovery: A summary of results . In Geographic Information Science , volume 8728 of Lecture Notes in Computer Science , pages 284 -- 300 . Springer International Publishing , 2014 . D. Oliver and et. al. Significant route discovery: A summary of results. In Geographic Information Science, volume 8728 of Lecture Notes in Computer Science, pages 284--300. Springer International Publishing, 2014."},{"key":"e_1_2_1_39_1","first-page":"867","volume-title":"CIKM","author":"Potamias M.","year":"2009","unstructured":"M. Potamias , F. Bonchi , C. Castillo , and A. Gionis . Fast shortest path distance estimation in large networks . CIKM , pages 867 -- 876 , 2009 . 10.1145\/1645953.1646063 M. Potamias, F. Bonchi, C. Castillo, and A. Gionis. Fast shortest path distance estimation in large networks. CIKM, pages 867--876, 2009. 10.1145\/1645953.1646063"},{"key":"e_1_2_1_40_1","first-page":"867","volume-title":"CIKM","author":"Potamias M.","year":"2009","unstructured":"M. Potamias , F. Bonchi , C. Castillo , and A. Gionis . Fast shortest path distance estimation in large networks . In CIKM , pages 867 -- 876 , 2009 . 10.1145\/1645953.1646063 M. Potamias, F. Bonchi, C. Castillo, and A. Gionis. Fast shortest path distance estimation in large networks. In CIKM, pages 867--876, 2009. 10.1145\/1645953.1646063"},{"key":"e_1_2_1_41_1","first-page":"542","volume-title":"ISWC Proceedings, Part I","author":"Pujara J.","year":"2013","unstructured":"J. Pujara and et. al. Knowledge graph identification . In ISWC Proceedings, Part I , pages 542 -- 557 , 2013 . 10.1007\/978-3-642-41335-3_34 J. Pujara and et. al. Knowledge graph identification. In ISWC Proceedings, Part I, pages 542--557, 2013. 10.1007\/978-3-642-41335-3_34"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732219.2732225"},{"key":"e_1_2_1_43_1","first-page":"255","volume-title":"SSDBM","author":"Qiao M.","year":"2011","unstructured":"M. Qiao , H. Cheng , and J. X. Yu . Querying shortest path distance with bounded errors in large graphs . In SSDBM , pages 255 -- 273 , 2011 . M. Qiao, H. Cheng, and J. X. Yu. Querying shortest path distance with bounded errors in large graphs. In SSDBM, pages 255--273, 2011."},{"key":"e_1_2_1_44_1","first-page":"1200","volume-title":"ICDM","author":"Ruan N.","year":"2011","unstructured":"N. Ruan , R. Jin , and Y. Huang . Distance preserving graph simplification . In ICDM , pages 1200 -- 1205 , 2011 . 10.1109\/ICDM.2011.57 N. Ruan, R. Jin, and Y. Huang. Distance preserving graph simplification. In ICDM, pages 1200--1205, 2011. 10.1109\/ICDM.2011.57"},{"key":"e_1_2_1_46_1","first-page":"421","volume-title":"SIGMOD","author":"Tao Y.","year":"2011","unstructured":"Y. Tao , C. Sheng , and J. Pei . On k-skip shortest paths . In SIGMOD , pages 421 -- 432 , 2011 . 10.1145\/1989323.1989368 Y. Tao, C. Sheng, and J. Pei. On k-skip shortest paths. In SIGMOD, pages 421--432, 2011. 10.1145\/1989323.1989368"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733103"},{"key":"e_1_2_1_48_1","first-page":"625","volume-title":"ICDE","author":"Yan D.","year":"2013","unstructured":"D. Yan , J. Cheng , W. Ng , and S. Liu . Finding distance-preserving subgraphs in large road networks . In ICDE , pages 625 -- 636 , 2013 . 10.1109\/ICDE.2013.6544861 D. Yan, J. Cheng, W. Ng, and S. Liu. Finding distance-preserving subgraphs in large road networks. In ICDE, pages 625--636, 2013. 10.1109\/ICDE.2013.6544861"},{"key":"e_1_2_1_49_1","first-page":"174","volume-title":"CSB Workshops","author":"Yang Q.","year":"2005","unstructured":"Q. Yang and S. Lonardi . A parallel algorithm for clustering protein-protein interaction networks . In CSB Workshops , pages 174 -- 177 , 2005 . 10.1109\/CSBW.2005.13 Q. Yang and S. Lonardi. A parallel algorithm for clustering protein-protein interaction networks. In CSB Workshops, pages 174--177, 2005. 10.1109\/CSBW.2005.13"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2824032.2824041","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:02:25Z","timestamp":1672221745000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2824032.2824041"}},"subtitle":["a betweenness aware approach"],"short-title":[],"issued":{"date-parts":[[2015,8]]},"references-count":48,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2015,8]]}},"alternative-id":["10.14778\/2824032.2824041"],"URL":"http:\/\/dx.doi.org\/10.14778\/2824032.2824041","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,8]]}}}