{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,24]],"date-time":"2026-04-24T11:25:27Z","timestamp":1777029927956,"version":"3.51.4"},"reference-count":57,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2013,4,26]],"date-time":"2013-04-26T00:00:00Z","timestamp":1366934400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Knowl Inf Syst"],"published-print":{"date-parts":[[2014,8]]},"DOI":"10.1007\/s10115-013-0648-4","type":"journal-article","created":{"date-parts":[[2013,4,30]],"date-time":"2013-04-30T18:01:43Z","timestamp":1367344903000},"page":"279-313","source":"Crossref","is-referenced-by-count":43,"title":["Compressed representations for web and social graphs"],"prefix":"10.1007","volume":"40","author":[{"given":"Cecilia","family":"Hern\u00e1ndez","sequence":"first","affiliation":[]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,4,26]]},"reference":[{"key":"648_CR1","doi-asserted-by":"crossref","unstructured":"Adler M, Mitzenmacher M (2001) Towards compressing web graphs. In: Proceedings of the data compression conference (DCC). Snowbird, UT, pp 203\u2013212","DOI":"10.1109\/DCC.2001.917151"},{"key":"648_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4419-6045-0","volume-title":"Managing and mining graph data","author":"C Aggarwal","year":"2010","unstructured":"Aggarwal C, Wang H (2010) Managing and mining graph data. Springer, Berlin"},{"key":"648_CR3","doi-asserted-by":"crossref","unstructured":"Anh V, Moffat A (2010) Local modeling for webgraph compression. In: Proceedings of the data compression conference (DCC). Snowbird UT, p 519","DOI":"10.1109\/DCC.2010.59"},{"issue":"3","key":"648_CR4","doi-asserted-by":"crossref","first-page":"1031","DOI":"10.3390\/a2031031","volume":"2","author":"A Apostolico","year":"2009","unstructured":"Apostolico A, Drovandi G (2009) Graph compression by BFS. Algorithms 2(3):1031\u20131044","journal-title":"Algorithms"},{"key":"648_CR5","doi-asserted-by":"crossref","unstructured":"Bader D, Madduri K (2005) Design and implementation of the HPCS graph analysis benchmark on symmetric multiprocessors. In: Proceedings of the 12th international high performance computing (HiPC). Goa, India, pp 465\u2013476","DOI":"10.1007\/11602569_48"},{"issue":"1","key":"648_CR6","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/1326561.1326563","volume":"2","author":"L Becchetti","year":"2008","unstructured":"Becchetti L, Castillo C, Donato D, Baeza-Yates R, Leonardi S (2008) Link analysis for web spam detection. ACM Trans Web 2(1):2","journal-title":"ACM Trans Web"},{"key":"648_CR7","doi-asserted-by":"crossref","unstructured":"Boldi P, Vigna S (2004) The Webgraph framework I: compression techniques. In: Proceedings of the 13th international conference on the world wide web (WWW), New York, NY, pp 595\u2013602","DOI":"10.1145\/988672.988752"},{"key":"648_CR8","doi-asserted-by":"crossref","unstructured":"Boldi P, Santini M, Vigna S (2009) Permuting web graph. In: The 6th workshop on algorithms and models for the web graph (WAW), Barcelona, Spain, pp 116\u2013126","DOI":"10.1007\/978-3-540-95995-3_10"},{"key":"648_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 (WWW), Hyderabad, India, pp 587\u2013596","DOI":"10.1145\/1963405.1963488"},{"issue":"7","key":"648_CR10","first-page":"107","volume":"1","author":"S Brin","year":"1998","unstructured":"Brin S, Page L (1998) The anatomy of a large-scale hypertextual web search engine. Comput Netw 1(7):107\u2013117","journal-title":"Comput Netw"},{"key":"648_CR11","doi-asserted-by":"crossref","unstructured":"Brisaboa N, Ladra S, Navarro G (2009) K2-trees for compact web graph representation. In: Proceedings of the 16th international symposium on string processing and information retrieval (SPIRE), Saariselk\u00e4, Finland, pp 18\u201330","DOI":"10.1007\/978-3-642-03784-9_3"},{"key":"648_CR12","unstructured":"Brisaboa N, Ladra S, Navarro G (2012) Personal communication including code"},{"key":"648_CR13","doi-asserted-by":"crossref","unstructured":"Broder A (2000) Min-wise independent permutations: theory and practice. In: Proceedings of the 27th international colloquium on automata, languages and programming (ICALP), Geneva, Italy, p 808","DOI":"10.1007\/3-540-45022-X_67"},{"key":"648_CR14","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1186\/1471-2105-7-488","volume":"7","author":"S Broh\u00e9e","year":"2006","unstructured":"Broh\u00e9e S, Van Helden J (2006) Evaluation of clustering algorithms for protein-protein interaction networks. BMC Bioinformatics 7:488","journal-title":"BMC Bioinformatics"},{"issue":"9","key":"648_CR15","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1145\/362342.362367","volume":"16","author":"C Bron","year":"1973","unstructured":"Bron C, Kerbosch J (1973) Finding all cliques of an undirected graph (Algorithm 457). Commun ACM 16(9):575\u2013576","journal-title":"Commun ACM"},{"key":"648_CR16","doi-asserted-by":"crossref","unstructured":"Buehrer G, Chellapilla K (2008) A scalable pattern mining approach to web graph compression with communities. In: Proceedings of the international conference on web search and web data mining (WSDM), Palo Alto, CA, pp 95\u2013106","DOI":"10.1145\/1341531.1341547"},{"key":"648_CR17","unstructured":"Cha M, Mislove A, Gummadi P (2009) A measurement-driven analysis of information propagation in the Flickr social networking. In: Proceedings of the 20th international conference on world wide web (WWW), Madrid, Spain, pp 721\u2013730"},{"key":"648_CR18","doi-asserted-by":"crossref","unstructured":"Chakrabarti D, Zhan Y, Faloutsos C (2004) R-MAT: a recursive model for graph mining. In: Proceedings of the 4th SIAM international conference on data mining (SDM), Lake Buena Vista, FL","DOI":"10.1137\/1.9781611972740.43"},{"key":"648_CR19","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 SIGKDD international conference on knowledge discovery and data mining (SIGKDD), Paris, France, pp 219\u2013228","DOI":"10.1145\/1557019.1557049"},{"key":"648_CR20","doi-asserted-by":"crossref","unstructured":"Claude F, Navarro F (2010) Extended compact web graph representations. In: Algorithms and applications. Lecture notes in computer science 6060. Springer, Berlin, pp 77\u201391","DOI":"10.1007\/978-3-642-12476-1_5"},{"key":"648_CR21","doi-asserted-by":"crossref","unstructured":"Claude F, Navarro G (2010) Fast and compact web graph representations. ACM Trans Web 4(4):16","DOI":"10.1145\/1841909.1841913"},{"key":"648_CR22","doi-asserted-by":"crossref","unstructured":"Claude F, Navarro G (2008) Practical rank\/select queries over arbitrary sequences. In: Proceedings of the 15th international symposium on string processing and information retrieval (SPIRE), Melbourne, Australia, pp 176\u2013187","DOI":"10.1007\/978-3-540-89097-3_18"},{"key":"648_CR23","doi-asserted-by":"crossref","unstructured":"Claude F, Ladra S (2011) Practical representations for web and social graphs. In: Proceedings of the 20th ACM conference on information and knowledge management (CIKM), Glasgow, UK, pp 1185\u20131190","DOI":"10.1145\/2063576.2063747"},{"key":"648_CR24","unstructured":"Clark D (1996) Compact Pat trees. Ph.D. Thesis, University of Waterloo, Canada"},{"key":"648_CR25","doi-asserted-by":"crossref","unstructured":"Demetrescu C, Finocchi I, Ribichini A (2006) Trading off space for passes in graph streaming problems. In: Proceedings of the 17th ACM-SIAM symposium on discrete algorithms (SODA), Miami, FL, pp 714\u2013723","DOI":"10.1145\/1109557.1109635"},{"key":"648_CR26","unstructured":"Donato D, Millozzi S, Leonardi S, Tsaparas P (2005) Mining the inner structure of the web graph. In: Proceedings of the 8th workshop on the web and databases (WebDB), Baltimore, MD, pp 145\u2013150"},{"key":"648_CR27","doi-asserted-by":"crossref","unstructured":"Dourisboure Y, Geraci F, Pellegrini M (2007) Extraction and classification of dense communities in the web. In: Proceedings of the 16th international conference on world wide web (WWW) Banff, Alberta, Canada, pp 461\u2013470","DOI":"10.1145\/1242572.1242635"},{"key":"648_CR28","unstructured":"Gibson D, Kumar R, Tomkins A (2005) Discovering large dense subgraphs in massive graphs. In: Proceedings of the 31st international conference on very large data bases (VLDB), Trondheim, Norway, pp 721\u2013732"},{"key":"648_CR29","unstructured":"Gonz\u00e1lez R, Grabowski S, M\u00e4kinen V, Navarro G (2005) Practical implementation of rank and select queries. In: Poster Proceedings of the volume of 4th workshop on efficient and experimental algorithms (WEA), Santorini Island, Greece, pp 27\u201338"},{"key":"648_CR30","doi-asserted-by":"crossref","unstructured":"Golynski A, Munro J, Rao S (2006) Rank\/select operations on large alphabets: a tool for text indexing. In: Proceedings of the seventeenth annual ACM-SIAM symposium on discrete algorithms (SODA), Miami, FL, pp 368\u2013373","DOI":"10.1145\/1109557.1109599"},{"key":"648_CR31","unstructured":"Grabowski S, Bieniecki W (2010) Tight and simple web graph compression. CoRR abs\/006.0809"},{"key":"648_CR32","doi-asserted-by":"crossref","unstructured":"Grabowski S, Bieniecki W (2011) Merging adjacency lists for efficient web graph compression. Adv Intell Soft Comput 103(1):385\u2013392","DOI":"10.1007\/978-3-642-23169-8_42"},{"key":"648_CR33","unstructured":"Grossi R, Gupta A, Vitter J (2003) High-order entropy-compressed text indexes. In: Proceedings of the 14th annual ACM-SIAM symposium on discrete algorithms (SODA), Baltimore, MD, pp 841\u2013850"},{"key":"648_CR34","doi-asserted-by":"crossref","unstructured":"Hasan M, Salem S, Zaki M (2011) SimClus: an effective algorithm for clustering with a lower bound on similarity. Knowl Inf Syst 28(3):665\u2013685","DOI":"10.1007\/s10115-010-0360-6"},{"key":"648_CR35","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 (SNAKDD), San Diego, CA"},{"key":"648_CR36","doi-asserted-by":"crossref","unstructured":"Hern\u00e1ndez C, Navarro G (2012) Compressed representation of web and social networks via dense subgraphs. In: Proceedings of the 19th international symposium on string processing and information retrieval (SPIRE), Cartagena de Indias, Colombia, pp 264\u2013276","DOI":"10.1007\/978-3-642-34109-0_28"},{"key":"648_CR37","unstructured":"Katarzyna M, Przemyslaw K, Piotr B (2009) User position measures in social networks. In: Proceedings of the 4th ACM workshop on social network mining and analysis (SNAKDD), Paris, France, pp 1\u20139"},{"issue":"5","key":"648_CR38","doi-asserted-by":"crossref","first-page":"604","DOI":"10.1145\/324133.324140","volume":"46","author":"J Kleinberg","year":"1999","unstructured":"Kleinberg J (1999) Authoritative sources in a hyperlinked environment. JACM 46(5):604\u2013632","journal-title":"JACM"},{"issue":"11","key":"648_CR39","doi-asserted-by":"crossref","first-page":"1481","DOI":"10.1016\/S1389-1286(99)00040-7","volume":"31","author":"R Kumar","year":"1999","unstructured":"Kumar R, Raghavan P, Rajagopalan S, Tomkins A (1999) Trawling the web for emerging cyber-communities. Comput Netw 31(11):1481\u20131493","journal-title":"Comput Netw"},{"key":"648_CR40","doi-asserted-by":"crossref","unstructured":"Larsson N, Moffat A (1999) Offline dictionary-based compression. In: Proceedings of the data compression conference (DCC), Snowbird, Utah, pp 296\u2013305","DOI":"10.1109\/DCC.1999.755679"},{"key":"648_CR41","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/978-1-4419-6045-0_10","volume":"2010","author":"V Lee","year":"2010","unstructured":"Lee V, Ruan N, Jin R, Aggarwal C (2010) A survey of algorithms for dense subgraph discovery. Manag Min Graph Data 2010:303\u2013336","journal-title":"Manag Min Graph Data"},{"issue":"1","key":"648_CR42","first-page":"693","volume":"3","author":"K Macropol","year":"2010","unstructured":"Macropol K, Singh A (2010) Scalable discovery of best clusters on large graphs. PVLDB J 3(1):693\u2013702","journal-title":"PVLDB J"},{"key":"648_CR43","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 (SIGKDD), Washington, DC, pp 533\u2013542","DOI":"10.1145\/1835804.1835873"},{"key":"648_CR44","doi-asserted-by":"crossref","unstructured":"Mcpherson J, Ma K, Ogawa M (2005) Discovering parametric clusters in social small-world graphs. In: Proceedings of the ACM symposium on applied computing, Santa Fe, New Mexico, USA","DOI":"10.1145\/1066677.1066954"},{"key":"648_CR45","doi-asserted-by":"crossref","unstructured":"Mislove A, Marcon M, Gummadi P, Druschel P, Bhattacharjee B (2007) Measurement and analysis of online social networks. In: Proceedings of the internet measurement conference (IMC), San Diego, CA, pp 29\u201342","DOI":"10.1145\/1298306.1298311"},{"issue":"1","key":"648_CR46","first-page":"22","volume":"22","author":"R Mishra","year":"2011","unstructured":"Mishra R, Shukla S, Arora D, Kumar M (2011) An effective comparison of graph clustering algorithms via random graphs. Int J Comput Appl 22(1):22\u201327","journal-title":"Int J Comput Appl"},{"issue":"3","key":"648_CR47","doi-asserted-by":"crossref","first-page":"715","DOI":"10.1007\/s10115-011-0431-3","volume":"30","author":"K Morik","year":"2012","unstructured":"Morik K, Kaspari A, Wurst M (2012) Multi-objective frequent termset clustering. Knowl Inf Syst 30(3):715\u2013738","journal-title":"Knowl Inf Syst"},{"key":"648_CR48","doi-asserted-by":"crossref","unstructured":"Randall K, Stata R, Wiener J, Wickremesinghe R (2002) The link database: fast access to graphs of the web. In: Proceedings of the data compression conference (DCC), Snowbird, UT, pp 122\u2013131","DOI":"10.1109\/DCC.2002.999950"},{"key":"648_CR49","unstructured":"Raman R, Raman V, Rao S (2002) Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In: Proceedings of the 13th annual ACM-SIAM symposium on discrete algorithms (SODA), San Francisco, CA, pp 233\u2013242"},{"key":"648_CR50","doi-asserted-by":"crossref","unstructured":"Saito H, Toyoda M, Kitsuregawa M, Aihara K (2007) A large-scale study of link spam detection by graph algorithms. In: Proceedings of adversarial information retrieval on the web (AIRWeb), Banff, Alberta, Canada","DOI":"10.1145\/1244408.1244417"},{"issue":"3","key":"648_CR51","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1007\/s10115-011-0396-2","volume":"30","author":"K Saito","year":"2012","unstructured":"Saito K, Kimura M, Ohara K, Motoda H (2012) Efficient discovery of influential nodes for SIS models in social networks. Knowl Inf Syst 30(3):613\u2013635","journal-title":"Knowl Inf Syst"},{"key":"648_CR52","doi-asserted-by":"crossref","unstructured":"Suel T, Yuan J (2001) Compressing the graph structure of the web. In: Proceedings of the data compression conference (DCC), Snowbird, UT, pp 213\u2013222","DOI":"10.1109\/DCC.2001.917152"},{"key":"648_CR53","doi-asserted-by":"crossref","unstructured":"Suri S, Vassilvitskii S (2011) Counting triangles and the curse of the last reducer. In: Proceedings of the 20th international conference on the world wide web (WWW), Hyderabad, India, pp 607\u2013614","DOI":"10.1145\/1963405.1963491"},{"key":"648_CR54","unstructured":"Van Dongen, S (2000) Graph clustering by flow simulation. Ph.D. Thesis, University of Utrecht, The Netherlands"},{"issue":"1","key":"648_CR55","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1137\/040608635","volume":"30","author":"S Dongen Van","year":"2008","unstructured":"Van Dongen S (2008) Graph clustering via a discrete uncoupling process. SIAM J Matrix Anal Appl 30(1):121\u2013141","journal-title":"SIAM J Matrix Anal Appl"},{"issue":"2","key":"648_CR56","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1145\/384192.384193","volume":"33","author":"J Vitter","year":"2001","unstructured":"Vitter J (2001) External memory algorithms and data structures: dealing with massive data. ACM Comput Surv 33(2):209\u2013271","journal-title":"ACM Comput Surv"},{"key":"648_CR57","doi-asserted-by":"crossref","unstructured":"Zhuge H (2009) Communities and emerging semantics in semantic link network: discovery and learning. IEEE Trans Knowl Data Eng 21(6):785\u2013799","DOI":"10.1109\/TKDE.2008.141"}],"container-title":["Knowledge and Information Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-013-0648-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10115-013-0648-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-013-0648-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,13]],"date-time":"2019-07-13T02:41:18Z","timestamp":1562985678000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10115-013-0648-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4,26]]},"references-count":57,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,8]]}},"alternative-id":["648"],"URL":"https:\/\/doi.org\/10.1007\/s10115-013-0648-4","relation":{},"ISSN":["0219-1377","0219-3116"],"issn-type":[{"value":"0219-1377","type":"print"},{"value":"0219-3116","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,4,26]]}}}