{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T04:39:53Z","timestamp":1777610393955,"version":"3.51.4"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2018,3,10]],"date-time":"2018-03-10T00:00:00Z","timestamp":1520640000000},"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":["Soc. Netw. Anal. Min."],"published-print":{"date-parts":[[2018,12]]},"DOI":"10.1007\/s13278-018-0491-4","type":"journal-article","created":{"date-parts":[[2018,3,10]],"date-time":"2018-03-10T01:11:42Z","timestamp":1520644302000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Reducing large graphs to small supergraphs: a unified approach"],"prefix":"10.1007","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0117-1656","authenticated-orcid":false,"given":"Yike","family":"Liu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tara","family":"Safavi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Neil","family":"Shah","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danai","family":"Koutra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,3,10]]},"reference":[{"key":"491_CR1","doi-asserted-by":"crossref","unstructured":"Ahmed A, Shervashidze N, Narayanamurthy S, Josifovski V, Smola AJ (2013) Distributed large-scale natural graph factorization. In: Proceedings of the 22nd international conference on world wide web (WWW), Rio de Janeiro, Brazil. International World Wide Web Conferences Steering Committee","DOI":"10.1145\/2488388.2488393"},{"issue":"2","key":"491_CR2","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1137\/0201008","volume":"1","author":"AV Aho","year":"1972","unstructured":"Aho AV, Garey MR, Ullman JD (1972) The transitive reduction of a directed graph. SIAM J Comput 1(2):131\u2013137","journal-title":"SIAM J Comput"},{"key":"491_CR3","doi-asserted-by":"crossref","unstructured":"Araujo M, G\u00fcnnemann S, Mateos G, Faloutsos C (2014) Beyond blocks: hyperbolic community detection. In: Proceedings of the European conference on machine learning and principles and practice of knowledge discovery in databases (ECML PKDD), Nancy, France","DOI":"10.1007\/978-3-662-44848-9_4"},{"key":"491_CR1300","doi-asserted-by":"crossref","unstructured":"Backstrom L, Huttenlocher DP, Kleinberg JM, Lan X (2006) Group formation in large social networks: membership, growth, and evolution. In: Proceedings of the 12th ACM international conference on knowledge discovery and data mining (SIGKDD), Philadelphia, PA","DOI":"10.1145\/1150402.1150412"},{"key":"491_CR4","doi-asserted-by":"crossref","unstructured":"Backstrom L, Kumar R, Marlow C, Novak J, Tomkins A (2008) Preferential behavior in online groups. In: Proceeding of the 1st ACM international conference on web search and data mining (WSDM)","DOI":"10.1145\/1341531.1341549"},{"issue":"8","key":"491_CR5","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1145\/2492007.2492029","volume":"56","author":"JD Batson","year":"2013","unstructured":"Batson JD, Spielman DA, Srivastava N, Teng S (2013) Spectral sparsification of graphs: theory and algorithms. Commun. ACM 56(8):87\u201394","journal-title":"Commun. ACM"},{"issue":"10","key":"491_CR6","doi-asserted-by":"publisher","first-page":"P10008","DOI":"10.1088\/1742-5468\/2008\/10\/P10008","volume":"2008","author":"VD Blondel","year":"2008","unstructured":"Blondel VD, Guillaume J-L, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. J Stat Mech Theory Exp 2008(10):P10008","journal-title":"J Stat Mech Theory Exp"},{"key":"491_CR7","doi-asserted-by":"crossref","unstructured":"Chakrabarti D, Papadimitriou S, Modha DS, Faloutsos C (2004) Fully automatic cross-associations. In: Proceedings of the 10th ACM international conference on knowledge discovery and data mining (SIGKDD), Seattle, WA","DOI":"10.21236\/ADA459025"},{"key":"491_CR8","doi-asserted-by":"crossref","unstructured":"Chierichetti F, Kumar R, Lattanzi S, Mitzenmacher M, Panconesi A, Raghavan P (2009) On compressing social networks. In: Proceedings of the 15th ACM international conference on knowledge discovery and data mining (SIGKDD), Paris, France","DOI":"10.1145\/1557019.1557049"},{"issue":"4","key":"491_CR9","doi-asserted-by":"publisher","first-page":"1523","DOI":"10.1109\/TIT.2005.844059","volume":"51","author":"R Cilibrasi","year":"2005","unstructured":"Cilibrasi R, Vit\u00e1nyi P (2005) Clustering by compression. IEEE Trans Inf Theory 51(4):1523\u20131545","journal-title":"IEEE Trans Inf Theory"},{"key":"491_CR10","unstructured":"clusterMaker (2016) Creating and visualizing Cytoscape clusters. http:\/\/www.cgl.ucsf.edu\/cytoscape\/cluster\/clusterMaker.shtml . Accessed 22 Feb 2016"},{"key":"491_CR11","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1613\/jair.43","volume":"1","author":"DJ Cook","year":"1994","unstructured":"Cook DJ, Holder LB (1994) Substructure discovery using minimum description length and background knowledge. J Artif Intell Res 1:231\u2013255","journal-title":"J Artif Intell Res"},{"key":"491_CR12","volume-title":"Elements of information theory","author":"TM Cover","year":"2012","unstructured":"Cover TM, Thomas JA (2012) Elements of information theory. Wiley, Hoboken"},{"key":"491_CR13","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10618-006-0057-3","volume":"15","author":"C Faloutsos","year":"2007","unstructured":"Faloutsos C, Megalooikonomou V (2007) On data mining, compression and kolmogorov complexity. Data Min Knowl Disc 15:3\u201320","journal-title":"Data Min Knowl Disc"},{"key":"491_CR14","doi-asserted-by":"crossref","unstructured":"Faloutsos M, Faloutsos P, Faloutsos C (1999) On power-law relationships of the internet topology. In: Proceedings of the ACM SIGCOMM 1999 conference on applications, technologies, architectures, and protocols for computer communication, Cambridge, MA","DOI":"10.1145\/316188.316229"},{"issue":"3","key":"491_CR15","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 (2010) Community detection in graphs. Phys Rep 486(3):75\u2013174","journal-title":"Phys Rep"},{"key":"491_CR16","doi-asserted-by":"crossref","unstructured":"Giatsidis C, Thilikos DM, Vazirgiannis M (2011) Evaluating cooperation in communities with the k-core structure. In: Proceedings of the 2011 international conference on advances in social networks analysis and mining. ASONAM '11. IEEE, Washington","DOI":"10.1109\/ASONAM.2011.65"},{"key":"491_CR17","doi-asserted-by":"publisher","first-page":"7821","DOI":"10.1073\/pnas.122653799","volume":"99","author":"M Girvan","year":"2002","unstructured":"Girvan M, Newman MEJ (2002) Community structure in social and biological networks. Proc Natl Acad Sci 99:7821\u20137826","journal-title":"Proc Natl Acad Sci"},{"key":"491_CR200","doi-asserted-by":"crossref","unstructured":"Goonetilleke O, Koutra D, Sellis T, Liao K (2017). Edge labeling schemes for graph data. In: Proceedings of the 29th international conference on scientific and statistical database management. SSDBM '17. ACM, Chicago, pp 12:1\u201312:12","DOI":"10.1145\/3085504.3085516"},{"key":"491_CR18","doi-asserted-by":"crossref","unstructured":"Hasan MA, Ahmed NK, Neville J (2016) Network sampling: methods and applications. https:\/\/www.cs.purdue.edu\/homes\/neville\/courses\/NetworkSampling-KDD13-final.pdf Accessed 21 Mar 2016","DOI":"10.1287\/educ.2016.0147"},{"key":"491_CR19","volume-title":"An efficient matlab algorithm for graph partitioning","author":"JP Hespanha","year":"2004","unstructured":"Hespanha JP (2004) An efficient matlab algorithm for graph partitioning. Department of Electrical and Computer Engineering, University of California, Santa Barbara"},{"key":"491_CR20","doi-asserted-by":"crossref","unstructured":"H\u00fcbler C, Kriegel H-P, Borgwardt K, Ghahramani Z (2008) Metropolis algorithms for representative subgraph sampling. In: Proceedings of the 2008 eighth IEEE international conference on data mining, ICDM \u201908, Washington, DC, USA, 2008. IEEE Computer Society","DOI":"10.1109\/ICDM.2008.124"},{"key":"491_CR400","unstructured":"Jin L, Koutra D (2017) Ecoviz: Comparative vizualization of time-evolving network summaries. In: ACM knowledge discovery and data mining (KDD) 2017 workshop on interactive data exploration and analytics, Halifax, NS, Canada"},{"key":"491_CR600","doi-asserted-by":"crossref","unstructured":"Jin D, Koutra D (2017) Exploratory analysis of graph data by leveraging domain knowledge. In: Proceedings of the 17th IEEE international conference on data mining (ICDM), New Orleans, LA, pp 187\u2013196","DOI":"10.1109\/ICDM.2017.28"},{"key":"491_CR300","doi-asserted-by":"crossref","unstructured":"Jin D, Leventidis A, Shen H, Zhang R, Wu J, Koutra D (2017) PERSEUS-HUB: interactive and collective exploration of large-scale graphs. Informatics 4(3):22","DOI":"10.3390\/informatics4030022"},{"key":"491_CR21","doi-asserted-by":"crossref","unstructured":"Kang U, Faloutsos C (2011) Beyond \u2018Caveman Communities\u2019: hubs and spokes for graph compression and mining. In: Proceedings of the 11th IEEE international conference on data mining (ICDM), Vancouver, Canada","DOI":"10.1109\/ICDM.2011.26"},{"key":"491_CR22","doi-asserted-by":"crossref","unstructured":"Karypis G, Kumar V (1999) Multilevel k-way hypergraph partitioning. In: Proceedings of the IEEE 36th conference on design automation conference (DAC), New Orleans, LA","DOI":"10.1145\/309847.309954"},{"key":"491_CR23","doi-asserted-by":"crossref","unstructured":"Kleinberg J, Kumar R, Raghavan P, Rajagopalan S, Tomkins A (1999) The web as a graph: measurements, models, and methods. In: Proceedings of the international computing and combinatorics conference (COCOON), Tokyo, Japan, Berlin, Germany. Springer","DOI":"10.1007\/3-540-48686-0_1"},{"key":"491_CR500","doi-asserted-by":"crossref","unstructured":"Koutra D, Faloutsos C (2017) Individual and collective graph mining: principles, algorithms, and applications. Synth Lect Data Min Knowl Discov 9(2):1\u2013206","DOI":"10.2200\/S00796ED1V01Y201708DMK014"},{"key":"491_CR25","doi-asserted-by":"crossref","unstructured":"Koutra D, Ke T-Y, Kang U, Chau DH, Pao H-KK, Faloutsos C (2011) Unifying guilt-by-association approaches: theorems and fast algorithms. In: Proceedings of the European conference on machine learning and principles and practice of knowledge discovery in databases (ECML PKDD), Athens, Greece","DOI":"10.1007\/978-3-642-23783-6_16"},{"key":"491_CR800","doi-asserted-by":"crossref","unstructured":"Koutra D, Koutras V, Prakash BA, Faloutsos C (2013) Patterns amongst competing task frequencies: super-linearities, and the Almond-DG model. In: Proceedings of the 17th Pacific-Asia conference on knowledge discovery and data mining (PAKDD), Gold Coast, Australia","DOI":"10.1007\/978-3-642-37453-1_17"},{"key":"491_CR24","doi-asserted-by":"crossref","unstructured":"Koutra D, Kang U, Vreeken J, Faloutsos C (2014) VoG: summarizing and understanding large graphs. In: Proceedings of the 14th SIAM international conference on data mining (SDM), Philadelphia, PA","DOI":"10.1137\/1.9781611973440.11"},{"key":"491_CR26","doi-asserted-by":"crossref","unstructured":"LeFevre K, Terzi E (2010) Grass: graph structure summarization. In: Proceedings of the 10th SIAM international conference on data mining (SDM), Columbus, OH. SIAM","DOI":"10.1137\/1.9781611972801.40"},{"key":"491_CR27","unstructured":"Leskovec J, Krevl A (2014) SNAP datasets: stanford large network dataset collection. http:\/\/snap.stanford.edu\/data . Accessed 22 Feb 2018"},{"key":"491_CR1200","doi-asserted-by":"crossref","unstructured":"Leskovec J, Kleinberg J, Christos F (2005) Graphs over time: densification laws, shrinking diameters and possible explanations. In: Proceedings of the 11th ACM international conference on knowledge discovery and data mining (SIGKDD), Chicago, IL. ACM","DOI":"10.1145\/1081870.1081893"},{"key":"491_CR28","doi-asserted-by":"crossref","unstructured":"Leskovec J, Lang KJ, Mahoney M (2010) Empirical comparison of algorithms for network community detection. In: Proceedings of the 19th international conference on world wide web (WWW), Raleigh, NC. ACM","DOI":"10.1145\/1772690.1772755"},{"key":"491_CR29","unstructured":"Liu Y, Shah N, Koutra D (2015) An empirical comparison of the summarization power of graph clustering methods. In: Neural information processing systems (NIPS) networks workshop, Montreal, Canada"},{"key":"491_CR100","unstructured":"Liu Y, Safavi T, Koutra D (2016) A graph summarization: a survey. CoRR. ACM Comput Surv. arXiv:1612.04883 (to appear)"},{"key":"491_CR30","doi-asserted-by":"crossref","unstructured":"Maiya AS, Berger-Wolf TY (2010) Sampling community structure. In: Proceedings of the 19th international conference on world wide web (WWW), Raleigh, NC. ACM","DOI":"10.1145\/1772690.1772762"},{"key":"491_CR31","doi-asserted-by":"crossref","unstructured":"Mathioudakis M, Bonchi F, Castillo C, Gionis A, Ukkonen A (2011) Sparsification of influence networks. In: Proceedings of the 17th ACM international conference on knowledge discovery and data mining (SIGKDD), San Diego, CA","DOI":"10.1145\/2020408.2020492"},{"key":"491_CR32","doi-asserted-by":"crossref","unstructured":"Navlakha S, Rastogi R, Shrivastava N (2008) Graph summarization with bounded error. In: Proceedings of the 2008 ACM international conference on management of data (SIGMOD), Vancouver, BC","DOI":"10.1145\/1376616.1376661"},{"key":"491_CR1400","unstructured":"OCP (2014). Open Connectome Project. http:\/\/www.openconnectomeproject.org . Accessed 3 Feb 2016"},{"key":"491_CR33","doi-asserted-by":"crossref","unstructured":"Prakash BA, Seshadri M, Sridharan A, Machiraju S, Faloutsos C (2010) EigenSpokes: surprising patterns and scalable community chipping in large graphs. In: Proceedings of the 14th Pacific-Asia conference on knowledge discovery and data mining (PAKDD), Hyderabad, India","DOI":"10.1007\/978-3-642-13672-6_42"},{"key":"491_CR34","unstructured":"Rafiei D, Curial S (2005) Sampling effectively visualizing large networks through sampling. In: 16th IEEE visualization conference (VIS), Minneapolis, MN"},{"key":"491_CR35","unstructured":"Raghavan S, Garcia-Molina H (2003) Representing web graphs. In: Proceedings of the 19th international conference on data engineering (ICDE), Bangalore, India. IEEE"},{"issue":"2","key":"491_CR36","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1214\/aos\/1176346150","volume":"11","author":"J Rissanen","year":"1983","unstructured":"Rissanen J (1983) A universal prior for integers and estimation by minimum description length. Ann Stat 11(2):416\u2013431","journal-title":"Ann Stat"},{"key":"491_CR700","doi-asserted-by":"crossref","unstructured":"Safavi T, Sripada C, Koutra D (2017) Scalable hashing-based network discovery. In: Proceedings of the 17th IEEE International Conference on Data Mining (ICDM), New Orleans, LA, pp 405\u2013414","DOI":"10.1109\/ICDM.2017.50"},{"key":"491_CR37","doi-asserted-by":"crossref","unstructured":"Shah N, Koutra D, Zou T, Gallagher B, Faloutsos C (2015) Timecrunch: interpretable dynamic graph summarization. In: Proceedings of the 21st ACM international conference on knowledge discovery and data mining (SIGKDD), Sydney, Australia. ACM","DOI":"10.1145\/2783258.2783321"},{"issue":"6","key":"491_CR38","doi-asserted-by":"publisher","first-page":"1913","DOI":"10.1137\/080734029","volume":"40","author":"DA Spielman","year":"2011","unstructured":"Spielman DA, Srivastava N (2011) Graph sparsification by effective resistances. SIAM J. Comput. 40(6):1913\u20131926","journal-title":"SIAM J. Comput."},{"key":"491_CR39","doi-asserted-by":"crossref","unstructured":"Yang J, Leskovec J (2013) Overlapping community detection at scale: a nonnegative matrix factorization approach. In: Proceeding of the 6th ACM international conference on web search and data mining (WSDM). ACM","DOI":"10.1145\/2433396.2433471"}],"container-title":["Social Network Analysis and Mining"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s13278-018-0491-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13278-018-0491-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13278-018-0491-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,12]],"date-time":"2019-10-12T12:52:55Z","timestamp":1570884775000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s13278-018-0491-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,10]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,12]]}},"alternative-id":["491"],"URL":"https:\/\/doi.org\/10.1007\/s13278-018-0491-4","relation":{},"ISSN":["1869-5450","1869-5469"],"issn-type":[{"value":"1869-5450","type":"print"},{"value":"1869-5469","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3,10]]},"assertion":[{"value":"16 May 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 January 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 February 2018","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 March 2018","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"17"}}