Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Near-Optimal Asymmetric Binary Matrix Partitions Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Densest Subgraph in Dynamic Graph Streams

Authors : Andrew McGregor, David Tench, Sofya Vorotnikova, Hoa T. Vu

Published in: Mathematical Foundations of Computer Science 2015

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this paper, we consider the problem of approximating the densest subgraph in the dynamic graph stream model. In this model of computation, the input graph is defined by an arbitrary sequence of edge insertions and deletions and the goal is to analyze properties of the resulting graph given memory that is sub-linear in the size of the stream. We present a single-pass algorithm that returns a \((1+\epsilon )\) approximation of the maximum density with high probability; the algorithm uses \(O(\epsilon ^{-2} n {{\mathrm{polylog}}}~n)\) space, processes each stream update in \({{\mathrm{polylog}}}(n)\) time, and uses \({{\mathrm{poly}}}(n)\) post-processing time where n is the number of nodes. The space used by our algorithm matches the lower bound of Bahmani et al. (PVLDB 2012) up to a poly-logarithmic factor for constant \(\epsilon \). The best existing results for this problem were established recently by Bhattacharya et al. (STOC 2015). They presented a \((2+\epsilon )\) approximation algorithm using similar space and another algorithm that both processed each update and maintained a \((4+\epsilon )\) approximation of the current maximum density in \({{\mathrm{polylog}}}(n)\) time per-update.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape
next chapter The Offline Carpool Problem Revisited
Footnotes
1
Throughout this paper, we say an event holds with high probability if the probability is at least \(1-n^{-c}\) for some constant \(c>0\).
 
Literature
1.
Ahn, K.J., Cormode, G., Guha, S., McGregor, A., Wirth, A.: Correlation clustering in data streams. In: Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, July 6–11, 2015 (2015)
2.
Ahn, K.J., Guha, S., McGregor, A.: Analyzing graph structure via linear measurements. In: Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, pp. 459–467 (2012)
3.
Ahn, K.J., Guha, S., McGregor, A.: Graph sketches: sparsification, spanners, and subgraphs. In: 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp. 5–14 (2012)
4.
Ahn, K.J., Guha, S., McGregor, A.: Spectral sparsification in dynamic graph streams. In: Raghavendra, P., Raskhodnikova, S., Jansen, K., Rolim, J.D.P. (eds.) RANDOM 2013 and APPROX 2013. LNCS, vol. 8096, pp. 1–10. Springer, Heidelberg (2013) CrossRef
5.
Assadi, S., Khanna, S., Li, Y., Yaroslavtsev, G.: Tight bounds for linear sketches of approximate matchings. CoRR, abs/1505.01467 (2015)
6.
Bahmani, B., Goel, A., Munagala, K.: Efficient primal-dual graph algorithms for mapreduce. In: Bonato, A., Graham, F.C., Prałat, P. (eds.) WAW 2014. LNCS, vol. 8882, pp. 59–78. Springer, Heidelberg (2014)
7.
Bahmani, B., Kumar, R., Vassilvitskii, S.: Densest subgraph in streaming and mapreduce. PVLDB 5(5), 454–465 (2012)
8.
Bhattacharya, S., Henzinger, M., Nanongkai, D., Tsourakakis, C.E.: Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In: STOC (2015)
9.
Bury, M., Schwiegelshohn, C.: Sublinear estimation of weighted matchings in dynamic data streams. CoRR, abs/1505.02019 (2015)
10.
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–95. Springer, Heidelberg (2000) CrossRef
11.
Chitnis, R.H., Cormode, G., Esfandiari, H., Hajiaghayi, M., McGregor, A., Monemizadeh, M., Vorotnikova, S.: Kernelization via sampling with applications to dynamic graph streams. CoRR, abs/1505.01731 (2015)
12.
Cormode, G., Firmani, D.: A unifying framework for \(\ell _0\)-sampling algorithms. Distrib. Parallel Databases 32(3), 315–335 (2014)CrossRef
13.
Cormode, G., Muthukrishnan, S.: An improved data stream summary: the count-min sketch and its applications. J. Algorithms 55(1), 58–75 (2005)MathSciNetCrossRefMATH
14.
Epasto, A., Lattanzi, S., Sozio, M.: Efficient densest subgraph computation in evolving graphs. In: WWW (2015)
15.
Gallo, G., Grigoriadis, M.D., Tarjan, R.E.: A fast parametric maximum flow algorithm and applications. SIAM J. Comput. 18(1), 30–55 (1989)MathSciNetCrossRefMATH
16.
Gilbert, A.C., Indyk, P.: Sparse recovery using sparse matrices. Proc. IEEE 98(6), 937–947 (2010)CrossRef
17.
Goel, A., Kapralov, M., Post, I.: Single pass sparsification in the streaming model with edge deletions. CoRR, abs/1203.4900 (2012)
18.
Goldberg, A.V.: Finding a maximum density subgraph. Technical report, Berkeley, CA, USA (1984)
19.
Guha, S., McGregor, A., Tench, D.: Vertex and hypergraph connectivity in dynamic graph streams. In: PODS (2015)
20.
Jowhari, H., Saglam, M., Tardos, G.: Tight bounds for lp samplers, finding duplicates in streams, and related problems. In: PODS, pp. 49–58 (2011)
21.
Kapralov, M., Lee, Y.T., Musco, C., Musco, C., Sidford, A.: Single pass spectral sparsification in dynamic streams. In: FOCS (2014)
22.
Kapralov, M., Woodruff, D.P.: Spanners and sparsifiers in dynamic streams. In: ACM Symposium on Principles of Distributed Computing, PODC 2014, Paris, France, July 15–18, 2014, pp. 272–281 (2014)
23.
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–608. Springer, Heidelberg (2009) CrossRef
24.
Konrad, C.: Maximum matching in turnstile streams. CoRR, abs/1505.01460 (2015)
25.
Kutzkov, K., Pagh, R.: Triangle counting in dynamic graph streams. In: Ravi, R., Gørtz, I.L. (eds.) SWAT 2014. LNCS, vol. 8503, pp. 306–318. Springer, Heidelberg (2014) CrossRef
26.
Lee, V., Ruan, N., Jin, R., Aggarwal, C.: A survey of algorithms for dense subgraph discovery. In: Aggarwal, C.C., Wang, H. (eds.) Managing and Mining Graph Data. Advances in Database Systems, vol. 40, pp. 303–336. Springer, US (2010)CrossRef
27.
McGregor, A.: Graph stream algorithms: a survey. SIGMOD Rec. 43(1), 9–20 (2014)CrossRef
28.
Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York (2005)CrossRefMATH
Metadata
Title
Densest Subgraph in Dynamic Graph Streams
Authors
Andrew McGregor
David Tench
Sofya Vorotnikova
Hoa T. Vu
Copyright Year
2015
Publisher
Springer Berlin Heidelberg
Book
Mathematical Foundations of Computer Science 2015

Print ISBN: 978-3-662-48053-3

Electronic ISBN: 978-3-662-48054-0

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-662-48054-0_39

Premium Partner

    Image Credits