О методе построения алгоритмов для решения задачи корреляционной кластеризации

Обложка

Цитировать

Полный текст

Аннотация

Развивается техника построения алгоритмов, основанных на структуре сети (NS-алгоритмы), для решения задачи корреляционной кластеризации (CCP) для знаковых сетей. Моделью знаковой сети выступает неориентированный и невзвешенный простой знаковых графов. Эта задача рассматривается в оптимизационной форме с функционалом ошибки в виде линейной комбинации межкластерной и внутрикластерной ошибок. Известно, что в данной постановке задача является NP-трудной. Техника построения NS-алгоритмов основана на системном подходе, представленном в виде общей схемы. Схема состоит из шести взаимосвязанных блоков, каждый из которых отражает основные этапы решения CCP. Основная идея техники заключается в комбинировании модулей, представляющих каждый блок схемы. Предложенный подход реализован в виде программного комплекса. В работе представлен модельный NS-алгоритм, построенный с помощью предлагаемой техники. Проведены вычислительные эксперименты на синтетических данных по сравнению модельного алгоритма с уже известными.

Об авторах

Э. И. Ибрагимова

Сибирский федеральный университет

Email: EIbragimova@sfu-kras.ru
ORCID iD: 0000-0002-6852-2281
Scopus Author ID: 58766400800

Assistant of Department of Higher and Applied Mathematics

д. 79, пр. Свободный, г. Красноярск, 660041, Российская Федерация

Д. В. Семенова

Сибирский федеральный университет

Email: DVSemenova@sfu-kras.ru
ORCID iD: 0000-0002-8670-2921
Scopus Author ID: 49261191500
ResearcherId: O-3107-2019

Candidate in Physics and Mathematics, Associate Professor of the Department of Higher and Applied Mathematics

д. 79, пр. Свободный, г. Красноярск, 660041, Российская Федерация

А. А. Солдатенко

Сибирский федеральный университет

Автор, ответственный за переписку.
Email: ASoldatenko@sfu-kras.ru
ORCID iD: 0000-0001-6708-4753
Scopus Author ID: 57194285182
ResearcherId: O-8550-2019

Candidate in Physics and Mathematics, Associate Professor of the Department of Higher and Applied Mathematics

д. 79, пр. Свободный, г. Красноярск, 660041, Российская Федерация

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

  1. Maatouk, A., Hajri, S. E., Assaad, M. & Sari, H. On optimal scheduling for joint spatial division and multiplexing approach in fdd massive mimo. IEEE Trans Signal Process 67, 1006-10213 (2018).
  2. Arinik, N., Figueiredo, R. & andLabatut, V. Multiple partitioning of multiplex signed networks: Application to European parliament votes. Social Networks 60, 83-102 (2020).
  3. Abdelnasser, A., Hossain, E. & Kim, D. I. Clustering and resource allocation for dense femtocells in a two-tier cellular OFDMA network. IEEE Trans Wireless Communications 13, 1628-1641 (2014).
  4. Hüffner, F., Betzler, N. & Niedermeier, R. Optimal Edge Deletions for Signed Graph Balancing in Experimental Algorithms (ed Demetrescu, C.) (Springer Berlin Heidelberg, Berlin, Heidelberg, 2007), 297-310.
  5. Figueiredo, R. & Frota, Y. An improved Branch-and-cut code for the maximum balanced subgraph of a signed graph 2013. ArXiv: abs/1312.4345.
  6. Figueiredo, R. & Frota, Y. The maximum balanced subgraph of a signed graph: Applications and solution approaches. European Journal of Operational Research 236 (2014).
  7. Tang, J., Chang, Y., Aggarwal, C. C. & Liu, H. A Survey of Signed Network Mining in Social Media. ACM Computing Surveys CSUR 49, 1-37 (2015).
  8. Il’ev, V., Il’eva, S. & Kononov, A. Short Survey on Graph Correlation Clustering with Minimization Criteria in Lecture Notes in Computer Science (Germany, Heidelberg, Springer-Verlag, 2016), 25-36.
  9. Wahid, D. F. & Hassini, E. A Literature Review on Correlation Clustering: Cross-disciplinary Taxonomy with Bibliometric Analysis. Oper. Res. Forum 47 (2022).
  10. Queiroga, E., Subramanian, A., Figueiredo, R. & Frota, Y. T. Integer programming formulations and efficient local search for relaxed correlation clustering. Journal of Global Optimization 81, 919-966 (2021).
  11. Ailon, N., Charikar, M. & Newman, A. Aggregating inconsistent information: ranking and clustering in Symposium on the Theory of Computing (2005).
  12. Brusco, M. J. & Doreian, P. Partitioning signed networks using relocation heuristics, tabu search, and variable neighborhood search. Social Networks 56, 70-80 (2019).
  13. Levorato, M., Figueiredo, R., Frota, Y. & Drummond, L. Evaluating balancing on social networks through the efficient solution of correlation clustering problems. EURO Journal on Computational Optimization 5, 467-498 (2017).
  14. Doreian, P. & Mrvar, A. Partitioning signed social networks. Soc. Networks 31, 1-11 (2009).
  15. Harary, F. Structural Balance: A Generalization of Heider’s Theory. Psychological Review 63, 227-293 (1956).
  16. Graham, R. L., Knuth, D. E. & Patashnik, O. Concrete Mathematics: A Foundation for Computer Science 2nd edn. 657 pp. (Addison-Wesley, Massachusetts, USA, 1994).
  17. Doreian, P. & Mrvar, A. A partitioning approach to structural balance. Social Networks 18, 149-168 (1996).
  18. Bansal, N., Blum, A. & Chawla, S. Correlation Clustering. Machine Learning 56, 89-113 (2002).
  19. Soldatenko, A. A., Semenova, D. V. & Ibragimova, E. I. An approach to analyzing and constructing algorithms for solving a one clustering problem on signed graphs. Applied discrete mathematics, 112-127 (2024).
  20. Ibragimova, E. I., D. V. Soldatenko, A. A. & Semenova. Comparison of Two Heuristic Algorithms for Correlation Clustering Problem Solving in 2023 5th International Conference on Problems of Cybernetics and Informatics (PCI) (IEEE, 2023), 1-4.
  21. Soldatenko, A., Semenova, D. & Ibragimova, E. On heuristic algorithm with greedy strategy for the Correlation Clustering problem solution in Lecture Notes in Computer Science (Germany, Heidelberg, Springer-Verlag, 2023), 462-477.
  22. Waxman, B. M. Routing of multipoint connections. IEEE Journal on Selected Areas in Communications 6, 1617-1622 (1988).
  23. Ciotti, V., Bianconi, G., Capocci, A., Colaiori, F. & Panzarasa, P. Degree correlations in signed social networks. Physica A: Statistical Mechanics and its Applications, 25-39 (2015).
  24. Aniyan, A. & Naduvath, S. Induced signed graphs of some classes of graphs. Proceedings of the Jangjeon Mathematical Society 23, 283-291 (2020).
  25. Sudheer, N., George, A. C., Aniyan, A. & Naduvath, S. Some new results on colour-induced signed graphs. Acta Univ. Sapientiae Informatica 14, 338-353 (2022).

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».