{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T05:34:08Z","timestamp":1770269648178,"version":"3.49.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,9]]},"abstract":"<jats:p>\n            Studying the topology of a network is critical to inferring underlying dynamics such as tolerance to failure, group behavior and spreading patterns.\n            <jats:italic>k<\/jats:italic>\n            -core decomposition is a well-established metric which partitions a graph into layers from external to more central vertices. In this paper we aim to explore whether\n            <jats:italic>k<\/jats:italic>\n            -core decomposition of large networks can be computed using a consumer-grade PC. We feature implementations of the \"vertex-centric\" distributed protocol introduced by Montresor, De Pellegrini and Miorandi on GraphChi and Webgraph. Also, we present an accurate implementation of the Batagelj and Zaversnik algorithm for\n            <jats:italic>k<\/jats:italic>\n            -core decomposition in Webgraph. With our implementations, we show that we can efficiently handle networks of billions of edges using a single consumer-level machine within reasonable time and can produce excellent approximations in only a fraction of the execution time. To the best of our knowledge, our biggest graphs are considerably larger than the graphs considered in the literature. Next, we present an optimized implementation of an external-memory algorithm (EMcore) by Cheng, Ke, Chu, and \u00d6zsu. We show that this algorithm also performs well for large datasets, however, it cannot predict whether a given memory budget is sufficient for a new dataset. We present a thorough analysis of all algorithms concluding that it is viable to compute\n            <jats:italic>k<\/jats:italic>\n            -core decomposition for large networks in a consumer-grade PC.\n          <\/jats:p>","DOI":"10.14778\/2850469.2850471","type":"journal-article","created":{"date-parts":[[2016,2,1]],"date-time":"2016-02-01T14:10:31Z","timestamp":1454335831000},"page":"13-23","source":"Crossref","is-referenced-by-count":158,"title":["K-core decomposition of large networks on a single PC"],"prefix":"10.14778","volume":"9","author":[{"given":"Wissam","family":"Khaouid","sequence":"first","affiliation":[{"name":"University of Victoria, BC, Canada"}]},{"given":"Marina","family":"Barsky","sequence":"additional","affiliation":[{"name":"University of Victoria, BC, Canada"}]},{"given":"Venkatesh","family":"Srinivasan","sequence":"additional","affiliation":[{"name":"University of Victoria, BC, Canada"}]},{"given":"Alex","family":"Thomo","sequence":"additional","affiliation":[{"name":"University of Victoria, BC, Canada"}]}],"member":"320","published-online":{"date-parts":[[2015,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-7-207"},{"key":"e_1_2_1_2_1","volume-title":"k-core decomposition of internet graphs: hierarchies, self-similarity and measurement biases. arXiv preprint cs\/0511007","author":"Alvarez-Hamelin J. I.","year":"2005","unstructured":"J. I. Alvarez-Hamelin , L. Dall'Asta , A. Barrat , and A. Vespignani . k-core decomposition of internet graphs: hierarchies, self-similarity and measurement biases. arXiv preprint cs\/0511007 , 2005 . J. I. Alvarez-Hamelin, L. Dall'Asta, A. Barrat, and A. Vespignani. k-core decomposition of internet graphs: hierarchies, self-similarity and measurement biases. arXiv preprint cs\/0511007, 2005."},{"key":"e_1_2_1_3_1","first-page":"41","volume-title":"Advances in neural information processing systems","author":"Alvarez-Hamelin J. I.","year":"2005","unstructured":"J. I. Alvarez-Hamelin , L. Dall'Asta , A. Barrat , and A. Vespignani . Large scale networks fingerprinting and visualization using the k-core decomposition . In Advances in neural information processing systems , pages 41 -- 50 , 2005 . J. I. Alvarez-Hamelin, L. Dall'Asta, A. Barrat, and A. Vespignani. Large scale networks fingerprinting and visualization using the k-core decomposition. In Advances in neural information processing systems, pages 41--50, 2005."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2008.10.032"},{"key":"e_1_2_1_5_1","volume-title":"Linked: the new science of networks science of networks","author":"Barab\u00e1si A.-L.","year":"2014","unstructured":"A.-L. Barab\u00e1si and J. Frangos . Linked: the new science of networks science of networks . Basic Books , 2014 . A.-L. Barab\u00e1si and J. Frangos. Linked: the new science of networks science of networks. Basic Books, 2014."},{"key":"e_1_2_1_6_1","volume-title":"An o (m) algorithm for cores decomposition of networks. arXiv preprint cs\/0310049","author":"Batagelj V.","year":"2003","unstructured":"V. Batagelj and M. Zaversnik . An o (m) algorithm for cores decomposition of networks. arXiv preprint cs\/0310049 , 2003 . V. Batagelj and M. Zaversnik. An o (m) algorithm for cores decomposition of networks. arXiv preprint cs\/0310049, 2003."},{"key":"e_1_2_1_7_1","volume-title":"Parallel and distributed computation: numerical methods","author":"Bertsekas D. P.","year":"1989","unstructured":"D. P. Bertsekas and J. N. Tsitsiklis . Parallel and distributed computation: numerical methods . Prentice-Hall, Inc. , 1989 . D. P. Bertsekas and J. N. Tsitsiklis. Parallel and distributed computation: numerical methods. Prentice-Hall, Inc., 1989."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31585-5_40"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623655"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767911"},{"key":"e_1_2_1_12_1","volume-title":"K-core organization of complex networks. Physical review letters, 96(4)","author":"Dorogovtsev S. N.","year":"2006","unstructured":"S. N. Dorogovtsev , A. V. Goltsev , and J. F. F. Mendes . K-core organization of complex networks. Physical review letters, 96(4) , 2006 . S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes. K-core organization of complex networks. Physical review letters, 96(4), 2006."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1348549.1348552"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.73.056101"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/3191835.3191981"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78808-9_13"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-013-0122-z"},{"key":"e_1_2_1_19_1","first-page":"31","volume-title":"OSDI","volume":"12","author":"Kyrola A.","year":"2012","unstructured":"A. Kyrola , G. E. Blelloch , and C. Guestrin . Graphchi: Large-scale graph computation on just a pc . In OSDI , volume 12 , pages 31 -- 46 , 2012 . A. Kyrola, G. E. Blelloch, and C. Guestrin. Graphchi: Large-scale graph computation on just a pc. In OSDI, volume 12, pages 31--46, 2012."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-6045-0_10"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2164-11-S1-S3"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2010.11.027"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.124"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242600"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-011-0224-z"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2012.10.021"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0808904106"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496842"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1116502109"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2010.75"},{"key":"e_1_2_1_34_1","volume-title":"Virality prediction and community structure in social networks. Scientific reports, 3","author":"Weng L.","year":"2013","unstructured":"L. Weng , F. Menczer , and Y.-Y. Ahn . Virality prediction and community structure in social networks. Scientific reports, 3 , 2013 . L. Weng, F. Menczer, and Y.-Y. Ahn. Virality prediction and community structure in social networks. Scientific reports, 3, 2013."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/MS.2009.16"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2007.02.028"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2850469.2850471","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:47:45Z","timestamp":1672220865000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2850469.2850471"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,9]]}},"alternative-id":["10.14778\/2850469.2850471"],"URL":"https:\/\/doi.org\/10.14778\/2850469.2850471","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,9]]}}}