{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T09:14:47Z","timestamp":1768468487915,"version":"3.49.0"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,9,9]],"date-time":"2020-09-09T00:00:00Z","timestamp":1599609600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,9,9]],"date-time":"2020-09-09T00:00:00Z","timestamp":1599609600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001717","name":"Leiden University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001717","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Min Knowl Disc"],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Many real-world phenomena can be represented as dynamic graphs, i.e., networks that change over time. The problem of dynamic graph summarization, i.e., to succinctly describe the evolution of a dynamic graph, has been widely studied. Existing methods typically use objective measures to find fixed structures such as cliques, stars, and cores. Most of the methods, however, do not consider the problem of <jats:italic>online<\/jats:italic> summarization, where the summary is incrementally conveyed to the analyst as the graph evolves, and (thus) do not take into account the knowledge of the analyst at a specific moment in time. We address this gap in the literature through a novel, generic framework for subjective interestingness for sequential data. Specifically, we iteratively identify atomic changes, called \u2018actions\u2019, that provide most information relative to the current knowledge of the analyst. For this, we introduce a novel <jats:italic>information gain<\/jats:italic> measure, which is motivated by the minimum description length (MDL) principle. With this measure, our approach discovers compact summaries without having to decide on the number of patterns. As such, we are the first to combine approaches for data mining based on subjective interestingness (using the maximum entropy principle) with pattern-based summarization (using the MDL principle). We instantiate this framework for dynamic graphs and dense subgraph patterns, and present DSSG, a heuristic algorithm for the online summarization of dynamic graphs by means of informative actions, each of which represents an interpretable change to the connectivity structure of the graph. The experiments on real-world data demonstrate that our approach effectively discovers informative summaries. We conclude with a case study on data from an airline network to show its potential for real-world applications.<\/jats:p>","DOI":"10.1007\/s10618-020-00714-8","type":"journal-article","created":{"date-parts":[[2020,9,10]],"date-time":"2020-09-10T11:42:31Z","timestamp":1599738151000},"page":"88-126","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Online summarization of dynamic graphs using subjective interestingness for sequential data"],"prefix":"10.1007","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3014-0306","authenticated-orcid":false,"given":"Sarang","family":"Kapoor","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7809-7744","authenticated-orcid":false,"given":"Dhish Kumar","family":"Saxena","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0510-3549","authenticated-orcid":false,"given":"Matthijs","family":"van Leeuwen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,9,9]]},"reference":[{"key":"714_CR1","doi-asserted-by":"crossref","unstructured":"Abello J, Resende MG, Sudarsky S (2002) Massive quasi-clique detection. In: Latin American symposium on theoretical informatics, Springer, pp 598\u2013612","DOI":"10.1007\/3-540-45995-2_51"},{"key":"714_CR2","doi-asserted-by":"crossref","unstructured":"Adhikari B, Zhang Y, Bharadwaj A, Prakash BA (2017) Condensing temporal networks using propagation. In: Proceedings of the 2017 SIAM international conference on data mining. SIAM, pp 417\u2013425","DOI":"10.1137\/1.9781611974973.47"},{"issue":"3","key":"714_CR3","doi-asserted-by":"publisher","first-page":"603","DOI":"10.1007\/s10115-012-0537-2","volume":"33","author":"R Ahmed","year":"2012","unstructured":"Ahmed R, Karypis G (2012) Algorithms for mining the evolution of conserved relational states in dynamic networks. Knowl Inf Syst 33(3):603\u2013630","journal-title":"Knowl Inf Syst"},{"issue":"1","key":"714_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2733380","volume":"10","author":"R Ahmed","year":"2015","unstructured":"Ahmed R, Karypis G (2015) Algorithms for mining the coevolving relational motifs in dynamic networks. ACM Trans Knowl Discov Data (TKDD) 10(1):1\u201331","journal-title":"ACM Trans Knowl Discov Data (TKDD)"},{"issue":"1\u20133","key":"714_CR5","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0166-218X(98)00083-3","volume":"90","author":"CJ Alpert","year":"1999","unstructured":"Alpert CJ, Kahng AB, Yao SZ (1999) Spectral partitioning with multiple eigenvectors. Discrete Appl Math 90(1\u20133):3\u201326","journal-title":"Discrete Appl Math"},{"key":"714_CR6","doi-asserted-by":"crossref","unstructured":"Araujo M, Papadimitriou S, G\u00fcnnemann S, Faloutsos C, Basu P, Swami A, Papalexakis EE, Koutra D (2014) Com2: fast automatic discovery of temporal (\u2018comet\u2019) communities. In: Pacific-Asia conference on knowledge discovery and data mining. Springer, pp 271\u2013283","DOI":"10.1007\/978-3-319-06605-9_23"},{"key":"714_CR7","doi-asserted-by":"publisher","DOI":"10.4324\/9781315566474","volume-title":"Airline operations and scheduling","author":"M Bazargan","year":"2016","unstructured":"Bazargan M (2016) Airline operations and scheduling. Routledge, London"},{"issue":"2","key":"714_CR8","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/s10618-019-00664-w","volume":"34","author":"A Bendimerad","year":"2020","unstructured":"Bendimerad A, Mel A, Lijffijt J, Plantevit M, Robardet C, De Bie T (2020) Sias-miner: mining subjectively interesting attributed subgraphs. Data Min Knowl Discov 34(2):355\u2013393","journal-title":"Data Min Knowl Discov"},{"issue":"1","key":"714_CR9","first-page":"231","volume":"1","author":"DJ Cook","year":"1994","unstructured":"Cook DJ, Holder LB (1994) Substructure discovery using minimum description length and background knowledge. J Artif Int Res 1(1):231\u2013255","journal-title":"J Artif Int Res"},{"issue":"3","key":"714_CR10","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/s10618-010-0209-3","volume":"23","author":"T De Bie","year":"2011","unstructured":"De Bie T (2011) Maximum entropy models and subjective interestingness: an application to tiles in binary databases. Data Min Knowl Disc 23(3):407\u2013446","journal-title":"Data Min Knowl Disc"},{"key":"714_CR11","doi-asserted-by":"crossref","unstructured":"Ding CH, He X, Zha H, Gu M, Simon HD (2001) A min-max cut algorithm for graph partitioning and data clustering. In: Proceedings 2001 IEEE international conference on data mining. IEEE, pp 107\u2013114","DOI":"10.1109\/ICDM.2001.989507"},{"issue":"4","key":"714_CR12","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1080\/15427951.2004.10129093","volume":"1","author":"GW Flake","year":"2004","unstructured":"Flake GW, Tarjan RE, Tsioutsiouliklis K (2004) Graph clustering and minimum cut trees. Internet Math 1(4):385\u2013408","journal-title":"Internet Math"},{"key":"714_CR13","doi-asserted-by":"crossref","unstructured":"Galimberti E, Barrat A, Bonchi F, Cattuto C, Gullo F (2018) Mining (maximal) span-cores from temporal networks. In: Proceedings of the 27th ACM international conference on information and knowledge management. ACM, pp 107\u2013116","DOI":"10.1145\/3269206.3271767"},{"key":"714_CR14","doi-asserted-by":"crossref","unstructured":"Goebl S, Tonch A, B\u00f6hm C, Plant C (2016) Megs: Partitioning meaningful subgraph structures using minimum description length. In: 2016 IEEE 16th international conference on data mining (ICDM). IEEE, pp 889\u2013894","DOI":"10.1109\/ICDM.2016.0108"},{"key":"714_CR15","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/4643.001.0001","volume-title":"The minimum description length principle","author":"PD Gr\u00fcnwald","year":"2007","unstructured":"Gr\u00fcnwald PD (2007) The minimum description length principle. MIT Press, Cambridge"},{"key":"714_CR16","doi-asserted-by":"crossref","unstructured":"Khan A, Aggarwal C (2016) Query-friendly compression of graph streams. In: 2016 IEEE\/ACM international conference on advances in social networks analysis and mining (ASONAM), pp 130\u2013137","DOI":"10.1109\/ASONAM.2016.7752224"},{"key":"714_CR17","doi-asserted-by":"crossref","unstructured":"Koutra D, Kang U, Vreeken J, Faloutsos C (2014) Vog: summarizing and understanding large graphs. In: Proceedings of the 2014 SIAM international conference on data mining, SIAM, pp 91\u201399","DOI":"10.1137\/1.9781611973440.11"},{"key":"714_CR18","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, pp 454\u2013465","DOI":"10.1137\/1.9781611972801.40"},{"issue":"1145\/1993077","key":"714_CR19","first-page":"1993081","volume":"10","author":"YR Lin","year":"2011","unstructured":"Lin YR, Sun J, Sundaram H, Kelliher A, Castro P, Konuru R (2011) Community discovery via metagraph factorization. ACM Trans Knowl Discov Data doi 10(1145\/1993077):1993081","journal-title":"ACM Trans Knowl Discov Data doi"},{"issue":"2","key":"714_CR20","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02289199","volume":"15","author":"RD Luce","year":"1950","unstructured":"Luce RD (1950) Connectivity and generalized cliques in sociometric group structure. Psychometrika 15(2):169\u2013190","journal-title":"Psychometrika"},{"issue":"2","key":"714_CR21","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/S0304-3975(98)00091-7","volume":"210","author":"H Matsuda","year":"1999","unstructured":"Matsuda H, Ishihara T, Hashimoto A (1999) Classifying molecular sequences using a linkage graph with their pairwise similarities. Theoret Comput Sci 210(2):305\u2013325","journal-title":"Theoret Comput Sci"},{"issue":"2","key":"714_CR22","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/BF00139635","volume":"13","author":"RJ Mokken","year":"1979","unstructured":"Mokken RJ (1979) Cliques, clubs and clans. Quality Quantity 13(2):161\u2013173","journal-title":"Quality Quantity"},{"key":"714_CR23","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, pp 419\u2013432","DOI":"10.1145\/1376616.1376661"},{"issue":"23","key":"714_CR24","doi-asserted-by":"publisher","first-page":"8577","DOI":"10.1073\/pnas.0601602103","volume":"103","author":"ME Newman","year":"2006","unstructured":"Newman ME (2006) Modularity and community structure in networks. Proc Natl Acad Sci 103(23):8577\u20138582","journal-title":"Proc Natl Acad Sci"},{"issue":"2","key":"714_CR25","doi-asserted-by":"publisher","first-page":"026113","DOI":"10.1103\/PhysRevE.69.026113","volume":"69","author":"ME Newman","year":"2004","unstructured":"Newman ME, Girvan M (2004) Finding and evaluating community structure in networks. Phys Rev E 69(2):026113","journal-title":"Phys Rev E"},{"issue":"12","key":"714_CR26","doi-asserted-by":"publisher","first-page":"3231","DOI":"10.1109\/TKDE.2016.2601611","volume":"28","author":"Q Qu","year":"2016","unstructured":"Qu Q, Liu S, Zhu F, Jensen CS (2016) Efficient online summarization of large-scale dynamic networks. IEEE Trans Knowl Data Eng 28(12):3231\u20133245","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"714_CR27","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:416\u2013431","journal-title":"Ann Stat"},{"key":"714_CR28","doi-asserted-by":"crossref","unstructured":"Robardet C (2009) Constraint-based pattern mining in dynamic graphs. In: 2009 ninth IEEE international conference on data mining, pp 950\u2013955","DOI":"10.1109\/ICDM.2009.99"},{"issue":"3","key":"714_CR29","first-page":"27","volume":"11","author":"P Rozenshtein","year":"2017","unstructured":"Rozenshtein P, Tatti N, Gionis A (2017) Finding dynamic dense subgraphs. ACM Trans Knowl Discov Data (TKDD) 11(3):27","journal-title":"ACM Trans Knowl Discov Data (TKDD)"},{"key":"714_CR30","doi-asserted-by":"crossref","unstructured":"Rozenshtein P, Bonchi F, Gionis A, Sozio M, Tatti N (2018) Finding events in temporal networks: segmentation meets densest-subgraph discovery. In: 2018 IEEE international conference on data mining (ICDM). IEEE, pp 397\u2013406","DOI":"10.1109\/ICDM.2018.00055"},{"key":"714_CR31","unstructured":"Saran D, Vreeken J (2019) Summarizing dynamic graphs using mdl. In: Proceedings of the ECMLPKDD workshop on graph embedding and mining (GEM). https:\/\/publications.cispa.saarland\/3002\/"},{"key":"714_CR32","doi-asserted-by":"crossref","unstructured":"Scharw\u00e4chter E, M\u00fcller E, Donges J, Hassani M, Seidl T (2016) Detecting change processes in dynamic networks by frequent graph evolution rule mining. In: 2016 IEEE 16th international conference on data mining (ICDM). IEEE, pp 1191\u20131196","DOI":"10.1109\/ICDM.2016.0158"},{"issue":"3","key":"714_CR33","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0378-8733(83)90028-X","volume":"5","author":"SB Seidman","year":"1983","unstructured":"Seidman SB (1983) Network structure and minimum degree. Social Netw 5(3):269\u2013287","journal-title":"Social Netw"},{"issue":"1","key":"714_CR34","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1080\/0022250X.1978.9989883","volume":"6","author":"SB Seidman","year":"1978","unstructured":"Seidman SB, Foster BL (1978) A graph-theoretic generalization of the clique concept. J Math Sociol 6(1):139\u2013154","journal-title":"J Math Sociol"},{"key":"714_CR35","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 21th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 1055\u20131064","DOI":"10.1145\/2783258.2783321"},{"key":"714_CR36","doi-asserted-by":"crossref","unstructured":"Sun J, Faloutsos C, Faloutsos C, Papadimitriou S, Yu PS (2007) Graphscope: parameter-free mining of large time-evolving graphs. In: Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 687\u2013696","DOI":"10.1145\/1281192.1281266"},{"key":"714_CR37","doi-asserted-by":"crossref","unstructured":"Tang N, Chen Q, Mitra P (2016) Graph stream summarization: from big bang to big crunch. In: SIGMOD 2016\u2014proceedings of the 2016 international conference on management of data, Association for Computing Machinery, Proceedings of the ACM SIGMOD international conference on management of data, pp 1481\u20131496. Conference date: 26-06-2016 Through 01-07-2016. https:\/\/doi.org\/10.1145\/2882903.2915223","DOI":"10.1145\/2882903.2915223"},{"key":"714_CR38","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, pp 965\u2013973","DOI":"10.1145\/2020408.2020566"},{"issue":"2","key":"714_CR39","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1109\/TKDE.2018.2884471","volume":"32","author":"I Tsalouchidou","year":"2020","unstructured":"Tsalouchidou I, Bonchi F, Morales GDF, Baeza-Yates R (2020) Scalable dynamic graph summarization. IEEE Trans Knowl Data Eng 32(2):360\u2013373","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"714_CR40","doi-asserted-by":"crossref","unstructured":"Tsourakakis C, Bonchi F, Gionis A, Gullo F, Tsiarli M (2013) Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees. In: Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 104\u2013112","DOI":"10.1145\/2487575.2487645"},{"issue":"1","key":"714_CR41","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/s10994-015-5539-3","volume":"105","author":"M van Leeuwen","year":"2016","unstructured":"van Leeuwen M, De Bie T, Spyropoulou E, Mesnage C (2016) Subjective interestingness of subgraph patterns. Mach Learn 105(1):41\u201375","journal-title":"Mach Learn"},{"issue":"1","key":"714_CR42","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/s10589-015-9804-y","volume":"64","author":"A Veremyev","year":"2016","unstructured":"Veremyev A, Prokopyev OA, Butenko S, Pasiliao EL (2016) Exact mip-based approaches for finding maximum quasi-cliques and dense subgraphs. Comput Optim Appl 64(1):177\u2013214","journal-title":"Comput Optim Appl"},{"issue":"3","key":"714_CR43","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1016\/j.ejor.2014.09.064","volume":"242","author":"Q Wu","year":"2015","unstructured":"Wu Q, Hao JK (2015) A review on algorithms for maximum clique problems. Eur J Oper Res 242(3):693\u2013709","journal-title":"Eur J Oper Res"},{"key":"714_CR44","doi-asserted-by":"publisher","unstructured":"You Ch, Holder LB, Cook DJ (2009) Learning patterns in the dynamics of biological networks. In: Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining, Association for Computing Machinery, New York, NY, USA, KDD \u201909, pp 977\u2013986. https:\/\/doi.org\/10.1145\/1557019.1557125","DOI":"10.1145\/1557019.1557125"}],"container-title":["Data Mining and Knowledge Discovery"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-020-00714-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10618-020-00714-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-020-00714-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,9]],"date-time":"2021-09-09T00:10:45Z","timestamp":1631146245000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10618-020-00714-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,9]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["714"],"URL":"https:\/\/doi.org\/10.1007\/s10618-020-00714-8","relation":{},"ISSN":["1384-5810","1573-756X"],"issn-type":[{"value":"1384-5810","type":"print"},{"value":"1573-756X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,9]]},"assertion":[{"value":"10 January 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 August 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 September 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}