{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,21]],"date-time":"2026-07-21T11:14:12Z","timestamp":1784632452268,"version":"3.55.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2013,4]]},"abstract":"<jats:p>\n            A\n            <jats:italic>k<\/jats:italic>\n            -core of a graph is a maximal connected subgraph in which every vertex is connected to at least\n            <jats:italic>k<\/jats:italic>\n            vertices in the subgraph.\n            <jats:italic>k<\/jats:italic>\n            -core decomposition is often used in large-scale network analysis, such as community detection, protein function prediction, visualization, and solving NP-Hard problems on real networks efficiently, like maximal clique finding. In many real-world applications, networks change over time. As a result, it is essential to develop efficient incremental algorithms for streaming graph data. In this paper, we propose the first incremental\n            <jats:italic>k<\/jats:italic>\n            -core decomposition algorithms for streaming graph data. These algorithms locate a small subgraph that is guaranteed to contain the list of vertices whose maximum\n            <jats:italic>k<\/jats:italic>\n            -core values have to be updated, and efficiently process this subgraph to update the\n            <jats:italic>k<\/jats:italic>\n            -core decomposition. Our results show a significant reduction in run-time compared to non-incremental alternatives. We show the efficiency of our algorithms on different types of real and synthetic graphs, at different scales. For a graph of 16 million vertices, we observe speedups reaching a million times, relative to the non-incremental algorithms.\n          <\/jats:p>","DOI":"10.14778\/2536336.2536344","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"433-444","source":"Crossref","is-referenced-by-count":147,"title":["Streaming algorithms for k-core decomposition"],"prefix":"10.14778","volume":"6","author":[{"given":"Ahmet Erdem","family":"Sar\u00edy\u00fcce","sequence":"first","affiliation":[{"name":"Department of Biomedical Informatics, The Ohio State University and Department of Computer Science and Engineering, The Ohio State University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bu\u011fra","family":"Gedik","sequence":"additional","affiliation":[{"name":"Department of Computer Engineering, \u0130hsan Do\u011framac\u00ed Bilkent University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gabriela","family":"Jacques-Silva","sequence":"additional","affiliation":[{"name":"IBM Thomas J. Watson Research Center, IBM Research"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kun-Lung","family":"Wu","sequence":"additional","affiliation":[{"name":"IBM Thomas J. Watson Research Center, IBM Research"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"\u00dcmit V.","family":"\u00c7ataly\u00fcrek","sequence":"additional","affiliation":[{"name":"Department of Biomedical Informatics, The Ohio State University and Department of Electrical and Computer Engineering, The Ohio State University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,4]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"k-core decomposition: A tool for the visualization of large scale networks. The Computing Research Repository (CoRR), abs\/cs\/0504107","author":"Alvarez-Hamelin J. I.","year":"2005"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/978-3-540-95995-3_3","volume-title":"Workshop on Algorithms and Models for the Web Graph (WAW)","author":"Andersen R.","year":"2009"},{"key":"e_1_2_1_3_1","first-page":"4","article-title":"An automated method for finding molecular complexes in large protein interaction networks","author":"Bader G. D.","year":"2003","journal-title":"BMC Bioinformatics"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1287\/opre.1100.0851","article-title":"Clique relaxations in social network analysis: The maximum k-plex problem","volume":"59","author":"Balasundaram B.","year":"2011","journal-title":"Operations Research"},{"issue":"5439","key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","article-title":"Emergence of scaling in random networks","volume":"286","author":"Barab\u00e1si A.-L.","year":"1999","journal-title":"Science"},{"key":"e_1_2_1_6_1","volume-title":"An O(m) algorithm for cores decomposition of networks. The Computing Research Repository (CoRR), cs.DS\/0310049","author":"Batagelj V.","year":"2003"},{"issue":"2","key":"e_1_2_1_7_1","doi-asserted-by":"crossref","first-page":"277","DOI":"10.3934\/nhm.2008.3.277","article-title":"Augmenting k-core generation with preferential attachment","volume":"3","author":"Baur M.","year":"2008","journal-title":"Networks and Heterogeneous Media"},{"key":"e_1_2_1_8_1","volume-title":"SIAM International Conference on Data Mining (SDM)","author":"Chakrabarti D.","year":"2004"},{"key":"e_1_2_1_9_1","first-page":"51","volume-title":"IEEE International Conference on Data Engineering (ICDE)","author":"Cheng J.","year":"2011"},{"key":"e_1_2_1_10_1","volume-title":"10th DIMACS implementation challenge","author":"DIMACS."},{"key":"e_1_2_1_11_1","first-page":"96","article-title":"k-core organization of complex networks","author":"Dorogovtsev S. N.","year":"2006","journal-title":"Physical Review Letters"},{"key":"e_1_2_1_12_1","first-page":"461","volume-title":"World Wide Web Conference (WWW)","author":"Dourisboure Y.","year":"2007"},{"key":"e_1_2_1_13_1","first-page":"17","volume-title":"On the evolution of random graphs","author":"Erd\u00f6s P.","year":"1960"},{"issue":"3","key":"e_1_2_1_14_1","first-page":"75","article-title":"Community detection in graphs","volume":"483","author":"Fortunato S.","year":"2009","journal-title":"Physics Reports"},{"key":"e_1_2_1_15_1","first-page":"13","volume-title":"International Workshop on Inter-domain Performance and Simulation (IPS)","author":"Gaertler M.","year":"2004"},{"key":"e_1_2_1_16_1","first-page":"201","volume-title":"IEEE International Conference on Data Mining (ICDM)","author":"Giatsidis C.","year":"2011"},{"key":"e_1_2_1_17_1","first-page":"87","volume-title":"International Conference on Advances in Social Network Analysis and Mining (ASONAM)","author":"Giatsidis C.","year":"2011"},{"key":"e_1_2_1_18_1","first-page":"137","volume-title":"Workshop on Algorithms and Models for the Web Graph (WAW)","author":"Healy J.","year":"2006"},{"issue":"2","key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1006\/jagm.1994.1032","article-title":"Generating sparse 2-spanners","volume":"17","author":"Kortsarz G.","year":"1994","journal-title":"Journal of Algorithms"},{"key":"e_1_2_1_20_1","volume-title":"Efficient core maintenance in large dynamic graphs. CoRR, abs\/1207.4567","author":"Li R.-H.","year":"2012"},{"issue":"1","key":"e_1_2_1_21_1","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/0012-365X(91)90162-U","article-title":"Size and connectivity of the k-core of a random graph","volume":"91","author":"Luczak T.","year":"1991","journal-title":"Discrete Math"},{"key":"e_1_2_1_22_1","first-page":"435","volume-title":"ACM International Conference on Information and Knowledge Management (CIKM)","author":"Nanavati A. A.","year":"2006"},{"key":"e_1_2_1_23_1","first-page":"400","volume-title":"International Conference on Advances in Social Network Analysis and Mining (ASONAM)","author":"Ozgul F.","year":"2010"},{"key":"e_1_2_1_24_1","first-page":"45","volume-title":"International Workshop on Adversarial Information Retrieval on the Web (AIRWeb)","author":"Saito H.","year":"2007"},{"issue":"1","key":"e_1_2_1_25_1","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1006\/jmbi.1998.1689","article-title":"A graph-theoretic algorithm for comparative modeling of protein structure","volume":"279","author":"Samudrala R.","year":"1998","journal-title":"Journal of Molecular Biology"},{"issue":"3","key":"e_1_2_1_26_1","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/0378-8733(83)90028-X","article-title":"Network structure and minimum degree","volume":"5","author":"Seidman S. B.","year":"1983","journal-title":"Social Networks"},{"key":"e_1_2_1_27_1","unstructured":"SNAP. Stanford network analysis package. http:\/\/snap.stanford.edu\/snap.  SNAP. Stanford network analysis package. http:\/\/snap.stanford.edu\/snap."},{"issue":"12","key":"e_1_2_1_28_1","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1002\/spe.993","article-title":"Design principles for developing stream processing applications. Software","volume":"40","author":"Turaga D.","year":"2010","journal-title":"Practice & Experience"},{"key":"e_1_2_1_29_1","volume-title":"10th DIMACS Implementation Challenge","author":"Verma A.","year":"2011"},{"issue":"2","key":"e_1_2_1_30_1","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1002\/pmic.200400962","article-title":"Peeling the yeast protein network","volume":"5","author":"Wuchty S.","year":"2005","journal-title":"PROTEOMICS"},{"key":"e_1_2_1_31_1","first-page":"1049","volume-title":"IEEE International Conference on Data Engineering (ICDE)","author":"Zhang Y.","year":"2012"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2536336.2536344","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:42:06Z","timestamp":1672224126000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2536336.2536344"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4]]},"references-count":31,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2013,4]]}},"alternative-id":["10.14778\/2536336.2536344"],"URL":"https:\/\/doi.org\/10.14778\/2536336.2536344","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2013,4]]}}}