Document Open Access Logo

Distributed Dense Subgraph Detection and Low Outdegree Orientation

Authors Hsin-Hao Su, Hoa T. Vu

PDF

File

Thumbnail PDF
PDF
LIPIcs.DISC.2020.15.pdf
  • Filesize: 0.62 MB
  • 18 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Networks → Network algorithms
  • Mathematics of computing → Graph algorithms
Keywords
  • Distributed Algorithms
  • Network Algorithms

Metrics

Abstract

The densest subgraph problem, introduced in the 80s by Picard and Queyranne [Networks 1982] as well as Goldberg [Tech. Report 1984], is a classic problem in combinatorial optimization with a wide range of applications. The lowest outdegree orientation problem is known to be its dual problem. We study both the problem of finding dense subgraphs and the problem of computing a low outdegree orientation in the distributed settings. 
Suppose G = (V,E) is the underlying network as well as the input graph. Let D denote the density of the maximum density subgraph of G. Our main results are as follows.  
- Given a value D̃ ≤ D and 0 < ε < 1, we show that a subgraph with density at least (1-ε)D̃ can be identified deterministically in O((log n) / ε) rounds in the LOCAL model. We also present a lower bound showing that our result for the LOCAL model is tight up to an O(log n) factor. 
In the CONGEST~ model, we show that such a subgraph can be identified in O((log³ n) / ε³) rounds with high probability. Our techniques also lead to an O(diameter + (log⁴ n)/ε⁴)-round algorithm that yields a 1-ε approximation to the densest subgraph. This improves upon the previous O(diameter /ε ⋅ log n)-round algorithm by Das Sarma et al. [DISC 2012] that only yields a 1/2-ε approximation.
- Given an integer D̃ ≥ D and Ω(1/D̃) < ε < 1/4, we give a deterministic, Õ((log² n) /ε²)-round algorithm in the CONGEST~ model that computes an orientation where the outdegree of every vertex is upper bounded by (1+ε)D̃. Previously, the best deterministic algorithm and randomized algorithm by Harris [FOCS 2019] run in Õ((log⁶ n)/ ε⁴) rounds and Õ((log³ n) /ε³) rounds respectively and only work in the LOCAL model.

Cite As Get BibTex

Hsin-Hao Su and Hoa T. Vu. Distributed Dense Subgraph Detection and Low Outdegree Orientation. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.DISC.2020.15

Author Details

Hsin-Hao Su
  • Boston College, Chestnut Hill, MA, USA
Hoa T. Vu
  • San Diego State University, CA, USA

Acknowledgements

We thank David Harris for pointing out Lemma 12, which can be used to improve the running time of the dual rounding algorithm in our previous version.

