{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:40:21Z","timestamp":1740109221890,"version":"3.37.3"},"reference-count":95,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,2,19]],"date-time":"2022-02-19T00:00:00Z","timestamp":1645228800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,2,19]],"date-time":"2022-02-19T00:00:00Z","timestamp":1645228800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Royal Society Wolfson Research Merit Award","award":["WRM\/R1\/180014"],"award-info":[{"award-number":["WRM\/R1\/180014"]}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/L01503X\/1"],"award-info":[{"award-number":["EP\/L01503X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62002236"],"award-info":[{"award-number":["62002236"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2023,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper proposes a scheme to reduce big graphs to small graphs. It contracts obsolete parts and regular structures into supernodes. The supernodes carry a synopsis <jats:inline-formula><jats:alternatives><jats:tex-math>$$S_\\mathcal {Q}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>S<\/mml:mi>\n                    <mml:mi>Q<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for each query class <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {Q}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>Q<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> in use, to abstract key features of the contracted parts for answering queries of <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {Q}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>Q<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Moreover, for various types of graphs, we identify regular structures to contract. The contraction scheme provides a compact graph representation and prioritizes up-to-date data. Better still, it is generic and lossless. We show that the same contracted graph is able to support multiple query classes at the same time, no matter whether their queries are label based or not, local or non-local. Moreover, existing algorithms for these queries can be readily adapted to compute exact answers by using the synopses when possible and decontracting the supernodes only when necessary. As a proof of concept, we show how to adapt existing algorithms for subgraph isomorphism, triangle counting, shortest distance, connected component and clique decision to contracted graphs. We also provide a bounded incremental contraction algorithm in response to updates, such that its cost is determined by the size of areas affected by the updates alone, not by the entire graphs. We experimentally verify that on average, the contraction scheme reduces graphs by 71.9% and improves the evaluation of these queries by 1.69, 1.44, 1.47, 2.24 and 1.37 times, respectively.<\/jats:p>","DOI":"10.1007\/s00778-022-00731-7","type":"journal-article","created":{"date-parts":[[2022,2,19]],"date-time":"2022-02-19T05:05:21Z","timestamp":1645247121000},"page":"49-73","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Making graphs compact by lossless contraction"],"prefix":"10.1007","volume":"32","author":[{"given":"Wenfei","family":"Fan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7501-4007","authenticated-orcid":false,"given":"Yuanhao","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Muyang","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Can","family":"Lu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,2,19]]},"reference":[{"key":"731_CR1","unstructured":"Traffic. http:\/\/www.dis.uniroma1.it\/challenge9\/download.html (2006)"},{"key":"731_CR2","unstructured":"DBLP. https:\/\/snap.stanford.edu\/data\/com-DBLP.html (2012)"},{"key":"731_CR3","unstructured":"Gsh host. http:\/\/law.di.unimi.it\/webdata\/gsh-2015-host (2015)"},{"key":"731_CR4","doi-asserted-by":"crossref","unstructured":"Akiba, T., Iwata, Y., Yoshida, Y.: Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In: SIGMOD (2013)","DOI":"10.1145\/2463676.2465315"},{"key":"731_CR5","doi-asserted-by":"crossref","unstructured":"Albert, R., Jeong, H., Barab\u00e1si, A.: The diameter of the World Wide Web. CoRR cond-mat\/9907038 (1999)","DOI":"10.1038\/43601"},{"key":"731_CR6","doi-asserted-by":"crossref","unstructured":"Angles, R., Arenas, M., Barcel\u00f3, P., Boncz, P.A., Fletcher, G.H.L., Gutierrez, C., Lindaaker, T., Paradies, M., Plantikow, S., Sequeda, J.F., van Rest, O., Voigt, H.: G-CORE: A core for future graph query languages. In: SIGMOD, pp. 1421\u20131432 (2018)","DOI":"10.1145\/3183713.3190654"},{"key":"731_CR7","doi-asserted-by":"crossref","unstructured":"Anirban, S., Wang, J., Islam, M.S.: Multi-level graph compression for fast reachability detection. In: DASFAA (2019)","DOI":"10.1007\/978-3-030-18579-4_14"},{"issue":"3","key":"731_CR8","doi-asserted-by":"publisher","first-page":"1031","DOI":"10.3390\/a2031031","volume":"2","author":"A Apostolico","year":"2009","unstructured":"Apostolico, A., Drovandi, G.: Graph compression by bfs. Algorithms 2(3), 1031\u20131044 (2009)","journal-title":"Algorithms"},{"key":"731_CR9","doi-asserted-by":"crossref","unstructured":"Backstrom, L., Huttenlocher, D., Kleinberg, J., Lan, X.: Group formation in large social networks: membership, growth, and evolution. In: SIGKDD, pp. 44\u201354 (2006)","DOI":"10.1145\/1150402.1150412"},{"issue":"3","key":"731_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2992785","volume":"11","author":"SH Bae","year":"2017","unstructured":"Bae, S.H., Halperin, D., West, J.D., Rosvall, M., Howe, B.: Scalable and efficient flow-based community detection for large-scale graph analysis. TKDD 11(3), 1\u201330 (2017)","journal-title":"TKDD"},{"key":"731_CR11","unstructured":"Berry, N., Ko, T., Moy, T., Smrcka, J., Turnley, J., Wu, B.: Emergent clique formation in terrorist recruitment. In: AAAI Workshop on Agent Organizations (2004)"},{"key":"731_CR12","unstructured":"Besta, M., Hoefler, T.: Survey and taxonomy of lossless graph compression and space-efficient graph representations. CoRR arXiv: 1806.01799 (2018)"},{"key":"731_CR13","doi-asserted-by":"crossref","unstructured":"Bhattarai, B., Liu, H., Huang, H.H.: CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching. In: SIGMOD (2019)","DOI":"10.1145\/3299869.3300086"},{"key":"731_CR14","doi-asserted-by":"crossref","unstructured":"Bi, F., Chang, L., Lin, X., Qin, L., Zhang, W.: Efficient subgraph matching by postponing cartesian products. In: SIGMOD (2016)","DOI":"10.1145\/2882903.2915236"},{"key":"731_CR15","doi-asserted-by":"crossref","unstructured":"Boldi, P., Vigna, S.: The WebGraph framework I: Compression techniques. In: WWW, pp. 595\u2013602 (2004)","DOI":"10.1145\/988672.988752"},{"issue":"5","key":"731_CR16","doi-asserted-by":"publisher","first-page":"1170","DOI":"10.1086\/228631","volume":"92","author":"P Bonacich","year":"1987","unstructured":"Bonacich, P.: Power and centrality: a family of measures. Am. J. Sociol. 92(5), 1170\u20131182 (1987)","journal-title":"Am. J. Sociol."},{"key":"731_CR17","doi-asserted-by":"crossref","unstructured":"Bourse, F., Lelarge, M., Vojnovic, M.: Balanced graph edge partition. In: SIGKDD, pp. 1456\u20131465 (2014)","DOI":"10.1145\/2623330.2623660"},{"issue":"2","key":"731_CR18","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1080\/0022250X.2001.9990249","volume":"25","author":"U Brandes","year":"2001","unstructured":"Brandes, U.: A faster algorithm for betweenness centrality. J. Math. Sociol. 25(2), 163\u2013177 (2001)","journal-title":"J. Math. Sociol."},{"key":"731_CR19","doi-asserted-by":"crossref","unstructured":"Bringmann, B., Nijssen, S.: What is frequent in a single graph? In: Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp. 858\u2013863 (2008)","DOI":"10.1007\/978-3-540-68125-0_84"},{"issue":"9","key":"731_CR20","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1145\/362342.362367","volume":"16","author":"C Bron","year":"1973","unstructured":"Bron, C., Kerbosch, J.: Algorithm 457: finding all cliques of an undirected graph. CACM 16(9), 575\u2013577 (1973)","journal-title":"CACM"},{"key":"731_CR21","doi-asserted-by":"crossref","unstructured":"Buehrer, G., Chellapilla, K.: A scalable pattern mining approach to web graph compression with communities. In: WSDM, pp. 95\u2013106 (2008)","DOI":"10.1145\/1341531.1341547"},{"issue":"4","key":"731_CR22","first-page":"535","volume":"17","author":"D Cantone","year":"2005","unstructured":"Cantone, D., Ferro, A., Pulvirenti, A., Recupero, D.R., Shasha, D.: Antipole tree indexing to support range search and k-nearest neighbor search in metric spaces. TKDE 17(4), 535\u2013550 (2005)","journal-title":"TKDE"},{"key":"731_CR23","doi-asserted-by":"crossref","unstructured":"Cheng, J., Huang, S., Wu, H., Fu, A.W.C.: TF-label: a topological-folding labeling scheme for reachability querying in a large graph. In: SIGMOD (2013)","DOI":"10.1145\/2463676.2465286"},{"key":"731_CR24","doi-asserted-by":"crossref","unstructured":"Chierichetti, F., Kumar, R., Lattanzi, S., Mitzenmacher, M., Panconesi, A., Raghavan, P.: On compressing social networks. In: SIGKDD, pp. 219\u2013228 (2009)","DOI":"10.1145\/1557019.1557049"},{"key":"731_CR25","doi-asserted-by":"crossref","unstructured":"Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. SICOMP 32(5) (2003)","DOI":"10.1137\/S0097539702403098"},{"key":"731_CR26","unstructured":"Cohen, J.: Trusses: Cohesive subgraphs for social network analysis. Natl. Secur. Agency Tech. Rep. 16(3.1) (2008)"},{"key":"731_CR27","doi-asserted-by":"crossref","unstructured":"Cohen, S.: Data management for social networking. In: SIGMOD (2016)","DOI":"10.1145\/2902251.2902306"},{"issue":"10","key":"731_CR28","doi-asserted-by":"publisher","first-page":"1367","DOI":"10.1109\/TPAMI.2004.75","volume":"26","author":"LP Cordella","year":"2004","unstructured":"Cordella, L.P., Foggia, P., Sansone, C., Vento, M.: A (sub) graph isomorphism algorithm for matching large graphs. TPAMI 26(10), 1367\u20131372 (2004)","journal-title":"TPAMI"},{"key":"731_CR29","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to algorithms. MIT press (2009)"},{"key":"731_CR30","doi-asserted-by":"crossref","unstructured":"Cortes, C., Pregibon, D., Volinsky, C.: Communities of interest. In: IDA (2001)","DOI":"10.1007\/3-540-44816-0_11"},{"key":"731_CR31","doi-asserted-by":"crossref","unstructured":"Dijkstra, E.W., et\u00a0al.: A note on two problems in connexion with graphs. Numer. Math. 1(1) (1959)","DOI":"10.1007\/BF01386390"},{"key":"731_CR32","doi-asserted-by":"crossref","unstructured":"Dominguez-Sal, D., Martinez-Bazan, N., Muntes-Mulero, V., Baleta, P., Larriba-Pey, J.L.: A discussion on the design of graph database benchmarks. In: TPCTC, pp. 25\u201340 (2010)","DOI":"10.1007\/978-3-642-18206-8_3"},{"issue":"7","key":"731_CR33","first-page":"517","volume":"7","author":"M Elseidy","year":"2014","unstructured":"Elseidy, M., Abdelhamid, E., Skiadopoulos, S., Kalnis, P.: GRAMI: frequent subgraph and pattern mining in a single large graph. PVLDB 7(7), 517\u2013528 (2014)","journal-title":"PVLDB"},{"key":"731_CR34","doi-asserted-by":"crossref","unstructured":"Fairey, J., Holder, L.: Stariso: Graph isomorphism through lossy compression. In: DCC (2016)","DOI":"10.1109\/DCC.2016.96"},{"key":"731_CR35","doi-asserted-by":"crossref","unstructured":"Fan, W., Hu, C., Tian, C.: Incremental graph computations: Doable and undoable. In: SIGMOD (2017)","DOI":"10.1145\/3035918.3035944"},{"key":"731_CR36","doi-asserted-by":"crossref","unstructured":"Fan, W., Jin, R., Liu, M., Lu, P., Tian, C., Zhou, J.: Capturing associations in graphs. PVLDB 13(11) (2020)","DOI":"10.14778\/3407790.3407795"},{"key":"731_CR37","doi-asserted-by":"crossref","unstructured":"Fan, W., Li, J., Wang, X., Wu, Y.: Query preserving graph compression. In: SIGMOD (2012)","DOI":"10.1145\/2213836.2213855"},{"key":"731_CR38","doi-asserted-by":"crossref","unstructured":"Fan, W., Li, Y., Liu, M., Lu, C.: Making graphs compact by lossless contraction (2021). SIGMOD","DOI":"10.1007\/s00778-022-00731-7"},{"key":"731_CR39","doi-asserted-by":"crossref","unstructured":"Fan, W., Wu, Y., Xu, J.: Functional dependencies for graphs. In: SIGMOD (2016)","DOI":"10.1145\/2882903.2915232"},{"key":"731_CR40","doi-asserted-by":"crossref","unstructured":"Francis, N., Green, A., Guagliardo, P., Libkin, L., Lindaaker, T., Marsault, V., Plantikow, S., Rydberg, M., Selmer, P., Taylor, A.: Cypher: An evolving query language for property graphs. In: SIGMOD (2018)","DOI":"10.1145\/3183713.3190657"},{"key":"731_CR41","doi-asserted-by":"crossref","unstructured":"Gabow, H.N., Galil, Z., Spencer, T.H.: Efficient implementation of graph algorithms using contraction. In: FOCS (1984)","DOI":"10.1109\/SFCS.1984.715935"},{"key":"731_CR42","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)"},{"key":"731_CR43","volume-title":"Graph Theory and its Applications","author":"J Gross","year":"1998","unstructured":"Gross, J., Yellen, J.: Graph Theory and its Applications. CRC Press, Boca Raton (1998)"},{"key":"731_CR44","unstructured":"Han, W.S., Lee, J., Lee, J.H.: Turbo$$_{\\rm iso}$$: Towards ultrafast and robust subgraph isomorphism search in large graph databases. In: SIGMOD (2013)"},{"key":"731_CR45","doi-asserted-by":"crossref","unstructured":"He, L., Chao, Y., Suzuki, K., Wu, K.: Fast connected-component labeling. Pattern Recogn. 42(9) (2009)","DOI":"10.1016\/j.patcog.2008.10.013"},{"issue":"3","key":"731_CR46","doi-asserted-by":"publisher","first-page":"584","DOI":"10.1198\/106186006X139162","volume":"15","author":"S Hill","year":"2006","unstructured":"Hill, S., Agarwal, D.K., Bell, R., Volinsky, C.: Building an effective representation for dynamic networks. J. Comput. Graph. Stat. 15(3), 584\u2013608 (2006)","journal-title":"J. Comput. Graph. Stat."},{"key":"731_CR47","doi-asserted-by":"crossref","unstructured":"Hu, X., Tao, Y., Chung, C.W.: Massive graph triangulation. In: SIGMOD (2013)","DOI":"10.1145\/2463676.2463704"},{"issue":"4","key":"731_CR48","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/0207033","volume":"7","author":"A Itai","year":"1978","unstructured":"Itai, A., Rodeh, M.: Finding a minimum circuit in a graph. SICOMP 7(4), 413\u2013423 (1978)","journal-title":"SICOMP"},{"key":"731_CR49","unstructured":"Jaakkola, M.S.T., Szummer, M.: Partially labeled classification with markov random walks. NIPS 14 (2002)"},{"key":"731_CR50","doi-asserted-by":"crossref","unstructured":"Jin, R., Xiang, Y., Ruan, N., Wang, H.: Efficiently answering reachability queries on very large directed graphs. In: SIGMOD (2008)","DOI":"10.1145\/1376616.1376677"},{"issue":"1","key":"731_CR51","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/sdata.2016.35","volume":"3","author":"AE Johnson","year":"2016","unstructured":"Johnson, A.E., Pollard, T.J., Shen, L., Li-Wei, H.L., Feng, M., Ghassemi, M., Moody, B., Szolovits, P., Celi, L.A., Mark, R.G.: MIMIC-III, a freely accessible critical care database. Sci. Data 3(1), 1\u20139 (2016)","journal-title":"Sci. Data"},{"key":"731_CR52","doi-asserted-by":"crossref","unstructured":"Kang, U., Faloutsos, C.: Beyond\u2019caveman communities\u2019: Hubs and spokes for graph compression and mining. In: ICDM, pp. 300\u2013309 (2011)","DOI":"10.1109\/ICDM.2011.26"},{"key":"731_CR53","doi-asserted-by":"crossref","unstructured":"Kang, U., McGlohon, M., Akoglu, L., Faloutsos, C.: Patterns on the connected components of terabyte-scale graphs. In: ICDM, pp. 875\u2013880 (2010)","DOI":"10.1109\/ICDM.2010.121"},{"key":"731_CR54","doi-asserted-by":"crossref","unstructured":"Karimi, R., Koppelman, D.M., Michael, C.J.: GPU road network graph contraction and SSSP query. In: ICS (2019)","DOI":"10.1145\/3330345.3330368"},{"issue":"1","key":"731_CR55","first-page":"96","volume":"48","author":"G Karypis","year":"1998","unstructured":"Karypis, G., Kumar, V.: Multilevelk-way partitioning scheme for irregular graphs. JPDC 48(1), 96\u2013129 (1998)","journal-title":"JPDC"},{"key":"731_CR56","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J., Tardos, \u00c9.: Maximizing the spread of influence through a social network. In: SIGKDD, pp. 137\u2013146 (2003)","DOI":"10.1145\/956750.956769"},{"issue":"1\u20132","key":"731_CR57","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(00)00286-3","volume":"250","author":"I Koch","year":"2001","unstructured":"Koch, I.: Enumerating all connected maximal common subgraphs in two graphs. TCS 250(1\u20132), 1\u201330 (2001)","journal-title":"TCS"},{"key":"731_CR58","doi-asserted-by":"crossref","unstructured":"Kropatsch, W.: Building irregular pyramids by dual-graph contraction. In: Vision Image and Signal Processing (1996)","DOI":"10.1049\/ip-vis:19952115"},{"key":"731_CR59","doi-asserted-by":"crossref","unstructured":"Lappas, T., Liu, K., Terzi, E.: Finding a team of experts in social networks. In: KDD (2009)","DOI":"10.1145\/1557019.1557074"},{"key":"731_CR60","doi-asserted-by":"crossref","unstructured":"LeFevre, K., Terzi, E.: Grass: Graph structure summarization. In: SDM (2010)","DOI":"10.1137\/1.9781611972801.40"},{"issue":"2","key":"731_CR61","doi-asserted-by":"publisher","first-page":"167","DOI":"10.3233\/SW-140134","volume":"6","author":"J Lehmann","year":"2015","unstructured":"Lehmann, J., Isele, R., Jakob, M., Jentzsch, A., Kontokostas, D., Mendes, P.N., Hellmann, S., Morsey, M., van Kleef, P., Auer, S., Bizer, C.: DBpedia - A large-scale, multilingual knowledge base extracted from Wikipedia. Semantic Web 6(2), 167\u2013195 (2015)","journal-title":"Semantic Web"},{"key":"731_CR62","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Huttenlocher, D., Kleinberg, J.: Predicting positive and negative links in online social networks. In: WWW, pp. 641\u2013650 (2010)","DOI":"10.1145\/1772690.1772756"},{"key":"731_CR63","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Kleinberg, J.M., Faloutsos, C.: Graphs over time: densification laws, shrinking diameters and possible explanations. In: SIGKDD (2005)","DOI":"10.1145\/1081870.1081893"},{"key":"731_CR64","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Lang, K.J., Dasgupta, A., Mahoney, M.W.: Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. CoRR arXiv:0810.1355 (2008)","DOI":"10.1080\/15427951.2009.10129177"},{"key":"731_CR65","unstructured":"Leung, K., Leckie, C.: Unsupervised anomaly detection in network intrusion detection using clusters. In: ACSW (2005)"},{"key":"731_CR66","doi-asserted-by":"crossref","unstructured":"Liang, Y., Zhao, P.: Similarity search in graph databases: a multi-layered indexing approach. In: ICDE (2017)","DOI":"10.1109\/ICDE.2017.129"},{"issue":"3","key":"731_CR67","first-page":"62:1","volume":"51","author":"Y Liu","year":"2018","unstructured":"Liu, Y., Safavi, T., Dighe, A., Koutra, D.: Graph summarization methods and applications: A survey. ACM Comput. Surv. 51(3), 62:1-62:34 (2018)","journal-title":"ACM Comput. Surv."},{"key":"731_CR68","doi-asserted-by":"crossref","unstructured":"Lu, C., Yu, J.X., Wei, H., Zhang, Y.: Finding the maximum clique in massive graphs. PVLDB 10(11) (2017)","DOI":"10.14778\/3137628.3137660"},{"key":"731_CR69","doi-asserted-by":"crossref","unstructured":"Maccioni, A., Abadi, D.J.: Scalable pattern matching over compressed graphs via dedensification. In: SIGKDD (2016)","DOI":"10.1145\/2939672.2939856"},{"key":"731_CR70","unstructured":"McAuley, J., Leskovec, J.: Learning to discover social circles in ego networks. In: NIPS (2012)"},{"issue":"11","key":"731_CR71","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1145\/219717.219748","volume":"38","author":"GA Miller","year":"1995","unstructured":"Miller, G.A.: WordNet: a lexical database for English. Commun. ACM 38(11), 39\u201341 (1995)","journal-title":"Commun. ACM"},{"key":"731_CR72","unstructured":"Myoungji, H., Hyunjoon, K., Geonmo, G., Kunsoo, P., Wook-Shin, H.: Efficient subgraph matching: harmonizing dynamic programming, adaptive matching order, and failing set together. In: SIGMOD (2019)"},{"key":"731_CR73","doi-asserted-by":"crossref","unstructured":"Navlakha, S., Rastogi, R., Shrivastava, N.: Graph summarization with bounded error. In: SIGMOD (2008)","DOI":"10.1145\/1376616.1376661"},{"issue":"suppl 1","key":"731_CR74","doi-asserted-by":"publisher","first-page":"2566","DOI":"10.1073\/pnas.012582999","volume":"99","author":"ME Newman","year":"2002","unstructured":"Newman, M.E., Watts, D.J., Strogatz, S.H.: Random graph models of social networks. PNAS 99(suppl 1), 2566\u20132572 (2002)","journal-title":"PNAS"},{"key":"731_CR75","doi-asserted-by":"crossref","unstructured":"Pandey, S., Li, X.S., Buluc, A., Xu, J., Liu, H.: H-index: Hash-indexing for parallel triangle counting on GPUs. In: HPCS, pp. 1\u20137 (2019)","DOI":"10.1109\/HPEC.2019.8916492"},{"key":"731_CR76","doi-asserted-by":"crossref","unstructured":"Papadopoulos, S., Kompatsiaris, Y., Vakali, A., Spyridonos, P.: Community detection in social media. Data Min. Knowl. Discov. 24 (2012)","DOI":"10.1007\/s10618-011-0224-z"},{"issue":"1\u20132","key":"731_CR77","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0304-3975(95)00079-8","volume":"158","author":"G Ramalingam","year":"1996","unstructured":"Ramalingam, G., Reps, T.: On the computational complexity of dynamic graph problems. TCS 158(1\u20132), 233\u2013277 (1996)","journal-title":"TCS"},{"issue":"5","key":"731_CR78","first-page":"617","volume":"8","author":"X Ren","year":"2015","unstructured":"Ren, X., Wang, J.: Exploiting vertex relationships in speeding up subgraph isomorphism over large graphs. PVLDB 8(5), 617\u2013628 (2015)","journal-title":"PVLDB"},{"key":"731_CR79","doi-asserted-by":"crossref","unstructured":"van Rest, O., Hong, S., Kim, J., Meng, X., Chafi, H.: PGQL: A property graph query language. In: GRADES (2016)","DOI":"10.1145\/2960414.2960421"},{"key":"731_CR80","doi-asserted-by":"crossref","unstructured":"Rossi, R.A., Ahmed, N.K.: The network data repository with interactive graph analytics and visualization. In: AAAI (2015)","DOI":"10.1609\/aaai.v29i1.9277"},{"issue":"2","key":"731_CR81","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1108\/17440081011053104","volume":"6","author":"S Sakr","year":"2010","unstructured":"Sakr, S., Al-Naymat, G.: Graph indexing and querying: a review. IJWIS 6(2), 101\u2013120 (2010)","journal-title":"IJWIS"},{"key":"731_CR82","doi-asserted-by":"crossref","unstructured":"Sha, M., Li, Y., Tan, K.: Gpu-based graph traversal on compressed graphs. In: SIGMOD, pp. 775\u2013792 (2019)","DOI":"10.1145\/3299869.3319871"},{"issue":"6","key":"731_CR83","first-page":"1427","volume":"12","author":"Z Shen","year":"2006","unstructured":"Shen, Z., Ma, K.L., Eliassi-Rad, T.: Visual analysis of large heterogeneous social networks by semantic and structural abstraction. TVCG 12(6), 1427\u20131439 (2006)","journal-title":"TVCG"},{"key":"731_CR84","doi-asserted-by":"crossref","unstructured":"Soundarajan, S., Tamersoy, A., Khalil, E.B., Eliassi-Rad, T., Chau, D.H., Gallagher, B., Roundy, K.: Generating graph snapshots from streaming edge data. In: WWW (2016)","DOI":"10.1145\/2872518.2889398"},{"issue":"2","key":"731_CR85","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R Tarjan","year":"1972","unstructured":"Tarjan, R.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146\u2013160 (1972)","journal-title":"SIAM J. Comput."},{"key":"731_CR86","doi-asserted-by":"crossref","unstructured":"Tian, Y., Balmin, A., Corsten, S.A., Tatikonda, S., McPherson, J.: From\u201c think like a vertex\u201d to\u201c think like a graph\u201d. PVLDB 7(3), 193\u2013204 (2013)","DOI":"10.14778\/2732232.2732238"},{"key":"731_CR87","doi-asserted-by":"crossref","unstructured":"Tian, Y., Hankins, R.A., Patel, J.M.: Efficient aggregation for graph summarization. In: SIGMOD (2008)","DOI":"10.1145\/1376616.1376675"},{"issue":"8","key":"731_CR88","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1145\/79173.79181","volume":"33","author":"LG Valiant","year":"1990","unstructured":"Valiant, L.G.: A bridging model for parallel computation. CACM 33(8), 103\u2013111 (1990)","journal-title":"CACM"},{"key":"731_CR89","doi-asserted-by":"crossref","unstructured":"Vieira, M.V., Fonseca, B.M., Damazio, R., Golgher, P.B., Reis, D.d.C., Ribeiro-Neto, B.: Efficient search ranking in social networks. In: CIKM (2007)","DOI":"10.1145\/1321440.1321520"},{"key":"731_CR90","unstructured":"W3C Recommendation: SPARQL query language for RDF. https:\/\/www.w3.org\/TR\/rdf-sparql-query\/ (2008)"},{"issue":"6684","key":"731_CR91","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"DJ Watts","year":"1998","unstructured":"Watts, D.J., Strogatz, S.H.: Collective dynamics of \u2018small-world\u2019networks. Nature 393(6684), 440 (1998)","journal-title":"Nature"},{"issue":"5","key":"731_CR92","first-page":"1160","volume":"28","author":"Y Wu","year":"2016","unstructured":"Wu, Y., Jin, R., Zhang, X.: Efficient and exact local search for random walk based top-k proximity query in large graphs. TKDE 28(5), 1160\u20131174 (2016)","journal-title":"TKDE"},{"issue":"1","key":"731_CR93","first-page":"710","volume":"1","author":"SA Yahia","year":"2008","unstructured":"Yahia, S.A., Benedikt, M., Lakshmanan, L.V., Stoyanovich, J.: Efficient network aware search in collaborative tagging sites. PVLDB 1(1), 710\u2013721 (2008)","journal-title":"PVLDB"},{"key":"731_CR94","doi-asserted-by":"crossref","unstructured":"Yang, J., Leskovec, J.: Defining and evaluating network communities based on ground-truth. In: ICDM (2012)","DOI":"10.1145\/2350190.2350193"},{"key":"731_CR95","doi-asserted-by":"crossref","unstructured":"Yildirim, H., Chaoji, V., Zaki, M.J.: Grail: Scalable reachability index for large graphs. PVLDB 3(1-2) (2010)","DOI":"10.14778\/1920841.1920879"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-022-00731-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-022-00731-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-022-00731-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,17]],"date-time":"2023-01-17T11:09:14Z","timestamp":1673953754000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-022-00731-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,19]]},"references-count":95,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["731"],"URL":"https:\/\/doi.org\/10.1007\/s00778-022-00731-7","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"type":"print","value":"1066-8888"},{"type":"electronic","value":"0949-877X"}],"subject":[],"published":{"date-parts":[[2022,2,19]]},"assertion":[{"value":"4 April 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 September 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 December 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 February 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}