{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:59:56Z","timestamp":1775638796283,"version":"3.50.1"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,4,12]],"date-time":"2019-04-12T00:00:00Z","timestamp":1555027200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,4,12]],"date-time":"2019-04-12T00:00:00Z","timestamp":1555027200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1527541"],"award-info":[{"award-number":["1527541"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1725702"],"award-info":[{"award-number":["1725702"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1632116"],"award-info":[{"award-number":["1632116"]}],"id":[{"id":"10.13039\/100000001","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":[[2019,6]]},"DOI":"10.1007\/s00778-019-00540-5","type":"journal-article","created":{"date-parts":[[2019,4,12]],"date-time":"2019-04-12T14:03:17Z","timestamp":1555077797000},"page":"351-375","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":34,"title":["Incremental maintenance of maximal cliques in a dynamic graph"],"prefix":"10.1007","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6250-3752","authenticated-orcid":false,"given":"Apurba","family":"Das","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Svendsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Srikanta","family":"Tirthapura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,4,12]]},"reference":[{"key":"540_CR1","first-page":"1","volume":"23","author":"A Angel","year":"2013","unstructured":"Angel, A., Koudas, N., Sarkas, N., Srivastava, D., Svendsen, M., Tirthapura, S.: Dense subgraph maintenance under streaming edge weight updates for real-time story identification. VLDB J. 23, 1\u201325 (2013)","journal-title":"VLDB J."},{"key":"540_CR2","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0166-218X(95)00026-N","volume":"65","author":"D Avis","year":"1993","unstructured":"Avis, D., Fukuda, K.: Reverse search for enumeration. Discrete Appl. Math. 65, 21\u201346 (1993)","journal-title":"Discrete Appl. Math."},{"issue":"5","key":"540_CR3","first-page":"454","volume":"5","author":"B Bahmani","year":"2012","unstructured":"Bahmani, B., Kumar, R., Vassilvitskii, S.: Densest subgraph in streaming and mapreduce. VLDB 5(5), 454\u2013465 (2012)","journal-title":"VLDB"},{"issue":"9","key":"540_CR4","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. Commun. ACM 16(9), 575\u2013577 (1973)","journal-title":"Commun. ACM"},{"key":"540_CR5","doi-asserted-by":"crossref","unstructured":"Chakrabarti, D., Zhan, Y., Faloutsos, C.: R-mat: a recursive model for graph mining. In: Proceedings of the 2004 SIAM International Conference on Data Mining, pp. 442\u2013446. SIAM (2004)","DOI":"10.1137\/1.9781611972740.43"},{"key":"540_CR6","doi-asserted-by":"crossref","unstructured":"Chateau, A., Riou, P., Rivals, E.: Approximate common intervals in multiple genome comparison. In: 2011 IEEE International Conference on Bioinformatics and Biomedicine (BIBM), pp. 131\u2013134. IEEE (2011)","DOI":"10.1109\/BIBM.2011.96"},{"issue":"4","key":"540_CR7","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1145\/2043652.2043654","volume":"36","author":"J Cheng","year":"2011","unstructured":"Cheng, J., Ke, Y., Fu, A.W.-C., Yu, J.X., Zhu, L.: Finding maximal cliques in massive networks. TODS 36(4), 21 (2011)","journal-title":"TODS"},{"key":"540_CR8","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/0214017","volume":"14","author":"N Chiba","year":"1985","unstructured":"Chiba, N., Nishizeki, T.: Arboricity and subgraph listing algorithms. SIAM J. Comput. 14, 210\u2013223 (1985)","journal-title":"SIAM J. Comput."},{"key":"540_CR9","doi-asserted-by":"crossref","unstructured":"Das, A., Sanei-Mehri, S.-V., Tirthapura, S.: Shared-memory parallel maximal clique enumeration. ArXiv preprint \n                    arXiv:1807.09417\n                    \n                   (2018)","DOI":"10.1109\/HiPC.2018.00016"},{"key":"540_CR10","unstructured":"Das, A., Tirthapura, S.: A change-sensitive algorithm for maintaining maximal bicliques in a dynamic bipartite graph. CoRR. \n                    arXiv:abs\/1707.08272\n                    \n                   (2017)"},{"issue":"5699","key":"540_CR11","doi-asserted-by":"publisher","first-page":"1172","DOI":"10.1126\/science.1102036","volume":"306","author":"AC Driskell","year":"2004","unstructured":"Driskell, A.C., An\u00e9, C., Burleigh, J.G., McMahon, M.M., O\u2019Meara, B.C., Sanderson, M.J.: Prospects for building the tree of life from large sequence databases. Science 306(5699), 1172\u20131174 (2004)","journal-title":"Science"},{"key":"540_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10462-011-9235-9","volume":"38","author":"D Duan","year":"2012","unstructured":"Duan, D., Li, Y., Li, R., Lu, Z.: Incremental k-clique clustering in dynamic social networks. Artif. Intell. Rev. 38, 1\u201319 (2012)","journal-title":"Artif. Intell. Rev."},{"key":"540_CR13","doi-asserted-by":"crossref","unstructured":"Eppstein, D., L\u00f6ffler, M., Strash, D.: Listing all maximal cliques in sparse graphs in near-optimal time. In: ISAAC, pp. 403\u2013414 (2010)","DOI":"10.1007\/978-3-642-17517-6_36"},{"key":"540_CR14","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1007\/978-3-642-20662-7_31","volume-title":"Experimental Algorithms, LNCS","author":"D Eppstein","year":"2011","unstructured":"Eppstein, D., Strash, D.: Listing all maximal cliques in large sparse real-world graphs. In: Pardalos, P., Rebennack, S. (eds.) Experimental Algorithms, LNCS, vol. 6630, pp. 364\u2013375. Springer, Berlin (2011)"},{"key":"540_CR15","first-page":"17","volume":"5","author":"P Erds","year":"1960","unstructured":"Erds, P., R\u00e9nyi, A.: On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci 5, 17\u201361 (1960)","journal-title":"Publ. Math. Inst. Hung. Acad. Sci"},{"key":"540_CR16","doi-asserted-by":"crossref","unstructured":"Fan, W., Hu, C., Tian, C.: Incremental graph computations: doable and undoable. In: Proceedings of the 2017 ACM International Conference on Management of Data, pp. 155\u2013169. ACM (2017)","DOI":"10.1145\/3035918.3035944"},{"issue":"5\u20136","key":"540_CR17","doi-asserted-by":"publisher","first-page":"1586","DOI":"10.1007\/s10618-014-0373-y","volume":"28","author":"E Galbrun","year":"2014","unstructured":"Galbrun, E., Gionis, A., Tatti, N.: Overlapping community detection in labeled graphs. Data Min. Knowl. Discov. 28(5\u20136), 1586\u20131610 (2014)","journal-title":"Data Min. Knowl. Discov."},{"key":"540_CR18","unstructured":"Gibson, D., Kumar, R., Tomkins, A.: Discovering large dense subgraphs in massive graphs. In: VLDB, pp. 721\u2013732 (2005)"},{"key":"540_CR19","unstructured":"Hanneman, R.A., Riddle, M.: Introduction to Social Network Methods. \n                    http:\/\/faculty.ucr.edu\/~hanneman\/nettext\/\n                    \n                  . Textbook on the web"},{"key":"540_CR20","doi-asserted-by":"crossref","unstructured":"Huang, X., Cheng, H., Qin, L., Tian, W., Yu. J.X.: Querying k-truss community in large and dynamic graphs. In: SIGMOD, pp. 1311\u20131322 (2014)","DOI":"10.1145\/2588555.2610495"},{"key":"540_CR21","unstructured":"Hung, S.-C., Araujo, M., Faloutsos, C.: Distributed community detection on edge-labeled graphs using spark. In: 12th International Workshop on Mining and Learning with Graphs (MLG), vol. 113 (2016)"},{"key":"540_CR22","first-page":"110","volume":"305","author":"MM-U Hussain","year":"2015","unstructured":"Hussain, M.M.-U., Wang, A., Trajcevski, G.: Co-maxrs: continuous maximizing range-sum query. Sciences 305, 110\u2013129 (2015)","journal-title":"Sciences"},{"key":"540_CR23","doi-asserted-by":"crossref","unstructured":"Java, A., Song, X., Finin, T., Tseng, B.L.: Why we twitter: an analysis of a microblogging community. In: WebKDD\/SNA-KDD, pp. 118\u2013138 (2007)","DOI":"10.1007\/978-3-642-00528-2_7"},{"issue":"3","key":"540_CR24","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","volume":"27","author":"DS Johnson","year":"1988","unstructured":"Johnson, D.S., Yannakakis, M., Papadimitriou, C.H.: On generating all maximal independent sets. Inf. Process. Lett. 27(3), 119\u2013123 (1988)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"540_CR25","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. Theor. Comput. Sci. 250(1), 1\u201330 (2001)","journal-title":"Theor. Comput. Sci."},{"issue":"12","key":"540_CR26","doi-asserted-by":"publisher","first-page":"1198","DOI":"10.1093\/bioinformatics\/17.12.1198","volume":"17","author":"F Kose","year":"2001","unstructured":"Kose, F., Weckwerth, W., Linke, T., Fiehn, O.: Visualizing plant metabolomic correlation networks using clique-metabolite matrices. Bioinformatics 17(12), 1198\u20131208 (2001)","journal-title":"Bioinformatics"},{"issue":"11","key":"540_CR27","doi-asserted-by":"publisher","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.: Trawling the web for emerging cyber-communities. Comput. Netw. 31(11), 1481\u20131493 (1999)","journal-title":"Comput. Netw."},{"key":"540_CR28","doi-asserted-by":"publisher","first-page":"016108","DOI":"10.1103\/PhysRevE.78.016108","volume":"78","author":"S Lehmann","year":"2008","unstructured":"Lehmann, S., Schwartz, M., Hansen, L.K.: Biclique communities. Phys. Rev. E 78, 016108 (2008)","journal-title":"Phys. Rev. E"},{"key":"540_CR29","unstructured":"Leskovec, J., Krevl, A.: SNAP datasets: stanford large network dataset collection. \n                    http:\/\/snap.stanford.edu\/data\n                    \n                   (2014)"},{"issue":"10","key":"540_CR30","first-page":"2453","volume":"26","author":"R Li","year":"2014","unstructured":"Li, R., Yu, J.X., Mao, R.: Efficient core maintenance in large dynamic graphs. TKDE 26(10), 2453\u20132465 (2014)","journal-title":"TKDE"},{"key":"540_CR31","doi-asserted-by":"crossref","unstructured":"Lo, D., Surian, D., Zhang, K., Lim, E.-P.: Mining direct antagonistic communities in explicit trust networks. In: CIKM, pp. 1013\u20131018 (2011)","DOI":"10.1145\/2063576.2063722"},{"key":"540_CR32","doi-asserted-by":"crossref","unstructured":"Makino, K., Uno, T.: New algorithms for enumerating all maximal cliques. In: SWAT, pp. 260\u2013272 (2004)","DOI":"10.1007\/978-3-540-27810-8_23"},{"key":"540_CR33","doi-asserted-by":"crossref","unstructured":"McGregor, A., Tench, D., Vorotnikova, S., Vu, H.T.: Densest subgraph in dynamic graph streams. In: MFCS, pp. 472\u2013482 (2015)","DOI":"10.1007\/978-3-662-48054-0_39"},{"issue":"1","key":"540_CR34","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF02760024","volume":"3","author":"JW Moon","year":"1965","unstructured":"Moon, J.W., Moser, L.: On cliques in graphs. Isr. J. Math. 3(1), 23\u201328 (1965)","journal-title":"Isr. J. Math."},{"issue":"5","key":"540_CR35","doi-asserted-by":"publisher","first-page":"771","DOI":"10.1109\/TSC.2016.2523997","volume":"10","author":"AP Mukherjee","year":"2017","unstructured":"Mukherjee, A.P., Tirthapura, S.: Enumerating maximal bicliques from a large graph using mapreduce. IEEE Trans. Serv. Comput. 10(5), 771\u2013784 (2017)","journal-title":"IEEE Trans. Serv. Comput."},{"issue":"3","key":"540_CR36","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1109\/TKDE.2016.2527643","volume":"29","author":"AP Mukherjee","year":"2017","unstructured":"Mukherjee, A.P., Xu, P., Tirthapura, S.: Enumeration of maximal cliques from an uncertain graph. IEEE Trans. Knowl. Data Eng. 29(3), 543\u2013555 (2017)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"540_CR37","unstructured":"Ottosen, T.J., Vomlel, J.: Honour thy neighbour: clique maintenance in dynamic graphs. In: PGM, pp. 201\u2013208 (2010)"},{"key":"540_CR38","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/978-3-540-32262-7_3","volume-title":"Formal Concept Analysis, LNCS","author":"JE Rome","year":"2005","unstructured":"Rome, J.E., Haralick, R.M.: Towards a formal concept analysis approach to exploring communities on the world wide web. In: Ganter, B., Wille, R. (eds.) Formal Concept Analysis, LNCS, vol. 3403, pp. 33\u201348. Springer, Berlin (2005)"},{"issue":"7","key":"540_CR39","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1093\/molbev\/msg115","volume":"20","author":"MJ Sanderson","year":"2003","unstructured":"Sanderson, M.J., Driskell, A.C., Ree, R.H., Eulenstein, O., Langley, S.: Obtaining maximal concatenated phylogenetic data sets from large sequence databases. Mol. Biol. Evol. 20(7), 1036\u20131042 (2003)","journal-title":"Mol. Biol. Evol."},{"issue":"6","key":"540_CR40","first-page":"433","volume":"6","author":"AE Sariy\u00fcce","year":"2013","unstructured":"Sariy\u00fcce, A.E., Gedik, B., Jacques-Silva, G., Wu, K., \u00c7ataly\u00fcrek, \u00dc.V.: Streaming algorithms for k-core decomposition. PVLDB 6(6), 433\u2013444 (2013)","journal-title":"PVLDB"},{"key":"540_CR41","doi-asserted-by":"crossref","unstructured":"Simsiri, N., Tangwongsan, K., Tirthapura, S., Wu, K.-L.: Work-efficient parallel union-find with applications to incremental graph connectivity. In: European Conference on Parallel Processing, pp. 561\u2013573. Springer (2016)","DOI":"10.1007\/978-3-319-43659-3_41"},{"issue":"2","key":"540_CR42","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1023\/B:COAP.0000008651.28952.b6","volume":"27","author":"V Stix","year":"2004","unstructured":"Stix, V.: Finding all maximal cliques in dynamic graphs. Comput. Optim. Appl. 27(2), 173\u2013186 (2004)","journal-title":"Comput. Optim. Appl."},{"key":"540_CR43","doi-asserted-by":"crossref","unstructured":"Sun, S., Wang, Y., Liao, W., Wang, W.: Mining maximal cliques on dynamic graphs efficiently by local strategies. In: 2017 IEEE 33rd International Conference on Data Engineering (ICDE), pp. 115\u2013118. IEEE (2017)","DOI":"10.1109\/ICDE.2017.53"},{"key":"540_CR44","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1016\/j.jpdc.2014.08.011","volume":"79\u201380","author":"M Svendsen","year":"2015","unstructured":"Svendsen, M., Mukherjee, A.P., Tirthapura, S.: Mining maximal cliques from a large graph using mapreduce: tackling highly uneven subproblem sizes. J. Parallel Distrib. Comput. 79\u201380, 104\u2013114 (2015)","journal-title":"J. Parallel Distrib. Comput."},{"issue":"2","key":"540_CR45","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1006\/jagm.1999.1033","volume":"33","author":"M Thorup","year":"1999","unstructured":"Thorup, M.: Decremental dynamic connectivity. J. Algorithms 33(2), 229\u2013243 (1999)","journal-title":"J. Algorithms"},{"issue":"2","key":"540_CR46","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/s10898-008-9362-2","volume":"44","author":"E Tomita","year":"2009","unstructured":"Tomita, E., Kameda, T.: An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments. J. Glob. Optim. 44(2), 311 (2009)","journal-title":"J. Glob. Optim."},{"key":"540_CR47","unstructured":"Tomita, E., Sutani, Y., Higashi, T., Takahashi, S., Wakatsuki, M.: A simple and faster branch-and-bound algorithm for finding a maximum clique. In: Proceedings of the WALCOM: Algorithms and Computation, 4th International Workshop, WALCOM 2010, Dhaka, Bangladesh, February 10\u201312, 2010, pp. 191\u2013203 (2010)"},{"issue":"1","key":"540_CR48","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/j.tcs.2006.06.015","volume":"363","author":"E Tomita","year":"2006","unstructured":"Tomita, E., Tanaka, A., Takahashi, H.: The worst-case time complexity for generating all maximal cliques and computational experiments. Theor. Comput. Sci. 363(1), 28\u201342 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"540_CR49","unstructured":"Tomita, E., Yoshida, K., Hatta, T., Nagao, A., Ito, H., Wakatsuki, M.: A much faster branch-and-bound algorithm for finding a maximum clique. In: Proceedings of the Frontiers in Algorithmics, 10th International Workshop, FAW 2016, Qingdao, China, June 30\u2013July 2, 2016, pp. 215\u2013226 (2016)"},{"issue":"3","key":"540_CR50","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/0206036","volume":"6","author":"S Tsukiyama","year":"1977","unstructured":"Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput. 6(3), 505\u2013517 (1977)","journal-title":"SIAM J. Comput."},{"key":"540_CR51","doi-asserted-by":"crossref","unstructured":"Wulff-Nilsen, C.: Faster deterministic fully-dynamic graph connectivity. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1757\u20131769. SIAM (2013)","DOI":"10.1137\/1.9781611973105.126"},{"issue":"3","key":"540_CR52","doi-asserted-by":"publisher","first-page":"528","DOI":"10.1016\/j.ympev.2005.02.008","volume":"35","author":"C Yan","year":"2005","unstructured":"Yan, C., Burleigh, J.G., Eulenstein, O.: Identifying optimal incomplete phylogenetic data sets from sequence databases. Mol. phylogenetics Evol. 35(3), 528\u2013535 (2005)","journal-title":"Mol. phylogenetics Evol."}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-019-00540-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00778-019-00540-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-019-00540-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,16]],"date-time":"2020-05-16T15:36:14Z","timestamp":1589643374000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00778-019-00540-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,12]]},"references-count":52,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["540"],"URL":"https:\/\/doi.org\/10.1007\/s00778-019-00540-5","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,4,12]]},"assertion":[{"value":"5 March 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 January 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 April 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 April 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}