References

  1. Mohamad Ahmadi, Fabian Kuhn, and Rotem Oshman. Distributed approximate maximum matching in the CONGEST model. In Proc. 32nd International Symposium on Distributed Computing (DISC), pages 6:1-6:17, 2018. Google Scholar
  2. Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications. Theory of Computing, 8(6):121-164, 2012. URL: https://doi.org/10.4086/toc.2012.v008a006.
  3. Baruch Awerbuch. Complexity of network synchronization. J. ACM, 32(4):804-823, 1985. Google Scholar
  4. Bahman Bahmani, Ashish Goel, and Kamesh Munagala. Efficient primal-dual graph algorithms for mapreduce. In WAW, volume 8882 of Lecture Notes in Computer Science, pages 59-78. Springer, 2014. Google Scholar
  5. Bahman Bahmani, Ravi Kumar, and Sergei Vassilvitskii. Densest subgraph in streaming and mapreduce. PVLDB, 5(5):454-465, 2012. Google Scholar
  6. Leonid Barenboim and Michael Elkin. Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition. Distributed Computing, 22(5-6):363-379, 2010. Google Scholar
  7. Edvin Berglin and Gerth Stølting Brodal. A simple greedy algorithm for dynamic graph orientation. Algorithmica, 82(2):245-259, 2020. Google Scholar
  8. Alex Beutel, Wanhong Xu, Venkatesan Guruswami, Christopher Palow, and Christos Faloutsos. Copycatch: Stopping group attacks by spotting lockstep behavior in social networks. In Proceedings of the 22Nd International Conference on World Wide Web (WWW), pages 119-130, 2013. Google Scholar
  9. Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, and Charalampos E. Tsourakakis. Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In Proc. 47th ACM Symposium on Theory of Computing (STOC), pages 173-182, 2015. Google Scholar
  10. Gerth Stølting Brodal and Rolf Fagerberg. Dynamic representations of sparse graphs. In Proc. 6th International Workshop on Algorithms and Data Structures (WADS), pages 342-351, 1999. Google Scholar
  11. Yi-Jun Chang and Thatchaphol Saranurak. Improved distributed expander decomposition and nearly optimal triangle enumeration. CoRR, abs/1904.08037, 2019. Google Scholar
  12. Moses Charikar. Greedy approximation algorithms for finding dense components in a graph. In APPROX, volume 1913 of Lecture Notes in Computer Science, pages 84-95. Springer, 2000. Google Scholar
  13. Jie Chen and Yousef Saad. Dense subgraph extraction with application to community detection. IEEE Trans. on Knowl. and Data Eng., 24(7):1216-1230, 2012. Google Scholar
  14. Yon Dourisboure, Filippo Geraci, and Marco Pellegrini. Extraction and classification of dense communities in the web. In Proc. 16th International Conference on World Wide Web (WWW), pages 461-470, 2007. Google Scholar
  15. Hossein Esfandiari, MohammadTaghi Hajiaghayi, and David P. Woodruff. Applications of uniform sampling: Densest subgraph and beyond. CoRR, abs/1506.04505, 2015. Google Scholar
  16. Manuela Fischer. Improved deterministic distributed matching via rounding. In 31st International Symposium on Distributed Computing (DISC), pages 17:1-17:15, 2017. Google Scholar
  17. Manuela Fischer, Mohsen Ghaffari, and Fabian Kuhn. Deterministic distributed edge-coloring via hypergraph maximal matching. In Proc. 58th IEEE Symposium on Foundations of Computer Science (FOCS), pages 180-191, 2017. Google Scholar
  18. Eugene Fratkin, Brian T. Naughton, Douglas Brutlag, and Serafim Batzoglou. Motifcut: Regulatory motifs finding with maximum density subgraphs. Bioinformatics (Oxford, England), 22:e150-7, August 2006. Google Scholar
  19. Harold N. Gabow and Herbert H. Westermann. Forests, frames, and games: Algorithms for matroid sums and applications. Algorithmica, 7(1):465, June 1992. Google Scholar
  20. G. Gallo, M. D. Grigoriadis, and R. E. Tarjan. A fast parametric maximum flow algorithm and applications. SIAM J. Comput., 18(1):30-55, 1989. Google Scholar
  21. Mohsen Ghaffari, David G. Harris, and Fabian Kuhn. On derandomizing local distributed algorithms. In Proc. 59th IEEE Symposium on Foundations of Computer Science (FOCS), pages 662-673, 2018. Google Scholar
  22. Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, Jukka Suomela, and Jara Uitto. Improved distributed degree splitting and edge coloring. In DISC, pages 19:1-19:15, 2017. Google Scholar
  23. Mohsen Ghaffari, Silvio Lattanzi, and Slobodan Mitrović. Improved parallel algorithms for density-based network clustering. In Proc. 36th International Conference on Machine Learning (ICML), volume 97, pages 2201-2210, 2019. Google Scholar
  24. Mohsen Ghaffari and Hsin-Hao Su. Distributed degree splitting, edge coloring, and orientations. In Proc. of 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2505-2523, 2017. Google Scholar
  25. David Gibson, Ravi Kumar, and Andrew Tomkins. Discovering large dense subgraphs in massive graphs. In Proceedings of the 31st International Conference on Very Large Data Bases (VLDB), pages 721-732, 2005. Google Scholar
  26. A. V. Goldberg. Finding a maximum density subgraph. Technical Report UCB/CSD-84-171, EECS Department, University of California, Berkeley, 1984. Google Scholar
  27. Anupam Gupta, Amit Kumar, and Cliff Stein. Maintaining assignments online: Matching, scheduling, and flows. In Proc. 25th ACM-SIAM Symposium on Discrete Algorithms (SODA), page 468–479, 2014. Google Scholar
  28. David G. Harris. Distributed approximation algorithms for maximum matching in graphs and hypergraphs. In Proc. 60th IEEE Symposium on Foundations of Computer Science (FOCS), pages 700-724, 2019. Google Scholar
  29. R. Kannan and V. Vinay. Analyzing the structure of large graphs. Technical report, 1999. Google Scholar
  30. Samir Khuller and Barna Saha. On finding dense subgraphs. In Proc. 36th International Colloquium on Automata, Languages and Programming (ICALP), pages 597-608, 2009. Google Scholar
  31. Tsvi Kopelowitz, Robert Krauthgamer, Ely Porat, and Shay Solomon. Orienting fully dynamic graphs with worst-case time bounds. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Proc. 41st International Colloquium on Automata, Languages and Programming (ICALP), pages 532-543, 2014. Google Scholar
  32. Łukasz Kowalik. Approximation scheme for lowest outdegree orientation and graph density measures. In Proc. of the 17th International Conference on Algorithms and Computation (ISAAC), pages 557-566, 2006. Google Scholar
  33. Nathan Linial and Michael E. Saks. Low diameter graph decompositions. Combinatorica, 13(4):441-454, 1993. Google Scholar
  34. Andrew McGregor, David Tench, Sofya Vorotnikova, and Hoa T. Vu. Densest subgraph in dynamic graph streams. In MFCS (2), volume 9235 of Lecture Notes in Computer Science, pages 472-482. Springer, 2015. Google Scholar
  35. Gary L. Miller, Richard Peng, and Shen Chen Xu. Parallel graph decompositions using random shifts. In SPAA, pages 196-203. ACM, 2013. Google Scholar
  36. C. St.J. A. Nash-Williams. Decomposition of finite graphs into forests. Journal of the London Mathematical Society, s1-39(1):12-12, 1964. Google Scholar
  37. Jean-Claude Picard and Maurice Queyranne. A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory. Networks, 12(2):141-159, 1982. Google Scholar
  38. Barna Saha, Allison Hoch, Samir Khuller, Louiqa Raschid, and Xiao-Ning Zhang. Dense subgraphs with restrictions and applications to gene annotation graphs. In Research in Computational Molecular Biology, pages 456-472, 2010. Google Scholar
  39. Atish Das Sarma, Ashwin Lall, Danupon Nanongkai, and Amitabh Trehan. Dense subgraphs on dynamic networks. In DISC, volume 7611 of Lecture Notes in Computer Science, pages 151-165. Springer, 2012. Google Scholar
  40. Saurabh Sawlani and Junxing Wang. Near-optimal fully dynamic densest subgraph. In Proc. 52th ACM Symposium on Theory of Computing (STOC), 2020. To appear. Google Scholar
  41. Hsin-Hao Su and Hoa T. Vu. Distributed dense subgraph detection and low outdegree orientation. CoRR, abs/1907.12443, 2019. Google Scholar
  42. M. Thorup. Fully-dynamic min-cut. Combinatorica, 27(1):91-127, 2007. URL: https://doi.org/10.1007/s00493-007-0045-2.
  43. Neal E. Young. Randomized rounding without solving the linear program. In SODA, pages 170-178. ACM/SIAM, 1995. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact