АЛГОРИТМЫ РАЗБИЕНИЯ ГРАФОВ: ОБЗОР ЛИТЕРАТУРЫ

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

Работа выполнена при финансовой поддержке Министерства пауки и высшего образования Российской Федерации (код проекта 0251-2020-0001)

Список литературы

1.            Итоги третьего квартала 2022 года соцсети Вконтакте. [Electron. Res.]: https://vk.com/ press/q3-2022-results.

2.            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.

3.            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.

4.            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.

5.            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.

6.            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.

7.            Brandes U. et al. On modularity clustering // IEEE Trans. On Knowledge And Data Engineering. 2007.

8.            Гэри M., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

9.            Armbruster М. Branch-and-cut for a semidefinite relaxation of large-scale minimum bisection problems. PhD-thesis. Technische Universit?t Chemnitz. Chemnitz, 2007.

10.          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.

11.          Felner A. Finding optimal solutions to the graph partitioning problem with heuristic search // Ann. Math. Artif. Intell. 2005. V. 45. P. 293-322.

12.          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.

13.          Hager W. W., Phan D. T., Zhang H. An exact algorithm for graph partitioning. Mathematical Programming. 2013. V. 137. P. 531-556.

14.          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.

15.          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.

16.          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.

17.          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.

18.          Walshaw C. An exploration of multilevel combinatorial optimization / Multilevel Optimization in VLSICAD. Combinatorial Optimization. V. 14. Springer, Boston, MA, 2003.

19.          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.

20.          Герб A. P., Омарова Г. А. Применение теории графов в алгебраических многосеточных методах для решения разреженных СЛАУ // Пробл. информ. 2022. № 3. С. 77-89.

21.          Akhremtsev У., Sanders Р., Schulz С. High-quality shared-memory graph partitioning // IEEE Trans, on Parallel and Distributed Systems. 2020.

22.          Qatalyiirek U. V., Aykanat C. Patoh (partitioning tool for hypergraphs). Encyclopedia of parallel computing. Springer, 2011.

23.          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.

24.          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.

25.          Hamann M., Strasser B. Graph bisection with Pareto optimization. Journal of Experimental Algorithmics (JEA). 2018. V. 23. P. 1-34.

26.          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.

27.          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.

28.          Alpert C. J., Huang J. H., Kahng A. B. Multilevel circuit partitioning // Proc, of the 34th Annual design automation Conf. 1997.

29.          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.

30.          Schlag S. et al. High-quality hypergraph partitioning // ACM J. of Experimental Algorithmics. 2023. V. 27. P. 1-39.

31.          Alpert C. J. The ISPD98 circuit benchmark suite // Proc, of the 1998 Intern, symp. on physical design. 1998.

32.          Garey M. R., Johnson D. S. Computers and intractability. San Francisco: Freeman, 1979.

33.          Heuer T., Maas N., Schlag S. Multilevel Hypergraph Partitioning with Vertex Weights Revisited. arXiv preprint arXiv:2102.01378. 2021.

34.          Patwary M. A. K., Garg S., Kang B. Window-based streaming graph partitioning algorithm // Proc, of the Australasian Computer Science Week Multiconf. 2019.

35.          Faraj M. F., Schulz C. Buffered streaming graph partitioning. arXiv preprint arXiv:2102.09384. 2021.

36.          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.

37.          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.

38.          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.

39.          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.

40.          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.

41.          Qatalyiirek U. V. et al. Multithreaded clustering for multi-level hypergraph partitioning // IEEE 26th Intern. Parallel and Distributed Proc. Symp. IEEE, 2012.

42.          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.

43.          LaSalle D., Karypis G. Multi-threaded graph partitioning. 2013 IEEE 27th Intern. Symp. on Parallel and Distributed Processing. IEEE, 2013.

44.          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.

45.          Slota G. M., Madduri K., Rajamanickam S. Complex network partitioning using label propagation // SIAM J. Scien. Comput. 2016. V. 38, iss. 5.

46.          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.

47.          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.

48.          Savage J. E., Wloka M. G. Parallelism in graph-partitioning // Journal of Parallel and Distributed Computing. 1991. V. 13, iss. 3. P. 257-272.

49.          Gottesbiiren L. et al. Deep multilevel graph partitioning. arXiv preprint arXiv:2105.02022. 2021.

50.          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.

51.          Andersen R., Peres Y. Finding sparse cuts locally using evolving sets // Proc, of the 41st Annual ACM symp. on theory of computing. 2009.

52.          Back T. Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms. Oxford university press, 1996.

53.          Barnard S. T., Simon H. D. Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. Concurrency: Practice and experience. 1994.

54.          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.

55.          Boppana R. B. Eigenvalues and graph bisection: An average-case analysis // 28th Annual Symp. on Foundations of Computer Science (sfcs 1987). IEEE, 1987.

56.          Donath W. E., Hoffman A. J. Lower bounds for the partitioning of graphs // IBM J. of Research and Development. 1973.

57.          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.

58.          Grigni M., Manne F. On the complexity of the generalized block distribution. LNCS. 1996. V. 1117.

59.          LaSalle D. et al. Improving graph partitioning for modern graphs and architectures // Proc, of the 5th Workshop on Irregular Applications: Architectures and Algorithms. 2015.

60.          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.

61.          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.

62.          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.

63.          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

64.          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.

65.          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.

66.          Yasar A. et al. On symmetric rectilinear matrix partitioning. arXiv preprint arXiv:2009.07735. 2020.

67.          Yasar A., Qatalyurek U. V. Heuristics for symmetric rectilinear matrix partitioning. arXiv preprint arXiv: 1909.12209. 2019.