{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T13:08:32Z","timestamp":1775912912938,"version":"3.50.1"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319235240","type":"print"},{"value":"9783319235257","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-23525-7_39","type":"book-chapter","created":{"date-parts":[[2015,8,28]],"date-time":"2015-08-28T08:20:13Z","timestamp":1440750013000},"page":"641-654","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":33,"title":["Finding Dense Subgraphs in Relational Graphs"],"prefix":"10.1007","author":[{"given":"Vinay","family":"Jethava","sequence":"first","affiliation":[]},{"given":"Niko","family":"Beerenwinkel","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,8,29]]},"reference":[{"key":"39_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/978-3-540-95995-3_3","volume-title":"Algorithms and Models for the Web-Graph","author":"R Andersen","year":"2009","unstructured":"Andersen, R., Chellapilla, K.: Finding dense subgraphs with size bounds. In: Avrachenkov, K., Donato, D., Litvak, N. (eds.) WAW 2009. LNCS, vol. 5427, pp. 25\u201337. Springer, Heidelberg (2009)"},{"issue":"2","key":"39_CR2","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1006\/jagm.1999.1062","volume":"34","author":"Y Asahiro","year":"2000","unstructured":"Asahiro, Y., Iwama, K., Tamaki, H., Tokuyama, T.: Greedily finding a dense subgraph. Journal of Algorithms 34(2), 203\u2013221 (2000)","journal-title":"Journal of Algorithms"},{"key":"39_CR3","doi-asserted-by":"crossref","unstructured":"Bach, F.R., Lanckriet, G.R.G., Jordan, M.I.: Multiple kernel learning, conic duality, and the SMO algorithm. In: Proceedings of the Twenty-First International Conference on Machine Learning, p. 6 (2004)","DOI":"10.1145\/1015330.1015424"},{"issue":"5","key":"39_CR4","doi-asserted-by":"publisher","first-page":"454","DOI":"10.14778\/2140436.2140442","volume":"5","author":"B Bahmani","year":"2012","unstructured":"Bahmani, B., Kumar, R., Vassilvitskii, S.: Densest subgraph in streaming and mapreduce. Proceedings of the VLDB Endowment 5(5), 454\u2013465 (2012)","journal-title":"Proceedings of the VLDB Endowment"},{"key":"39_CR5","doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U., Vijayaraghavan, A.: Detecting high log-densities: an o (n $$1\/4$$) approximation for densest k-subgraph. In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing (STOC), pp. 201\u2013210. ACM (2010)","DOI":"10.1145\/1806689.1806719"},{"key":"39_CR6","doi-asserted-by":"crossref","unstructured":"Boden, B., G\u00fcnnemann, S., Hoffmann, H., Seidl, T.: Mining coherent subgraphs in multi-layer graphs with edge labels. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1258\u20131266. ACM (2012)","DOI":"10.1145\/2339530.2339726"},{"key":"39_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/3-540-44436-X_10","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"M Charikar","year":"2000","unstructured":"Charikar, M.: Greedy approximation algorithms for finding dense components in a graph. In: Jansen, K., Khuller, S. (eds.) APPROX 2000. LNCS, vol. 1913, pp. 84\u201395. Springer, Heidelberg (2000)"},{"issue":"2","key":"39_CR8","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1006\/jagm.2001.1183","volume":"41","author":"U Feige","year":"2001","unstructured":"Feige, U., Langberg, M.: Approximation algorithms for maximization problems arising in graph partitioning. Journal of Algorithms 41(2), 174\u2013211 (2001)","journal-title":"Journal of Algorithms"},{"issue":"3","key":"39_CR9","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/s004530010050","volume":"29","author":"U Feige","year":"2001","unstructured":"Feige, U., Peleg, D., Kortsarz, G.: The dense k-subgraph problem. Algorithmica 29(3), 410\u2013421 (2001)","journal-title":"Algorithmica"},{"issue":"1","key":"39_CR10","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1137\/0218003","volume":"18","author":"G Gallo","year":"1989","unstructured":"Gallo, G., Grigoriadis, M.D., Tarjan, R.E.: A fast parametric maximum flow algorithm and applications. SIAM Journal on Computing 18(1), 30\u201355 (1989)","journal-title":"SIAM Journal on Computing"},{"key":"39_CR11","volume-title":"Finding a maximum density subgraph","author":"AV Goldberg","year":"1984","unstructured":"Goldberg, A.V.: Finding a maximum density subgraph. University of California at Berkeley, Berkeley (1984)"},{"issue":"suppl 1","key":"39_CR12","doi-asserted-by":"publisher","first-page":"i213","DOI":"10.1093\/bioinformatics\/bti1049","volume":"21","author":"H Hu","year":"2005","unstructured":"Hu, H., Yan, X., Huang, Y., Han, J., Zhou, X.J.: Mining coherent dense subgraphs across massive biological networks for functional discovery. Bioinformatics 21(suppl 1), i213\u2013i221 (2005)","journal-title":"Bioinformatics"},{"key":"39_CR13","unstructured":"Jethava, V., Martinsson, A., Bhattacharyya, C., Dubhashi, D.: The lovasz $$\\theta $$ function, svms and finding large dense subgraphs. In: Neural Information Processing Systems (NIPS), pp. 1169\u20131177 (2012)"},{"key":"39_CR14","first-page":"3495","volume":"14","author":"V Jethava","year":"2014","unstructured":"Jethava, V., Martinsson, A., Bhattacharyya, C., Dubhashi, D.: Lovasz theta function, SVMs and finding dense subgraphs. Journal of Machine Learning Research 14, 3495\u20133536 (2014)","journal-title":"Journal of Machine Learning Research"},{"issue":"01","key":"39_CR15","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1017\/S0269888912000331","volume":"28","author":"C Jiang","year":"2013","unstructured":"Jiang, C., Coenen, F., Zito, M.: A survey of frequent subgraph mining algorithms. The Knowledge Engineering Review 28(01), 75\u2013105 (2013)","journal-title":"The Knowledge Engineering Review"},{"issue":"4","key":"39_CR16","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/1460797.1460799","volume":"2","author":"D Jiang","year":"2009","unstructured":"Jiang, D., Pei, J.: Mining frequent cross-graph quasi-cliques. ACM Transactions on Knowledge Discovery from Data (TKDD) 2(4), 16 (2009)","journal-title":"ACM Transactions on Knowledge Discovery from Data (TKDD)"},{"key":"39_CR17","doi-asserted-by":"crossref","unstructured":"Johnson, D.S., Trick, M.A.: Cliques, coloring, and satisfiability: second DIMACS implementation challenge, October 11\u201313, 1993, vol. 26. Amer Mathematical Society (1996)","DOI":"10.1090\/dimacs\/026"},{"key":"39_CR18","unstructured":"Kannan, R., Vinay, V.: Analyzing the structure of large graphs. Rheinische Friedrich-Wilhelms-Universit\u00e4t Bonn (1999)"},{"issue":"4","key":"39_CR19","doi-asserted-by":"publisher","first-page":"1025","DOI":"10.1137\/S0097539705447037","volume":"36","author":"S Khot","year":"2006","unstructured":"Khot, S.: Ruling out ptas for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM Journal on Computing 36(4), 1025\u20131071 (2006)","journal-title":"SIAM Journal on Computing"},{"key":"39_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1007\/978-3-642-02927-1_50","volume-title":"Automata, Languages and Programming","author":"S Khuller","year":"2009","unstructured":"Khuller, S., Saha, B.: On finding dense subgraphs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol. 5555, pp. 597\u2013608. Springer, Heidelberg (2009)"},{"key":"39_CR21","doi-asserted-by":"crossref","unstructured":"Lee, V.E., Ruan, N., Jin, R., Aggarwal, C.: A survey of algorithms for dense subgraph discovery. Managing and Mining Graph Data 303\u2013336 (2010)","DOI":"10.1007\/978-1-4419-6045-0_10"},{"key":"39_CR22","unstructured":"Leskovec, J., Krevl, A.: SNAP Datasets: Stanford large network dataset collection (June 2014). \n                      http:\/\/snap.stanford.edu\/data"},{"key":"39_CR23","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Kleinberg, J., Faloutsos, C.: Graphs over time: densification laws, shrinking diameters and possible explanations. In: Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, pp. 177\u2013187. ACM (2005)","DOI":"10.1145\/1081870.1081893"},{"issue":"6","key":"39_CR24","doi-asserted-by":"publisher","first-page":"e1001106","DOI":"10.1371\/journal.pcbi.1001106","volume":"7","author":"W Li","year":"2011","unstructured":"Li, W., Liu, C.-C., Zhang, T., Li, H., Waterman, M.S., Zhou, X.J.: Integrative analysis of many weighted co-expression networks using tensor computation. PLoS computational biology 7(6), e1001106 (2011)","journal-title":"PLoS computational biology"},{"key":"39_CR25","unstructured":"Papailiopoulos, D., Mitliagkas, I., Dimakis, A., Caramanis, C.: Finding dense subgraphs via low-rank bilinear optimization. In: Proceedings of the 31st International Conference on Machine Learning (ICML-14), pp. 1890\u20131898 (2014)"},{"key":"39_CR26","unstructured":"Pei, J., Jiang, D., Zhang, A.: Mining cross-graph quasi-cliques in gene expression and protein interaction data. In: Proceedings of the 21st International Conference on Data Engineering. ICDE 2005, pp. 353\u2013356. IEEE (2005)"},{"key":"39_CR27","first-page":"2491","volume":"9","author":"A Rakotomamonjy","year":"2008","unstructured":"Rakotomamonjy, A., Bach, F., Canu, S., Grandvalet, Y.: Simplemkl. Journal of Machine Learning Research 9, 2491\u20132521 (2008)","journal-title":"Journal of Machine Learning Research"},{"issue":"2","key":"39_CR28","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1287\/opre.42.2.299","volume":"42","author":"SS Ravi","year":"1994","unstructured":"Ravi, S.S., Rosenkrantz, D.J., Tayi, G.K.: Heuristic and special case algorithms for dispersion problems. Operations Research 42(2), 299\u2013310 (1994)","journal-title":"Operations Research"},{"key":"39_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/BFb0053974","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"A Srivastav","year":"1998","unstructured":"Srivastav, A., Wolf, K.: Finding dense subgraphs with semidefinite programming. In: Jansen, K., Rolim, J.D.P. (eds.) APPROX 1998. LNCS, vol. 1444, pp. 181\u2013191. Springer, Heidelberg (1998)"},{"key":"39_CR30","doi-asserted-by":"crossref","unstructured":"Tsourakakis, C., Bonchi, F., Gionis, A., Gullo, F., Tsiarli, M.: 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, pp. 104\u2013112. ACM (2013)","DOI":"10.1145\/2487575.2487645"},{"key":"39_CR31","doi-asserted-by":"crossref","unstructured":"Yan, X., Zhou, X., Han, J.: Mining closed relational graphs with connectivity constraints. In: Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, pp. 324\u2013333. ACM (2005)","DOI":"10.1145\/1081870.1081908"},{"issue":"1","key":"39_CR32","first-page":"899","volume":"14","author":"X-T Yuan","year":"2013","unstructured":"Yuan, X.-T., Zhang, T.: Truncated power method for sparse eigenvalue problems. The Journal of Machine Learning Research 14(1), 899\u2013925 (2013)","journal-title":"The Journal of Machine Learning Research"},{"key":"39_CR33","doi-asserted-by":"crossref","unstructured":"Zeng, Z., Wang, J., Zhou, L., Karypis, G.: Coherent closed quasi-clique discovery from large dense graph databases. In: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 797\u2013802. ACM (2006)","DOI":"10.1145\/1150402.1150506"},{"key":"39_CR34","unstructured":"Zhang, T.: Multi-stage convex relaxation for non-convex optimization. Technical report, Rutgers University (2009)"}],"container-title":["Lecture Notes in Computer Science","Machine Learning and Knowledge Discovery in Databases"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-23525-7_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,7]],"date-time":"2020-09-07T00:09:46Z","timestamp":1599437386000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-23525-7_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319235240","9783319235257"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-23525-7_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"29 August 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}