ГлавнаяАрхивАлгоритмы приближённого решения одной задачи кластеризации графа

Алгоритмы приближённого решения одной задачи кластеризации графа | Прикладная дискретная математика. 2019. № 45. DOI: 10.17223/20710410/45/7

Изучается задача кластеризации графа. Для варианта задачи, в котором число кластеров не превосходит 3, разработаны три приближённых алгоритма. Первый алгоритм использует в качестве процедуры известный алгоритм Коулмана - Саундерсона - Вирта, который приближённо решает аналогичную задачу с числом кластеров, не превосходящим 2, и многократно применяет локальный поиск. Второй алгоритм основан на оригинальной идее и вообще не использует локальный поиск. В третьем алгоритме процедура локального поиска применяется к допустимому решению, возвращенному вторым алгоритмом. Получены априорные гарантированные оценки точности всех трёх алгоритмов, лучшая из которых равна (6 - 12/n), где n - число вершин данного графа. Проведено также экспериментальное сравнение предложенных алгоритмов.
  • Title Алгоритмы приближённого решения одной задачи кластеризации графа
  • Headline Алгоритмы приближённого решения одной задачи кластеризации графа
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 45
  • Date:
  • DOI 10.17223/20710410/45/7
Ключевые слова
граф, кластеризация, приближённый алгоритм, гарантированная оценка точности, graph, clustering, approximation algorithm, performance guarantee
Авторы
Ссылки
Kulis B., Basu S., Dhil lon I., and Mooney R. Semi-supervised graph clustering: a kernel approach // Machine Learning. 2009. V. 74. No. 1. P. 1-22
Schaeffer S. E. Graph clustering // Computer Science Review. 2005. V. 1. No. 1. P. 27-64
Shamir R., Sharan R., and Tsur D. Cluster graph modification problems // Discr. Appl. Math. 2004. V. 144. No. 1-2. P. 173-182
Bansal N., Blum A., and Chawla S. Correlation clustering // Machine Learning. 2004. V. 56. P. 89-113
Ben-Dor A., Shamir R., and Yakhimi Z. Clustering gene expression patterns // J. Comput. Biol. 1999. V. 6. No. 3-4. P. 281-297
Krivanek M. and Moravek J. NP-hard problems in hierarchical-tree clustering // Acta Informatica. 1986. V. 23. P. 311-323
Giotis I. and Guruswami V. Correlation clustering with a fixed number of clusters // Theory of Computing. 2006. V. 2. No. 1. P. 249-266
Агеев А. А., Ильев В. П., Кононов А. В., Талевнин А. С. Вычислительная сложность задачи аппроксимации графов // Дискрет. анализ и исслед. операций. Сер. 1. 2006. Т. 13. № 1. С. 3-11
Coleman T., Saunderson J., and Wirth A. A local-search 2-approximation for 2-correlation-clustering // LNCS. 2008. V. 5193. P. 308-319
Ильев В. П., Ильева С. Д., Навроцкая А. А. Приближенные алгоритмы для задач аппроксимации графов // Дискрет. анализ и исслед. операций. 2011. Т. 18. № 1. C. 41-60
Charikar M., Guruswami V., and Wirth A. Clustering with qualitative information // J. Comput. Syst. Sci. 2005. V. 71. No. 3. P. 360-383
Ailon N., Charikar M., and Newman A. Aggregating inconsistent information: Ranking and clustering // J. ACM. 2008. V. 55. No. 5. P. 1-27
Chawla S., Makarychev K., Schramm T., and Yaroslavtsev G. Near optimal LP algorithm for correlation clustering on complete and complete k-partite graphs // STOC'15 Symp. on Theory of Computing. N.Y.: ACM, 2015. P. 219-228
Il'ev V., Il'eva S., and Kononov A. Short survey on graph correlation clustering with minimization criteria // LNCS. 2016. V. 9869. P. 25-36
Эрдёш П., Спенсер Дж. Вероятностные методы в комбинаторике. М.: Мир, 1976
Alon N. and Spencer J. The Probabilistic Method. N.Y.: Wiley and Sons, 1992
Алгоритмы приближённого решения одной задачи кластеризации графа | Прикладная дискретная математика. 2019. № 45. DOI: 10.17223/20710410/45/7
Алгоритмы приближённого решения одной задачи кластеризации графа | Прикладная дискретная математика. 2019. № 45. DOI: 10.17223/20710410/45/7