{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T19:40:43Z","timestamp":1770234043260,"version":"3.49.0"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,6,6]],"date-time":"2016-06-06T00:00:00Z","timestamp":1465171200000},"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":["Data Min Knowl Disc"],"published-print":{"date-parts":[[2017,3]]},"DOI":"10.1007\/s10618-016-0468-8","type":"journal-article","created":{"date-parts":[[2016,6,6]],"date-time":"2016-06-06T07:35:07Z","timestamp":1465198507000},"page":"314-349","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":55,"title":["Graph summarization with quality guarantees"],"prefix":"10.1007","volume":"31","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2523-4420","authenticated-orcid":false,"given":"Matteo","family":"Riondato","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Garc\u00eda-Soriano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francesco","family":"Bonchi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,6,6]]},"reference":[{"key":"468_CR1","doi-asserted-by":"crossref","unstructured":"Aggarwal A, Deshpande A, Kannan R (2009) Adaptive sampling for k-means clustering. Approximation, randomization, and combinatorial optimization. Algorithms and techniques, APPROX-RANDOM. Springer, Berlin, pp 15\u201328","DOI":"10.1007\/978-3-642-03685-9_2"},{"issue":"2","key":"468_CR2","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/s10994-009-5103-0","volume":"75","author":"D Aloise","year":"2009","unstructured":"Aloise D, Deshpande A, Hansen P, Popat P (2009) NP-hardness of Euclidean sum-of-squares clustering. Mach Learn 75(2):245\u2013248","journal-title":"Mach Learn"},{"issue":"1","key":"468_CR3","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1006\/jagm.1994.1005","volume":"16","author":"N Alon","year":"1994","unstructured":"Alon N, Duke RA, Lefmann H, R\u00f6dl V, Yuster R (1994) The algorithmic aspects of the regularity lemma. J Algorithms 16(1):80\u2013109","journal-title":"J Algorithms"},{"issue":"4","key":"468_CR4","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1137\/S0097539704441629","volume":"35","author":"N Alon","year":"2006","unstructured":"Alon N, Naor A (2006) Approximating the cut-norm via Grothendieck\u2019s inequality. SIAM J Comput 35(4):787\u2013803","journal-title":"SIAM J Comput"},{"key":"468_CR5","unstructured":"Arthur D, Vassilvitskii S (2007) \n                        $$k$$\n                        \n                            \n                                k\n                            \n                        \n                    -means++: the advantages of careful seeding. In: Proceedings of the 18th annual ACM-SIAM symposium on discrete algorithms, SIAM, SODA \u201907, pp 1027\u20131035"},{"issue":"3","key":"468_CR6","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1137\/S0097539702416402","volume":"33","author":"V Arya","year":"2004","unstructured":"Arya V, Garg N, Khandekar R, Meyerson A, Munagala K, Pandit V (2004) Local search heuristics for \n                        $$k$$\n                        \n                            \n                                k\n                            \n                        \n                    -median and facility location problems. SIAM J Comput 33(3):544\u2013562","journal-title":"SIAM J Comput"},{"issue":"7","key":"468_CR7","doi-asserted-by":"crossref","first-page":"622","DOI":"10.14778\/2180912.2180915","volume":"5","author":"B Bahmani","year":"2012","unstructured":"Bahmani B, Moseley B, Vattani A, Kumar R, Vassilvitskii S (2012) Scalable \n                        $$k$$\n                        \n                            \n                                k\n                            \n                        \n                    -means++. Proc VLDB Endow 5(7):622\u2013633","journal-title":"Proc VLDB Endow"},{"issue":"3","key":"468_CR8","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1080\/15427951.2009.10390641","volume":"6","author":"P Boldi","year":"2009","unstructured":"Boldi P, Santini M, Vigna S (2009) Permuting web and social graphs. Internet Math 6(3):257\u2013283","journal-title":"Internet Math"},{"key":"468_CR9","doi-asserted-by":"crossref","unstructured":"Boldi P, Rosa M, Santini M, Vigna S (2011) Layered label propagation: a multiresolution coordinate-free ordering for compressing social networks. In: Proceedings of the 20th international conference on World Wide Web, ACM, WWW \u201911, pp 587\u2013596","DOI":"10.1145\/1963405.1963488"},{"key":"468_CR10","doi-asserted-by":"crossref","unstructured":"Boldi P, Vigna S (2004) The webgraph framework i: compression techniques. In: Proceedings of the 13th international conference on World Wide Web, ACM, WWW \u201904, pp 595\u2013602","DOI":"10.1145\/988672.988752"},{"key":"468_CR11","unstructured":"Bonchi F, Garc\u00eda-Soriano D, Kutzkov K (2013) Local correlation clustering. arXiv preprint \n                        arXiv:1312.5105v1"},{"key":"468_CR12","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/978-3-642-01718-6_4","volume-title":"Privacy, security, and trust in KDD","author":"A Campan","year":"2009","unstructured":"Campan A, Truta TM (2009) Data and structural k-anonymity in social networks. Privacy, security, and trust in KDD. Springer, Berlin, pp 33\u201354"},{"issue":"5","key":"468_CR13","doi-asserted-by":"crossref","first-page":"1191","DOI":"10.1007\/s00039-012-0171-x","volume":"22","author":"D Conlon","year":"2012","unstructured":"Conlon D, Fox J (2012) Bounds for graph regularity and removal lemmas. Geom Funct Anal 22(5):1191\u20131256","journal-title":"Geom Funct Anal"},{"issue":"1","key":"468_CR14","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/s00778-009-0167-9","volume":"19","author":"G Cormode","year":"2010","unstructured":"Cormode G, Srivastava D, Yu T, Zhang Q (2010) Anonymizing bipartite graph data using safe groupings. VLDB J 19(1):115\u2013139","journal-title":"VLDB J"},{"key":"468_CR15","unstructured":"Dasgupta S (2008) The hardness of \n                        $$k$$\n                        \n                            \n                                k\n                            \n                        \n                    -means clustering. Tech. Rep. 09-16. University of California, San Diego"},{"issue":"1","key":"468_CR16","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1137\/110846373","volume":"26","author":"DJ Dellamonica","year":"2012","unstructured":"Dellamonica DJ, Kalyanasundaram S, Martin DM, R\u00f6dl V, Shapira A (2012) A deterministic algorithm for the Frieze-Kannan regularity lemma. SIAM J Discret Math 26(1):15\u201329","journal-title":"SIAM J Discret Math"},{"issue":"02","key":"468_CR17","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1017\/S0963548314000200","volume":"24","author":"DJ Dellamonica","year":"2015","unstructured":"Dellamonica DJ, Kalyanasundaram S, Martin DM, R\u00f6dl V, Shapira A (2015) An optimal algorithm for finding Frieze-Kannan regular partitions. Comb Prob Comput 24(02):407\u2013437","journal-title":"Comb Prob Comput"},{"key":"468_CR18","doi-asserted-by":"crossref","unstructured":"Fan W, Li J, Wang X, Wu Y (2012) Query preserving graph compression. In: Proceedings of the 2012 ACM SIGMOD international conference on management of data, ACM, SIGMOD \u201912, pp 157\u2013168","DOI":"10.1145\/2213836.2213855"},{"issue":"2","key":"468_CR19","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/s004930050052","volume":"19","author":"A Frieze","year":"1999","unstructured":"Frieze A, Kannan R (1999) Quick approximation to matrices and applications. Combinatorica 19(2):175\u2013220","journal-title":"Combinatorica"},{"issue":"2","key":"468_CR20","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1007\/PL00001621","volume":"7","author":"WT Gowers","year":"1997","unstructured":"Gowers WT (1997) Lower bounds of tower type for Szemer\u00e9di\u2019s uniformity lemma. Geom Funct Anal 7(2):322\u2013337","journal-title":"Geom Funct Anal"},{"issue":"6","key":"468_CR21","doi-asserted-by":"crossref","first-page":"797","DOI":"10.1007\/s00778-010-0210-x","volume":"19","author":"M Hay","year":"2010","unstructured":"Hay M, Miklau G, Jensen D, Towsley D, Li C (2010) Resisting structural re-identification in anonymized social networks. VLDB J 19(6):797\u2013823","journal-title":"VLDB J"},{"key":"468_CR22","unstructured":"Hern\u00e1ndez C, Navarro G (2011) Compression of web and social graphs supporting neighbor and community queries. In: Proceedings of the 6th ACM workshop on social network mining and analysis, ACM, SNAKDD \u201911"},{"issue":"3","key":"468_CR23","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1145\/1147954.1147955","volume":"53","author":"P Indyk","year":"2006","unstructured":"Indyk P (2006) Stable distributions, pseudorandom generators, embeddings, and data stream computation. J ACM 53(3):307\u2013323","journal-title":"J ACM"},{"issue":"2","key":"468_CR24","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K Jain","year":"2001","unstructured":"Jain K, Vazirani VV (2001) Approximation algorithms for metric facility location and \n                        $$k$$\n                        \n                            \n                                k\n                            \n                        \n                    -median problems using the primal-dual schema and Lagrangian relaxation. J ACM 48(2):274\u2013296","journal-title":"J ACM"},{"key":"468_CR25","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1090\/conm\/026\/737400","volume":"26","author":"WB Johnson","year":"1984","unstructured":"Johnson WB, Lindenstrauss J (1984) Extensions of Lipschitz mappings into a Hilbert space. Contemp Math 26:189\u2013206","journal-title":"Contemp Math"},{"key":"468_CR26","doi-asserted-by":"crossref","unstructured":"LeFevre K, Terzi E (2010) GraSS: graph structure summarization. In: Proceedings of the 2010 SIAM international conference on data mining, SIAM, SDM \u201910, pp 454\u2013465","DOI":"10.1137\/1.9781611972801.40"},{"issue":"1","key":"468_CR27","first-page":"32","volume":"7","author":"Z Liu","year":"2012","unstructured":"Liu Z, Yu JX, Cheng H (2012) Approximate homogeneous graph summarization. Inf Media Technol 7(1):32\u201343","journal-title":"Inf Media Technol"},{"issue":"2","key":"468_CR28","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","volume":"28","author":"S Lloyd","year":"1982","unstructured":"Lloyd S (1982) Least squares quantization in PCM. IEEE Trans Inf Theory 28(2):129\u2013137","journal-title":"IEEE Trans Inf Theory"},{"key":"468_CR29","volume-title":"Large networks and graph limits","author":"L Lov\u00e1sz","year":"2012","unstructured":"Lov\u00e1sz L (2012) Large networks and graph limits. American Mathematical Society, Providence"},{"key":"468_CR30","doi-asserted-by":"crossref","unstructured":"Maserrat H, Pei J (2010) Neighbor query friendly compression of social networks. In: Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, KDD \u201910, pp 533\u2013542","DOI":"10.1145\/1835804.1835873"},{"issue":"1","key":"468_CR31","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1137\/0213014","volume":"13","author":"N Megiddo","year":"1984","unstructured":"Megiddo N, Supowit KJ (1984) On the complexity of some common geometric location problems. SIAM J Comput 13(1):182\u2013196","journal-title":"SIAM J Comput"},{"issue":"3","key":"468_CR32","doi-asserted-by":"crossref","first-page":"816","DOI":"10.1137\/S0097539701383443","volume":"32","author":"RR Mettu","year":"2003","unstructured":"Mettu RR, Plaxton CG (2003) The online median problem. SIAM J Comput 32(3):816\u2013832","journal-title":"SIAM J Comput"},{"key":"468_CR33","doi-asserted-by":"crossref","unstructured":"Navlakha S, Rastogi R, Shrivastava N (2008) Graph summarization with bounded error. In: Proceedings of the 2008 ACM SIGMOD international conference on Management of data, ACM, SIGMOD \u201908, pp 419\u2013432","DOI":"10.1145\/1376616.1376661"},{"key":"468_CR34","doi-asserted-by":"crossref","unstructured":"Riondato M, Garc\u00eda-Soriano D, Bonchi F (2014) Graph summarization with quality guarantees. In: 2014 IEEE international conference on data mining, IEEE, ICDM \u201914, pp 947\u2013952","DOI":"10.1109\/ICDM.2014.56"},{"issue":"1","key":"468_CR35","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.cosrev.2007.05.001","volume":"1","author":"SE Schaeffer","year":"2007","unstructured":"Schaeffer SE (2007) Graph clustering. Comput Sci Rev 1(1):27\u201364","journal-title":"Graph clustering. Comput Sci Rev"},{"key":"468_CR36","unstructured":"Szemer\u00e9di E (1976) Regular partitions of graphs. In: Probl\u00e8mes Combinatoires et Th\u00e9orie des Graphes, Colloq. Internat. CNRS, Univ. Orsay., pp 399\u2013401"},{"issue":"2","key":"468_CR37","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1109\/TKDE.2011.232","volume":"25","author":"T Tassa","year":"2013","unstructured":"Tassa T, Cohen DJ (2013) Anonymization of centralized and distributed social networks by sequential clustering. IEEE Trans Knowl Data Eng 25(2):311\u2013324","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"468_CR38","doi-asserted-by":"crossref","unstructured":"Tian Y, Hankins RA, Patel JM (2008) Efficient aggregation for graph summarization. In: Proceedings of the 2008 ACM SIGMOD international conference on management of data, ACM, SIGMOD \u201908, pp 567\u2013580","DOI":"10.1145\/1376616.1376675"},{"key":"468_CR39","doi-asserted-by":"crossref","unstructured":"Toivonen H, Zhou F, Hartikainen A, Hinkka A (2011) Compression of weighted graphs. In: Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, KDD \u201911, pp 965\u2013973","DOI":"10.1145\/2020408.2020566"},{"key":"468_CR40","doi-asserted-by":"crossref","unstructured":"Tsourakakis CE (2008) Fast counting of triangles in large real networks without counting: algorithms and laws. In: 2008 IEEE international conference on data mining, IEEE, ICDM \u201908, pp 608\u2013617","DOI":"10.1109\/ICDM.2008.72"},{"key":"468_CR41","unstructured":"Vassilevska Williams V (2011) Breaking the Coppersmith\u2013Winograd barrier, unpublished manuscript"},{"issue":"301","key":"468_CR42","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1080\/01621459.1963.10500845","volume":"58","author":"JH Ward","year":"1963","unstructured":"Ward JH (1963) Hierarchical grouping to optimize an objective function. J Am Stat Assoc 58(301):236\u2013244","journal-title":"J Am Stat Assoc"},{"key":"468_CR43","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511813658","volume-title":"Probability with Martingales","author":"D Williams","year":"1991","unstructured":"Williams D (1991) Probability with Martingales. Cambridge University Press, Cambridge"},{"key":"468_CR44","doi-asserted-by":"crossref","unstructured":"Zheleva E, Getoor L (2008) Preserving the privacy of sensitive relationships in graph data. In: Privacy, security, and trust in KDD, Springer, pp 153\u2013171","DOI":"10.1007\/978-3-540-78478-4_9"}],"container-title":["Data Mining and Knowledge Discovery"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10618-016-0468-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-016-0468-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-016-0468-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-016-0468-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,12,4]],"date-time":"2018-12-04T03:41:51Z","timestamp":1543894911000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10618-016-0468-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,6]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,3]]}},"alternative-id":["468"],"URL":"https:\/\/doi.org\/10.1007\/s10618-016-0468-8","relation":{},"ISSN":["1384-5810","1573-756X"],"issn-type":[{"value":"1384-5810","type":"print"},{"value":"1573-756X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6,6]]}}}