{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:41:12Z","timestamp":1725558072007},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2018,7,18]],"date-time":"2018-07-18T00:00:00Z","timestamp":1531872000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib Parallel Databases"],"published-print":{"date-parts":[[2018,9]]},"DOI":"10.1007\/s10619-018-7232-6","type":"journal-article","created":{"date-parts":[[2018,7,18]],"date-time":"2018-07-18T23:30:30Z","timestamp":1531956630000},"page":"555-592","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Distributed computing connected components with linear communication cost"],"prefix":"10.1007","volume":"36","author":[{"given":"Xing","family":"Feng","sequence":"first","affiliation":[]},{"given":"Lijun","family":"Chang","sequence":"additional","affiliation":[]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[]},{"given":"Lu","family":"Qin","sequence":"additional","affiliation":[]},{"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Long","family":"Yuan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,7,18]]},"reference":[{"key":"7232_CR1","doi-asserted-by":"publisher","first-page":"1258","DOI":"10.1109\/TC.1987.1676869","volume":"10","author":"B Awerbuch","year":"1987","unstructured":"Awerbuch, B., Shiloach, Y.: New connectivity and MSF algorithms for shuffle-exchange network and PRAM. IEEE Trans. Comput. 10, 1258\u20131263 (1987)","journal-title":"IEEE Trans. Comput."},{"key":"7232_CR2","doi-asserted-by":"crossref","unstructured":"Ceccarello, M., Pietracaprina, A., Pucci, G., Upfal, E.: Space and time efficient parallel graph decomposition, clustering and diameter approximation. In: Proceedings of SPAA\u201915 (2015)","DOI":"10.1145\/2755573.2755591"},{"key":"7232_CR3","doi-asserted-by":"crossref","unstructured":"Chang, L., Yu, J.\u00a0X., Qin, L., Lin, X., Liu, C., Liang, W.: Efficiently computing k-edge connected components via graph decomposition. In: Proceedings of SIGMOD\u201913 (2013)","DOI":"10.1145\/2463676.2465323"},{"key":"7232_CR4","unstructured":"Ching, A., Kunz, C.: Giraph: large-scale graph processing infrastructure on hadoop. Hadoop Summit (2011)"},{"key":"7232_CR5","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1109\/MCSE.2009.120","volume":"11","author":"J Cohen","year":"2009","unstructured":"Cohen, J.: Graph twiddling in a mapreduce world. Comput. Sci. Eng. 11, 29\u201341 (2009)","journal-title":"Comput. Sci. Eng."},{"key":"7232_CR6","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2001","unstructured":"Cormen, T.H., Stein, C., Rivest, R.L., Leiserson, C.E.: Introduction to Algorithms. McGraw-Hill Higher Education, New York (2001)"},{"key":"7232_CR7","unstructured":"Dean, J., Ghemawat, S.: Mapreduce: Simplified data processing on large clusters. In: Proceedings of OSDI\u201904 (2004)"},{"key":"7232_CR8","doi-asserted-by":"crossref","unstructured":"Feng, X., Chang, L., Lin, X., Qin, L., Zhang, W.: Computing connected components with linear communication cost in pregel-like systems. In: Proceedings of ICDE\u201916 (2016)","DOI":"10.1109\/ICDE.2016.7498231"},{"key":"7232_CR9","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.physrep.2009.11.002","volume":"486","author":"S Fortunato","year":"2010","unstructured":"Fortunato, S.: Community detection in graphs. Phys. Rep. 486, 75\u2013174 (2010)","journal-title":"Phys. Rep."},{"key":"7232_CR10","volume-title":"Algorithmic Graph Theory","author":"A Gibbons","year":"1985","unstructured":"Gibbons, A.: Algorithmic Graph Theory. Cambridge University Press, Cambridge (1985)"},{"key":"7232_CR11","unstructured":"Gonzalez, J.E., Xin, R.S., Dave, A., Crankshaw, D., Franklin, M.J., Stoica, I.: Graphx: graph processing in a distributed dataflow framework. In: Proceedings of OSDI\u201914 (2014)"},{"key":"7232_CR12","doi-asserted-by":"publisher","first-page":"1317","DOI":"10.1109\/TVCG.2008.141","volume":"14","author":"N Henry","year":"2008","unstructured":"Henry, N., Bezerianos, A., Fekete, J.: Improving the readability of clustered social networks using node duplication. IEEE Trans. Vis. Comput. Graph. 14, 1317\u20131324 (2008)","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"7232_CR13","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1145\/362248.362272","volume":"16","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Efficient algorithms for graph manipulation [H] (algorithm 447). Commun. ACM 16, 372\u2013378 (1973)","journal-title":"Commun. ACM"},{"key":"7232_CR14","unstructured":"Kang, U., Tsourakakis, C.E., Faloutsos, C.: PEGASUS: a peta-scale graph mining system. In: Proceedings of ICDM\u201909 (2009)"},{"key":"7232_CR15","doi-asserted-by":"crossref","unstructured":"Kang, U., McGlohon, M., Akoglu, L., Faloutsos, C.: Patterns on the connected components of terabyte-scale graphs. In: Proceedings of ICDM\u201910 (2010)","DOI":"10.1109\/ICDM.2010.121"},{"key":"7232_CR16","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/j.cosrev.2009.08.001","volume":"3","author":"T Kavitha","year":"2009","unstructured":"Kavitha, T., Liebchen, C., Mehlhorn, K., Michail, D., Rizzi, R., Ueckerdt, T., Zweig, K.A.: Cycle bases in graphs characterization, algorithms, complexity, and applications. Comput. Sci. Rev. 3, 199\u2013243 (2009)","journal-title":"Comput. Sci. Rev."},{"key":"7232_CR17","first-page":"716","volume":"5","author":"Y Low","year":"2012","unstructured":"Low, Y., Gonzalez, J., Kyrola, A., Bickson, D., Guestrin, C., Hellerstein, J.M.: Distributed graphlab: a framework for machine learning in the cloud. PVLDB 5, 716\u2013727 (2012)","journal-title":"PVLDB"},{"key":"7232_CR18","doi-asserted-by":"crossref","unstructured":"Malewicz, G., Austern, M.H., Bik, A.J.C., Dehnert, J.C., Horn, I., Leiser, N., Czajkowski, G.: Pregel: a system for large-scale graph processing. In: Proceedings of SIGMOD\u201910 (2010)","DOI":"10.1145\/1807167.1807184"},{"key":"7232_CR19","doi-asserted-by":"crossref","unstructured":"Miller, G.L., Peng, R., Xu, S.C.: Parallel graph decompositions using random shifts. In: Proceedings of SPAA\u201913 (2013)","DOI":"10.1145\/2486159.2486180"},{"key":"7232_CR20","first-page":"162","volume":"135","author":"GL Miller","year":"1986","unstructured":"Miller, G.L., Ramachandran, V.: Efficient parallel ear decomposition with applications. MSRI 135, 162 (1986)","journal-title":"MSRI"},{"key":"7232_CR21","unstructured":"Munagala, K., Ranade, A.G.: I\/o-complexity of graph algorithms. In: Proceedings of SODA\u201999 (1999)"},{"key":"7232_CR22","doi-asserted-by":"crossref","unstructured":"Nanda, S., Kotz, D.: Localized bridging centrality for distributed network analysis. In: Proceedings of ICCCN\u201908 (2008)","DOI":"10.1109\/ICCCN.2008.ECP.31"},{"key":"7232_CR23","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1093\/bioinformatics\/btg415","volume":"20","author":"N Przulj","year":"2004","unstructured":"Przulj, N., Wigle, D., Jurisica, I.: Functional topology in a network of protein interactions. Bioinformatics 20, 340\u2013348 (2004)","journal-title":"Bioinformatics"},{"key":"7232_CR24","doi-asserted-by":"crossref","unstructured":"Qin, L., Yu, J.X., Chang, L., Cheng, H., Zhang, C., Lin, X.: Scalable big graph processing in mapreduce. In: Proceedings of SIGMOD\u201914 (2014)","DOI":"10.1145\/2588555.2593661"},{"key":"7232_CR25","unstructured":"Ramachandran, V.: Parallel open ear decomposition with applications to graph biconnectivity and triconnectivity. Citeseer (1992)"},{"key":"7232_CR26","doi-asserted-by":"crossref","unstructured":"Rastogi, V., Machanavajjhala, A., Chitnis, L., Sarma, A.D.: Finding connected components in map-reduce in logarithmic rounds. In: Proceedings of ICDE\u201913 (2013)","DOI":"10.1109\/ICDE.2013.6544813"},{"key":"7232_CR27","first-page":"577","volume":"7","author":"S Salihoglu","year":"2014","unstructured":"Salihoglu, S., Widom, J.: Optimizing graph algorithms on Pregel-like systems. PVLDB 7, 577\u2013588 (2014)","journal-title":"PVLDB"},{"key":"7232_CR28","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/S0020-0190(98)00127-6","volume":"67","author":"P Sanders","year":"1998","unstructured":"Sanders, P.: Random permutations on distributed, external and hierarchical memory. Inf. Process. Lett. 67, 305\u2013309 (1998)","journal-title":"Inf. Process. Lett."},{"key":"7232_CR29","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/j.ipl.2013.01.016","volume":"113","author":"JM Schmidt","year":"2013","unstructured":"Schmidt, J.M.: A simple test on 2-vertex- and 2-edge-connectivity. Inf. Process. Lett. 113, 241\u2013244 (2013)","journal-title":"Inf. Process. Lett."},{"key":"7232_CR30","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0196-6774(82)90008-6","volume":"3","author":"Y Shiloach","year":"1982","unstructured":"Shiloach, Y., Vishkin, U.: An o(log n) parallel connectivity algorithm. J. Algorithms 3, 57\u201367 (1982)","journal-title":"J. Algorithms"},{"key":"7232_CR31","doi-asserted-by":"crossref","unstructured":"Slota, G.M., Madduri, K.: Simple parallel biconnectivity algorithms for multicore platforms. In: Proceedings of HiPC\u201914 (2014)","DOI":"10.1109\/HiPC.2014.7116914"},{"key":"7232_CR32","doi-asserted-by":"crossref","unstructured":"Stanton, I.: Streaming balanced graph partitioning algorithms for random graphs. In: Proceedings of SODA\u201914 (2014)","DOI":"10.1137\/1.9781611973402.95"},{"key":"7232_CR33","doi-asserted-by":"publisher","first-page":"862","DOI":"10.1137\/0214061","volume":"14","author":"RE Tarjan","year":"1985","unstructured":"Tarjan, R.E., Vishkin, U.: An efficient parallel biconnectivity algorithm. SIAM J. Comput. 14, 862\u2013874 (1985)","journal-title":"SIAM J. Comput."},{"key":"7232_CR34","first-page":"193","volume":"7","author":"Y Tian","year":"2013","unstructured":"Tian, Y., Balmin, A., Corsten, S.A., Tatikonda, S., McPherson, J.: From \u201cthink like a vertex\u201d to \u201cthink like a graph\u201d. PVLDB 7, 193\u2013204 (2013)","journal-title":"PVLDB"},{"key":"7232_CR35","doi-asserted-by":"crossref","unstructured":"Turau, V.: Computing bridges, articulations, and 2-connected components in wireless sensor networks. In: Proceedings of ALGOSENSORS\u201906 (2006)","DOI":"10.1007\/11963271_15"},{"key":"7232_CR36","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1145\/79173.79181","volume":"33","author":"LG Valiant","year":"1990","unstructured":"Valiant, L.G.: A bridging model for parallel computation. Commun ACM 33, 103\u2013111 (1990)","journal-title":"Commun ACM"},{"key":"7232_CR37","doi-asserted-by":"crossref","unstructured":"Vega, D., Cerda-Alabern, L., Navarro, L., Meseguer, R.: Topology patterns of a community network: Guifi.net. In: Proceedings of WiMob\u201912 (2012)","DOI":"10.1109\/WiMOB.2012.6379139"},{"key":"7232_CR38","first-page":"1821","volume":"7","author":"D Yan","year":"2014","unstructured":"Yan, D., Cheng, J., Xing, K., Lu, Y., Ng, W., Bu, Y.: Pregel algorithms for graph connectivity problems with performance guarantees. PVLDB 7, 1821\u20131832 (2014)","journal-title":"PVLDB"},{"key":"7232_CR39","unstructured":"Zaharia, M., Chowdhury, M., Das, T., Dave, A., Ma, J., McCauly, M., Franklin, M.J., Shenker, S., Stoica, I.: Resilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing. In: Proceedings of NSDI\u201912 (2012)"}],"container-title":["Distributed and Parallel Databases"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10619-018-7232-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10619-018-7232-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10619-018-7232-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,17]],"date-time":"2019-07-17T19:23:36Z","timestamp":1563391416000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10619-018-7232-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,18]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,9]]}},"alternative-id":["7232"],"URL":"https:\/\/doi.org\/10.1007\/s10619-018-7232-6","relation":{},"ISSN":["0926-8782","1573-7578"],"issn-type":[{"value":"0926-8782","type":"print"},{"value":"1573-7578","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,7,18]]},"assertion":[{"value":"18 July 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}