nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

Densest Subgraph in Dynamic Graph Streams

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

Erschienen in: Mathematical Foundations of Computer Science 2015

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape

Nächstes Kapitel The Offline Carpool Problem Revisited

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\).

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)

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)

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)

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

Assadi, S., Khanna, S., Li, Y., Yaroslavtsev, G.: Tight bounds for linear sketches of approximate matchings. CoRR, abs/1505.01467 (2015)

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)

Bahmani, B., Kumar, R., Vassilvitskii, S.: Densest subgraph in streaming and mapreduce. PVLDB 5(5), 454–465 (2012)

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)

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

Titel: Densest Subgraph in Dynamic Graph Streams
verfasst von: Andrew McGregor
David Tench
Sofya Vorotnikova
Hoa T. Vu
Verlag: Springer Berlin Heidelberg
Buch: Mathematical Foundations of Computer Science 2015
Print ISBN: 978-3-662-48053-3

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

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

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner