Алгоритмы разбиения графов: обзор литературы

Алгоритмы разбиения графов: обзор литературы

Автор: Герб А.Р., Омарова Г.А.

Журнал: Проблемы информатики @problem-info

Рубрика: Прикладные информационные технологии

Статья в выпуске: 3 (60), 2023 года.

Бесплатный доступ

Работа посвящена разбору современных методов и алгоритмов разбиения графов. Исследованы и проанализированы точные решения, последовательные итерационные, многоуровневые, потоковые и параллельные алгоритмы. Отмечены как преимущества, так и слабые места алгоритмов, выявленные при их реализации.

Графы, огрубление, последовательные и параллельные алгоритмы, многоуровневые алгоритмы

Короткий адрес: https://sciup.org/143181004

IDR: 143181004   |   DOI: 10.24412/2073-0667-2023-3-19-36

Список литературы Алгоритмы разбиения графов: обзор литературы

  • Итоги третьего квартала 2022 года соцсети Вконтакте. [Electron. Res.]: https://vk.com/ press/q3-2022-results.
  • Annual Report 2022 (SEC Filing Form 10-K). Meta Platforms, Inc. [Electron. Res.]: https://dl8rn0p25nwr6d.cloudfront.net/СIK-0001326801/e574646c-c642-42d9-9229- 3892bl3aabfb.pdf.
  • Annual Report 2022 (SEC Filing Form 10-K). Twitter, Inc. [Electron. Res.]: https://www.sec. gov/ix?doc=/Archives/edgar/data/1418091/000141809122000029/twtr-20211231.htm.
  • Gottesbiiren L. et al. Shared-memory n-level hypergraph partitioning // Proc, of the Symp. on algorithm engineering and experiments (ALENEX). Soc. for Industrial and Appl. Math., 2022.
  • Hamers L. et al. Similarity measures in scientometric research: The Jaccard index versus Salton’s cosine formula // Inform. Process, and Manag. 1989. V. 25, iss. 3. P. 315-318.
  • Bourse F., Lelarge M., Vojnovic M. Balanced graph edge partition // Proc, of the 20th ACM SIGKDD Intern, conf, on knowledge discovery and data mining. 2014.
  • Brandes U. et al. On modularity clustering // IEEE Trans. On Knowledge And Data Engineering. 2007.
  • Гэри M., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
  • Armbruster М. Branch-and-cut for a semidefinite relaxation of large-scale minimum bisection problems. PhD-thesis. Technische Universit?t Chemnitz. Chemnitz, 2007.
  • Delling D. et al. Exact combinatorial branch-and-bound for graph bisection // Proc, of the 14th Workshop on Algorithm Engineering and Experiments (ALENEX). Soc. for Industrial and Applied Mathematics, 2012.
  • Felner A. Finding optimal solutions to the graph partitioning problem with heuristic search // Ann. Math. Artif. Intell. 2005. V. 45. P. 293-322.
  • Feldmann A. E., Widmayer P. An O(n4) time algorithm to compute the bisection width of solid grid graphs // Proc, of the Algorithms-ESA 2011: 19th Annual European Symp., Saarbriicken, Germany, Sept. 5-9, 2011. Springer Berlin Heidelberg, 2011.
  • Hager W. W., Phan D. T., Zhang H. An exact algorithm for graph partitioning. Mathematical Programming. 2013. V. 137. P. 531-556.
  • Karisch S. Е., Rendl F., Clausen J. Solving graph bisection problems with semidefinite programming // INFORMS J. on Comput. 2000. V. 12, iss. 3. P. 177-191.
  • Sellmann M., Sensen N., Timajev L. Multicommodity flow approximation used for exact graph partitioning // Algorithms-ESA 2003: 11th Annual European Symp., Budapest, Hungary, Sept. 16-19, 2003. Proc. 11. Springer Berlin Heidelberg, 2003.
  • Fiduccia С. M., Mattheyses R. M. A linear-time heuristic for improving network partitions // Proc, of the 19th Conf, on Design Automation. 1982. P. 175-181.
  • Bui T. N., Jones C. A heuristic for reducing fill-in in sparse matrix factorization // Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (United States), 1993.
  • Walshaw C. An exploration of multilevel combinatorial optimization / Multilevel Optimization in VLSICAD. Combinatorial Optimization. V. 14. Springer, Boston, MA, 2003.
  • Karypis G., Kumar V. A fast and high quality multilevel scheme for partitioning irregular graphs // SIAM Journal on scientific Computing. 1998. V. 20, N 1. P. 359-392.
  • Герб A. P., Омарова Г. А. Применение теории графов в алгебраических многосеточных методах для решения разреженных СЛАУ // Пробл. информ. 2022. № 3. С. 77-89.
  • Akhremtsev У., Sanders Р., Schulz С. High-quality shared-memory graph partitioning // IEEE Trans, on Parallel and Distributed Systems. 2020.
  • Qatalyiirek U. V., Aykanat C. Patoh (partitioning tool for hypergraphs). Encyclopedia of parallel computing. Springer, 2011.
  • Preen R. J., Smith J. Evolutionary n-level hypergraph partitioning with adaptive coarsening // IEEE Trans, on Evolutionary Computation. 2019. V. 23, iss. 6. P. 962-971.
  • Sanders P., Schulz C. Engineering multilevel graph partitioning algorithms // Algorithms-ESA 2011: 19th Annual European Symp., Saarbrucken, Germany, Sept. 5-9, 2011. Proc. 19. Springer Berlin Heidelberg, 2011.
  • Hamann M., Strasser B. Graph bisection with Pareto optimization. Journal of Experimental Algorithmics (JEA). 2018. V. 23. P. 1-34.
  • Henzinger A., Noe A., Schulz C. ILP-based local search for graph partitioning // ACM J. of Experimental Algorithmics (JEA). 2020. V. 25. P. 1-26.
  • Godenschwager C. et al. A framework for hybrid parallel flow simulations with a trillion cells in complex geometries // Proc, of the Intern, conf, on high performance computing, networking, storage and analysis. 2013.
  • Alpert C. J., Huang J. H., Kahng A. B. Multilevel circuit partitioning // Proc, of the 34th Annual design automation Conf. 1997.
  • Osipov V., Sanders P. n-Level graph partitioning // Algorithms-ESA 2010: 18th Annual European Symp., Liverpool, UK, Sept. 6-8, 2010. Proc., Part I 18. Springer Berlin Heidelberg, 2010.
  • Schlag S. et al. High-quality hypergraph partitioning // ACM J. of Experimental Algorithmics. 2023. V. 27. P. 1-39.
  • Alpert C. J. The ISPD98 circuit benchmark suite // Proc, of the 1998 Intern, symp. on physical design. 1998.
  • Garey M. R., Johnson D. S. Computers and intractability. San Francisco: Freeman, 1979.
  • Heuer T., Maas N., Schlag S. Multilevel Hypergraph Partitioning with Vertex Weights Revisited. arXiv preprint arXiv:2102.01378. 2021.
  • Patwary M. A. K., Garg S., Kang B. Window-based streaming graph partitioning algorithm // Proc, of the Australasian Computer Science Week Multiconf. 2019.
  • Faraj M. F., Schulz C. Buffered streaming graph partitioning. arXiv preprint arXiv:2102.09384. 2021.
  • Jafari N., Selvitopi O., Aykanat C. Fast shared-memory streaming multilevel graph partitioning //J. of Parallel and Distributed Computing. 2021. V. 147, iss. 2. P. 140-151.
  • Stanton I., Kliot G. Streaming graph partitioning for large distributed graphs // Proc, of the 18th ACM SIGKDD Intern, conf, on knowledge discovery and data mining. 2012.
  • Slota G. M. et al. Scalable, multi-constraint, complex-objective graph partitioning // IEEE Trans, on Parallel and Distributed Systems. 2020. V. 31, iss. 1. P. 2789-2801.
  • Zhang W., Chen Y., Dai D. AKIN: A streaming graph partitioning algorithm for distributed graph storage systems. 2018 18th IEEE/АСМ Intern. Symp. on Cluster, Cloud and Grid Computing (CCGRID). IEEE, 2018.
  • Tsourakakis C. et al. Fennel: Streaming graph partitioning for massive scale graphs // Proc, of the 7th ACM Intern, conf, on Web search and data mining. 2014.
  • Qatalyiirek U. V. et al. Multithreaded clustering for multi-level hypergraph partitioning // IEEE 26th Intern. Parallel and Distributed Proc. Symp. IEEE, 2012.
  • Meyerhenke H., Sanders P., Schulz C. Partitioning complex networks via size-constrained clustering // Experimental Algorithms: 13th Intern. Symp., SEA 2014, Copenhagen, Denmark, June 29 - July 1, 2014. Proc. 13. Springer International Publishing, 2014.
  • LaSalle D., Karypis G. Multi-threaded graph partitioning. 2013 IEEE 27th Intern. Symp. on Parallel and Distributed Processing. IEEE, 2013.
  • Maleki S. et al. Bipart: a parallel and deterministic hypergraph partitioner // Proc, of the 26th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming. 2021.
  • Slota G. M., Madduri K., Rajamanickam S. Complex network partitioning using label propagation // SIAM J. Scien. Comput. 2016. V. 38, iss. 5.
  • Gottesbiiren L. et al. Scalable shared-memory hypergraph partitioning // Proc, of the Workshop on algorithm engineering and experiments (ALENEX). Soc. for Industrial and Appl. Math., 2021.
  • Gottesbiiren L., Hamann M. Deterministic parallel hypergraph partitioning // Euro-Par 2022: Parallel Processing: 28th Intern, conf, on parallel and distributed computing, Glasgow, UK, Aug. 22-26, 2022. Proc. Cham: Springer International Publishing, 2022.
  • Savage J. E., Wloka M. G. Parallelism in graph-partitioning // Journal of Parallel and Distributed Computing. 1991. V. 13, iss. 3. P. 257-272.
  • Gottesbiiren L. et al. Deep multilevel graph partitioning. arXiv preprint arXiv:2105.02022. 2021.
  • Hamann M. et al. Distributed graph clustering using modularity and map equation // Euro¬Par 2018: Parallel Processing: 24th Intern. Conf, on Parallel and Distributed Computing, Turin, Italy, Aug. 27-31, 2018. Proc. Springer International Publishing, 2018.
  • Andersen R., Peres Y. Finding sparse cuts locally using evolving sets // Proc, of the 41st Annual ACM symp. on theory of computing. 2009.
  • Back T. Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms. Oxford university press, 1996.
  • Barnard S. T., Simon H. D. Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. Concurrency: Practice and experience. 1994.
  • Benlic U., Hao J. K. An effective multilevel memetic algorithm for balanced graph partitioning // 22nd IEEE Intern, conf, on tools with artificial intelligence. IEEE. 2010.
  • Boppana R. B. Eigenvalues and graph bisection: An average-case analysis // 28th Annual Symp. on Foundations of Computer Science (sfcs 1987). IEEE, 1987.
  • Donath W. E., Hoffman A. J. Lower bounds for the partitioning of graphs // IBM J. of Research and Development. 1973.
  • Fiedler M. A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory // Czechoslovak Math. J. 1975. V. 25, iss. 4. P. 619-633.
  • Grigni M., Manne F. On the complexity of the generalized block distribution. LNCS. 1996. V. 1117.
  • LaSalle D. et al. Improving graph partitioning for modern graphs and architectures // Proc, of the 5th Workshop on Irregular Applications: Architectures and Algorithms. 2015.
  • Manne F., S0orevik T. Partitioning an array onto a mesh of processors // Applied parallel computing industrial computation and optimization: 3rd Intern. Workshop, PARA’96 Lyngby, Denmark, Aug. 18-21, 1996. Proceedings 3. Springer Berlin Heidelberg, 1996.
  • Meyerhenke H., Sanders P., Schulz C. Partitioning (hierarchically clustered) complex networks via size-constrained graph clustering // J. of Heuristics. 2016. V. 22, iss. 1. P. 759-782.
  • Sanders P., Schulz C. Distributed evolutionary graph partitioning // Proc, of the 14th workshop on algorithm engineering and experiments (ALENEX). Soc. for Industrial and Appl. Math., 2012.
  • Timothy A. Davis and Yifan Hu. The University of Florida Sparse Matrix Collection. ACM Transactions on Mathematical Software 38, 1, Article 1 (December 2011), 25 pages. DOL https://doi.org/10.1145/2049662.2049663, 2011
  • Ugander J., Backstrom L. Balanced label propagation for partitioning massive graphs // Proc, of the sixth ACM Intern, conf, on Web search and data mining. 2013.
  • Van Bevern R. et al. On the parameterized complexity of computing balanced partitions in graphs // Theory of Computing Systems. 2015. V. 57, iss. 1. P. 1-35.
  • Yasar A. et al. On symmetric rectilinear matrix partitioning. arXiv preprint arXiv:2009.07735. 2020.
  • Yasar A., Qatalyurek U. V. Heuristics for symmetric rectilinear matrix partitioning. arXiv preprint arXiv: 1909.12209. 2019.
Еще
Статья обзорная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp