{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,26]],"date-time":"2026-04-26T07:54:02Z","timestamp":1777190042435,"version":"3.51.4"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2020,4,3]],"date-time":"2020-04-03T00:00:00Z","timestamp":1585872000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,4,3]],"date-time":"2020-04-03T00:00:00Z","timestamp":1585872000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1524312"],"award-info":[{"award-number":["CCF-1524312"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-0939370"],"award-info":[{"award-number":["CCF-0939370"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We continue building up the information theory of non-sequential data structures such as trees, sets, and graphs. In this paper, we consider dynamic graphs generated by a full duplication model in which a new vertex selects an existing vertex and copies all of its neighbors. We ask how many bits are needed to describe the labeled and unlabeled versions of such graphs. We first estimate entropies of both versions and then present asymptotically optimal compression algorithms up to two bits. Interestingly, for the full duplication model the labeled version needs<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Theta (n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>\u0398<\/mml:mi><mml:mo>(<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>bits while its unlabeled version (structure) can be described by<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Theta (\\log n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>\u0398<\/mml:mi><mml:mo>(<\/mml:mo><mml:mo>log<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>bits due to significant amount of symmetry (i.e. large average size of the automorphism group of sample graphs).<\/jats:p>","DOI":"10.1007\/s00453-020-00699-2","type":"journal-article","created":{"date-parts":[[2020,4,3]],"date-time":"2020-04-03T12:02:37Z","timestamp":1585915357000},"page":"2687-2707","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Compression of Dynamic Graphs Generated by a Duplication Model"],"prefix":"10.1007","volume":"82","author":[{"given":"Krzysztof","family":"Turowski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abram","family":"Magner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wojciech","family":"Szpankowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,4,3]]},"reference":[{"key":"699_CR1","doi-asserted-by":"crossref","unstructured":"Abbe, E.: Graph compression: the effect of clusters. In: Proceedings of the Fifty-fourth Annual Allerton Conference (2016)","DOI":"10.1109\/ALLERTON.2016.7852203"},{"key":"699_CR2","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1103\/RevModPhys.74.47","volume":"74","author":"R Albert","year":"2002","unstructured":"Albert, R., Barab\u00e1si, A.L.: Statistical mechanics of complex networks. Rev. Mod. Phys 74, 47\u201397 (2002)","journal-title":"Rev. Mod. Phys"},{"key":"699_CR3","unstructured":"Besta, M., Hoefler, T.: Survey and taxonomy of lossless graph compression and space-efficient graph representations. Preprint (2018). https:\/\/arxiv.org\/pdf\/1806.01799"},{"key":"699_CR4","doi-asserted-by":"publisher","first-page":"2447","DOI":"10.1142\/S0218127407018518","volume":"17","author":"S Boccaletti","year":"2007","unstructured":"Boccaletti, S., Hwang, D.U., Latora, V.: Growing hierarchical scale-free networks by means of nonhierarchical processes. Int. J. Bifurc. Chaos 17, 2447\u20132452 (2007)","journal-title":"Int. J. Bifurc. Chaos"},{"issue":"2","key":"699_CR5","doi-asserted-by":"publisher","first-page":"620","DOI":"10.1109\/TIT.2011.2173710","volume":"58","author":"Y Choi","year":"2012","unstructured":"Choi, Y., Szpankowski, W.: Compression of graphical structures: fundamental limits, algorithms, and experiments. IEEE Trans. Inf. Theor. 58(2), 620\u2013638 (2012). https:\/\/doi.org\/10.1109\/TIT.2011.2173710","journal-title":"IEEE Trans. Inf. Theor."},{"issue":"5","key":"699_CR6","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1089\/106652703322539024","volume":"10","author":"F Chung","year":"2003","unstructured":"Chung, F., Lu, L., Dewey, T.G., Galas, D.J.: Duplication models for biological networks. J. Comput. Biol. 10(5), 677\u2013687 (2003). https:\/\/doi.org\/10.1089\/106652703322539024","journal-title":"J. Comput. Biol."},{"key":"699_CR7","volume-title":"Elements of Information Theory","author":"T Cover","year":"2006","unstructured":"Cover, T., Thomas, J.: Elements of Information Theory, 2nd edn. Wiley, London (2006)","edition":"2"},{"key":"699_CR8","doi-asserted-by":"crossref","unstructured":"Delgosha, P., Anantharam, V.: Distributed compression of graphical data. In: 2018 IEEE International Symposium on Information Theory (ISIT), pp. 2216\u20132220 (2018)","DOI":"10.1109\/ISIT.2018.8437614"},{"key":"699_CR9","doi-asserted-by":"crossref","unstructured":"Delgosha, P., Anantharam, V.: Universal lossless compression of graphical data. In: 2017 IEEE International Symposium on Information Theory (ISIT), pp. 1578\u20131582 (2017)","DOI":"10.1109\/ISIT.2017.8006795"},{"key":"699_CR10","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316339831","volume-title":"Introduction to Random Graphs","author":"A Frieze","year":"2016","unstructured":"Frieze, A., Karo\u0144ski, M.: Introduction to Random Graphs. Cambridge University Press, Cambridge (2016)"},{"key":"699_CR11","doi-asserted-by":"publisher","unstructured":"Go\u0142ebiewski, Z., Magner, A., Szpankowski, W.: Entropy of some general plane trees. In: 2017 IEEE International Symposium on Information Theory (ISIT), pp. 301\u2013305 (2017). https:\/\/doi.org\/10.1109\/ISIT.2017.8006538","DOI":"10.1109\/ISIT.2017.8006538"},{"key":"699_CR12","doi-asserted-by":"publisher","unstructured":"Hucke, D., Lohrey, M.: Universal tree source coding using grammar-based compression. In: 2017 IEEE International Symposium on Information Theory (ISIT), pp. 1753\u20131757 (2017). https:\/\/doi.org\/10.1109\/ISIT.2017.8006830","DOI":"10.1109\/ISIT.2017.8006830"},{"key":"699_CR13","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1088\/1367-2630\/7\/1\/145","volume":"7","author":"I Ispolatov","year":"2005","unstructured":"Ispolatov, I., Krapivsky, P., Mazo, I., Yuryev, A.: Cliques and duplication-divergence network growth. New J. Phys. 7, 145 (2005)","journal-title":"New J. Phys."},{"key":"699_CR14","doi-asserted-by":"publisher","first-page":"061911","DOI":"10.1103\/PhysRevE.71.061911","volume":"71","author":"I Ispolatov","year":"2005","unstructured":"Ispolatov, I., Krapivsky, P.L., Yuryev, A.: Duplication-divergence model of protein interaction network. Phys. Rev. E 71, 061911 (2005). https:\/\/doi.org\/10.1103\/PhysRevE.71.061911","journal-title":"Phys. Rev. E"},{"key":"699_CR15","doi-asserted-by":"publisher","DOI":"10.1002\/0471715816","volume-title":"Univariate Discrete Distributions","author":"N Johnson","year":"2005","unstructured":"Johnson, N., Kemp, A., Kotz, S.: Univariate Discrete Distributions. Wiley, London (2005)"},{"key":"699_CR16","doi-asserted-by":"publisher","first-page":"055101","DOI":"10.1103\/PhysRevE.66.055101","volume":"66","author":"J Kim","year":"2002","unstructured":"Kim, J., Krapivsky, P.L., Kahng, B., Redner, S.: Infinite-order percolation and giant fluctuations in a protein interaction network. Phys. Rev. E 66, 055101 (2002). https:\/\/doi.org\/10.1103\/PhysRevE.66.055101","journal-title":"Phys. Rev. E"},{"key":"699_CR17","doi-asserted-by":"crossref","unstructured":"\u0141uczak, T., Magner, A., Szpankowski, W.: Asymmetry and structural information in preferential attachment graphs. Random Struct. Algorithms (2019)","DOI":"10.1109\/ISIT.2019.8849739"},{"key":"699_CR18","doi-asserted-by":"crossref","unstructured":"Magner, A., Turowski, K., Szpankowski, W.: Lossless compression of binary trees with correlated vertex names. Trans. Inf. Theory 64 (2018)","DOI":"10.1109\/TIT.2018.2851224"},{"key":"699_CR19","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001","volume-title":"Networks: An Introduction","author":"M Newman","year":"2010","unstructured":"Newman, M.: Networks: An Introduction. Oxford University Press, Oxford (2010)"},{"issue":"2","key":"699_CR20","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/S0022-5193(03)00028-6","volume":"222","author":"R Pastor-Satorras","year":"2003","unstructured":"Pastor-Satorras, R., Smith, E., Sol\u00e9, R.: Evolving protein interaction networks through gene duplication. J. Theor. Biol. 222(2), 199\u2013210 (2003). https:\/\/doi.org\/10.1016\/S0022-5193(03)00028-6","journal-title":"J. Theor. Biol."},{"key":"699_CR21","doi-asserted-by":"publisher","first-page":"066119","DOI":"10.1103\/PhysRevE.68.066119","volume":"68","author":"A Raval","year":"2003","unstructured":"Raval, A.: Some asymptotic properties of duplication graphs. Phys. Rev. E 68, 066119 (2003)","journal-title":"Phys. Rev. E"},{"issue":"5","key":"699_CR22","doi-asserted-by":"publisher","first-page":"823","DOI":"10.1093\/bib\/bbt014","volume":"15","author":"M Shao","year":"2014","unstructured":"Shao, M., Yang, Y., Guan, J., Zhou, S.: Choosing appropriate models for protein-protein interaction networks: a comparison study. Brief. Bioinform. 15(5), 823\u2013838 (2014). https:\/\/doi.org\/10.1093\/bib\/bbt014","journal-title":"Brief. Bioinform."},{"issue":"5","key":"699_CR23","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1002\/asi.4630270505","volume":"27","author":"PDD Solla","year":"1976","unstructured":"Solla, P.D.D.: A general theory of bibliometric and other cumulative advantage processes. J. Am. Soc. Inf. Sci. 27(5), 292\u2013306 (1976). https:\/\/doi.org\/10.1002\/asi.4630270505","journal-title":"J. Am. Soc. Inf. Sci."},{"key":"699_CR24","doi-asserted-by":"crossref","DOI":"10.1017\/9781316779422","volume-title":"Random Graphs and Complex Networks","author":"R van der Hofstad","year":"2016","unstructured":"van der Hofstad, R.: Random Graphs and Complex Networks, vol. 1. Cambridge University Press, Cambridge (2016)"},{"issue":"1","key":"699_CR25","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1159\/000067642","volume":"1","author":"A V\u00e1zquez","year":"2003","unstructured":"V\u00e1zquez, A., Flammini, A., Maritan, A., Vespignani, A.: Modeling of protein interaction networks. Complexus 1(1), 38\u201344 (2003)","journal-title":"Complexus"},{"issue":"3","key":"699_CR26","doi-asserted-by":"publisher","first-page":"1373","DOI":"10.1109\/TIT.2013.2295392","volume":"60","author":"J Zhang","year":"2014","unstructured":"Zhang, J., Yang, E.H., Kieffer, J.C.: A universal grammar-based code for lossless compression of binary trees. IEEE Trans. Inf. Theory 60(3), 1373\u20131386 (2014). https:\/\/doi.org\/10.1109\/TIT.2013.2295392","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00699-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00699-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00699-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,20]],"date-time":"2022-10-20T14:06:49Z","timestamp":1666274809000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00699-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,3]]},"references-count":26,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["699"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00699-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,3]]},"assertion":[{"value":"9 October 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 March 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 April 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}