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

Подход к анализу и построению алгоритмов решения одной задачи кластеризации на знаковых графах | Прикладная дискретная математика. 2024. № 64. DOI: 10.17223/20710410/64/9

Рассматривается NP-трудная оптимизационная задача корреляционной кластеризации для неориентированных и невзвешенных знаковых графов без кратных рёбер и петель, где функционал ошибки представляет собой линейную комбинацию межкластерной и внутрикластерной ошибок. Предложен системный подход построения и анализа алгоритмов, основанных на структуре графа, для решения этой задачи. Подход представлен в виде общей схемы, состоящей из шести взаимосвязанных блоков, отражающих основные этапы решения задачи корреляционной кластеризации. С использованием данной схемы проанализированы шесть существующих алгоритмов. Согласно общей схеме построен новый алгоритм CarVeR, который является модификацией алгоритма SGClustα с помощью потенциальных функций. Топология общей схемы открывает возможности для анализа и доказательства вычислительной сложности алгоритмов, что продемонстрировано в теореме о вычислительной сложности алгоритма CarVeR. Представлены вычислительные эксперименты на синтетических данных для сравнения пяти алгоритмов. Результаты экспериментов показали конкурентную способность алгоритма CarVeR как по времени выполнения, так и по минимизации значения функционала ошибки.
  • Title Подход к анализу и построению алгоритмов решения одной задачи кластеризации на знаковых графах
  • Headline Подход к анализу и построению алгоритмов решения одной задачи кластеризации на знаковых графах
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 64
  • Date:
  • DOI 10.17223/20710410/64/9
Ключевые слова
знаковый граф, корреляционная кластеризация, систематизация алгоритмов, потенциальные функции
Авторы
Ссылки
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.
Wahid D. F. and Hassini E. A literature review on correlation clustering: Cross-disciplinary taxonomy with bibliometric analysis // Oper. Res. Forum. 2022. V. 3. Article 47.
Ailon N., Charikar М., and Newm,an A. Aggregating inconsistent information: Ranking and clustering //j. ACM. 2008. V.55. Iss.5. Article 23. R 1 27.
Demaine E. D. and Immorlica N. Correlation clustering with partial information // LNCS. 2003. V.2764. P. 1 13.
Swamy C. Correlation clustering: Maximizing agreements via semidefinite programming // Proc. SODA'04. New Orleans, Louisiana, 2004. P. 526-527.
Bonizzoni P., Vedova D. G., Dondi R., and Jiang T. Correlation clustering and consensus clustering // LNCS. 2005. V.3827. R226 235.
Figueiredo R. and Moura G. Mixed integer programming formulations for clustering problems related to structural balance // Social Networks. 2013. No.35. P.639-651.
Queiroga E., Subramanian A., Figueiredo R., and Frota Yu,.Integer programming formulations and efficient local search for relaxed correlation clustering //j. Glob. Optim. 2021. No. 81. P.919-966.
Doreian P. and Mrvar A. Partitioning signed social networks // Soc.Networks. 2009. No. 31. P.1-11.
Graham R., L., Knuth D., E., and Patashnik O. Concrete Mathematics: A Foundation for Computer Science. 2nd ed. Massachusetts, USA: Addison-Weslev, 1994. 657 p.
Cartwright D. and Harary F. Structural balance: A generalization of Heider's theory // Psychol. Rev. 1956. V.63. No.5. P.227-293.
Doreian P. and Mrvar A. Structural Balance and Partitioning Signed Graphs, http://mrvar2.fdv.si/pajek/SignedNetworks/Bled94.pdf. 1996.
Bansal N., Blum A., and Chawla S. Correlation clustering // Machine Learning. 2004. No. 56. P.89-113.
Doreian P. and Mrvar A. A partitioning approach to structural balance // Soc.Networks. 1996. No. 18. P. 149-168.
Kormen T. H., Leiserson С. E., Rivest R. L., and Stein C.Introduction to Algorithms. 3rd ed. Cambridge: MIT Press, 2009. 1312 p.
Brusco M. J. and Doreian P. Partitioning signed networks using relocation heuristics, tabu search, and variable neighborhood search // Soc.Networks. 2019. No.56. P.70-80.
Levorato M., Figueiredo R., Frota Yu,., and Drummond L. Evaluating balancing on social networks through the efficient solution of correlation clustering problems // EURO J.Comput. Optim. 2017. V. 5. P.467-498.
Ibragimova E., Semenova D., and Soldatenko A.Comparison of two heuristic algorithms for correlation clustering problem solving // 5th Intern. Conf. PCI. Baku, Azerbaijan, 2023. P. 1-4.
Soldatenko A., Semenova D., and Ibragimova E. On heuristic algorithm with greedy strategy for the correlation clustering problem solution // LNCS. 2024. V. 14123. P.462-477.
Солдатенко А. А., Семенова Д. В., Ибрагим,ова Э. И. Алгоритм с потенциальными функциями для задачи разбиения знаковых графов // Информационные технологии и математическое моделирование. Томск, 2023. С. 238-244.
Waxman В. М. Routing of multipoint connections // IEEE J. Selected Areas Commun. 1988. V.6. No. 9. P.1617-1622.
Подход к анализу и построению алгоритмов решения одной задачи кластеризации на знаковых графах | Прикладная дискретная математика. 2024. № 64. DOI: 10.17223/20710410/64/9
Подход к анализу и построению алгоритмов решения одной задачи кластеризации на знаковых графах | Прикладная дискретная математика. 2024. № 64. DOI: 10.17223/20710410/64/9